10038

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

Доклад

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

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

Русский

2013-03-20

46.5 KB

12 чел.

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

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

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

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

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

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

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

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

;

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

;   ;

,   ;   .

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


 

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

79892. Расчет котельного агрегата Пп-1000-255ГМ (ТГМП-344) 2.11 MB
  НРЧ выполнена из четырех последовательных ходов вертикальных панелей, СРЧ и ВРЧ — из параллельно включенных панелей с горизонтально-подъемным движением среды. Между каждой частью экрана среда в пределах потока полностью перемешивается.
79893. Разработка системы IP видеонаблюдения организации 873.14 KB
  Это не только делает более комфортной работу оператора но и уменьшает длину так называемой ближней зоны видеокамеры. В зависимости oт критериев выбираются в первую очередь камеры со стандартным или высоким разрешением.
79894. Техническое перевооружение, и его влияние на финансовую результативность предприятия 172.48 KB
  Актуальность темы исследования заключается в том, что проблема эффективного развития предприятий выходит на первый план, в связи с усилением дефицита сырьевых ресурсов, ужесточением конкуренции и возникновением процессов глобализации на современном этапе развития экономики.
79895. Исследование взаимосвязи смыслов учения и мотивации выбора профессии в старшем школьном возрасте 120.2 KB
  Разработка проблемы мотивации в современной психологии связана прежде всего с анализом источников активации человека побудительных сил его деятельности поведения с поиском ответа на вопрос что побуждает человека к деятельности каков мотив ради чего он ее осуществляет.
79896. Основні підходи і методи рішення транспортної задачі лінійного програмування 206.84 KB
  Дані задачі відносяться до задач лінійного програмування і можуть бути вирішені симплексним методом. Проте матриця системи обмежень транспортної задачі настільки своєрідна, що для її вирішення розроблені спеціальні методи, які ми розглядатимемо далі.
79898. Модернізація парогенератора ПГВ-1000 для підвищення КПД та надійності в реакторі ВВЕР-1000 910.08 KB
  Водоводяні енергетичні реактори без кипіння води в активній зоні одержали найбільше поширення в усьому світі. До однієї з циркуляційних петель першого контура приєднаний компенсатор тиску за допомогою якого в контурі підтримується заданий тиск води що являється у реакторі і теплоносієм і сповільнювачем нейтронів.
79899. Транзитная подстанция переменного тока 1.24 MB
  Система постоянного тока получила широкое применение для электрической тяги в городском и промышленном электротранспорте, а также для железнодорожного транспорта на первом этапе его электрификации из-за значительных преимуществ двигателей постоянного тока с последовательным возбуждением по тяговым и скоростным характеристикам.