10038

Определение и свойства символа Лежандра

Доклад

Информатика, кибернетика и программирование

Двучленным квадратичным сравнением называется сравнение вида где неизвестный вычет. Целое число a называется квадратичным вычетом по модулю n если сравнение разрешимо. Если сравнение разрешимо то для составного модуля количество решений как правило больше дву...

Русский

2013-03-20

46.5 KB

12 чел.

Двучленным квадратичным сравнением называется сравнение вида , где - неизвестный вычет.

Целое число a называется квадратичным вычетом по модулю n, если сравнение  разрешимо. Если сравнение разрешимо, то для составного модуля количество решений, как правило, больше двух.

В общем случае, не только данная задача, но даже вопрос о разрешимости квадратичного сравнения по составному модулю, факторизация которого неизвестна, является нерешенной проблемой.

В то же время для модулей, являющихся простыми числами, задача легко поддается анализу.

Определение и свойства символа Лежандра.

Существуют алгоритмы для определения, является ли данное число квадратичным вычетом по простому модулю или нет. Один из алгоритмов связан с вычислением значения т.н. символа Лежандра, который для нечетного простого определяется так:

Значение  называется квадратичным характером числа   по модулю .

Основные свойства символа Лежандра.

;

Критерий Эйлера: ;  

;   ;

,   ;   .

Квадратичный закон взаимности Гаусса: для любых простых нечетных чисел и выполняется равенство .   Символ Лежандра  можно вычислить с помощью следующей последовательности действий. (1) Если , то выделяем сомножитель ;  (2) приводим по модулю ; (3) раскладываем в произведение степеней простых чисел, используя мультипликативность символа Лежандра: , затем удаляем сомножители являющиеся квадратами; (4) выделяем двойки, например, если , вычисляем ; (5) для каждого нечетного сомножителя применяем квадратичный закон взаимности (уменьшаем величины участвующих в вычислениях чисел); (6) при необходимости, переходим к п.(1).


 

А также другие работы, которые могут Вас заинтересовать

10525. Морское страхование 28 KB
  Морское страхование Страхование - способ возмещения случайных потерь. Страхование делится на 4 вида: самострахование государственное коммерческое осуществляют специалисты страховых компаний взаимное добровольные ассоциации судовладельцев...
10526. Страхование. Участники отношений страхования 45.5 KB
  Страхование Страховая премия - это цена страхования. Та плата которую страхователь платит страховщику: а страховая премия: большая и один раз, б страховые взносы: по частям. Страховое возмещение - то возмещение которое страховщик выплачивает страхователю при...
10527. Случаи, когда договор страхования может быть расторгнут 41 KB
  Случаи когда договор страхования может быть расторгнут. Срочный договор: заключается на год. Но если страховой случай наступил то он потом прекращается после выплаты страховки. В результате гибели застрахованного имущества по причинам иным чем страховой случ...
10528. Страхование грузов: КАРГО 39.5 KB
  Существуют районы которые не покрываются страхованием: ─ Юг: ближе к 60 параллели - Север: выше 70 параллели - Финский залив - Гудзон. Страхование грузов: КАРГО. Основные принципы - такие же. В чем отличие: Страхователями грузов могут быть продавец или по...
10529. Коммерческие условия пассажирских перевозок 32.5 KB
  Коммерческие условия пассажирских перевозок. Три категории: Богатые. Курьеры. Бедные. Не выдержало конкуренции с авиацией. Появилось два вида: паромное круизное. Особенность паромов короткие морские. Каюты минимальных р...
10530. Социальная педагогика 27 KB
  Педагогическая деятельность это одна из сторон профессиональной деятельности специалиста по социальной работе. Педагогическая деятельность специалиста направлена на превращение неуправляемой неорганизованной деятельности члена социального сообщества в управляему...
10531. Социальная педагогика: предмет и основные понятия 109 KB
  Социальная педагогика: предмет и основные понятия План. 1. Основная функция и предмет педагогики. 2. Основная функция и предмет социальной педагогики. 3. Основные понятия социальной педагогики. 1. Основная функция и предмет педагогики. Область любой проф
10532. Российский менталитет. Его сущность и национальная специфика 40.5 KB
  Российский менталитет. Его сущность и национальная специфика. Идеалы равенства и социальной справедливости в российской ментальности. 1 равенство и социальная справедливость а также на настороженное отношение к частной собственности и особенное отношение к деньгам...
10533. Структура и механизм функционирования индивидуального сознания. Понятия: хитрость и мудрость; разум и интеллект 58 KB
  Структура и механизм функционирования индивидуального сознания. Понятия: хитрость и мудрость; разум и интеллект Структура сознания. Понятие сознание не однозначно. В широком смысле слова под ним имеют в виду психическое отражение действительности независимо от того...