10038

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

Доклад

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

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

Русский

2013-03-20

46.5 KB

12 чел.

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

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

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

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

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

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

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

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

;

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

;   ;

,   ;   .

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


 

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

7146. Денежная масса и движение денег во внутреннем экономическом обороте страны 401.38 KB
  Введение Проблемами денег, организации денежного обращения человеческая мысль была занята больше, чем всеми остальными экономическими проблемами. С глубокой древности до наших дней вопросами теории денег занимались экономисты, философы, юристы. И се...
7147. Понятие первобытной культуры. Культура Средневековья и Возрождения 115.5 KB
  Лекция 3. Мировая культура. Часть 1 Шаяхметова А.М., Коровина С.В. А. Понятие первобытной культуры. Б. Культура Древних цивилизаций. В. Античная культура. Г. Культура Средневековья и Возрождения. Понятие первобытной культуры Первобытность - эт...
7148. Основное уравнение передачи по световоду 81 KB
  Основное уравнение передачи по световоду. Рассмотрим волоконный световод без потерь двухслойной конструкции, приведенный на рис...
7149. Построение принципиальной схемы 147 KB
  Построение принципиальной схемы Принципиальная схема строится с учетом помех, фильтров, по входу/выходу, с учётом нагрузок способности, для чего ставятся различные фильтры низких или высоких частот. В результате принципиальные схемы реализуют те же ...
7150. Особенности и периодизация культуры Нового времени. Личность и культура 70 KB
  А. Особенности и периодизация культуры Нового времени. Б. Культура ХХ века. В. Личность и культура. Роль интеллигенции в обеспечении духовного развития общества. Особенности и периодизация культуры Нового времени Специфические особенности рассматрив...
7151. Типы волн в световодах. Критические длины и частоты 76 KB
  Типы волн в световодах. Критические длины и частоты. В сетоводах могут существовать два типа волн: симметричные E0m , H0m несимметричные дипольные EHnm, HEnm. В индексе n - число изменений поля по диаметру m - число изменений поля по периметру. Сим...
7152. Прямоугольные и пирамидальные дешифраторы 959.5 KB
  Прямоугольные и пирамидальные дешифраторы Пирамидальные дешифраторы строятся обычных на двухходовых элементах, где число входных переменных больше двух. Дешифратор наращивается каскадно, путем добавления в дешифратор дополнительных каскадов. Пирамид...
7153. Древнейшие культуры на территории России. Культура Киевской Руси. Культура России нового времени 141.5 KB
  Древнейшие культуры на территории России. Культура Киевской Руси. Русская культура XIII–XVII вв. Культура России нового времени: а) реформы I четверти ХVIII в. и культура б) основные достижения культуры России в ХIХ в. ...
7154. Синхронизированный RS-триггер 662 KB
  Синхронизированный RS-триггер Синхронизированные RS-триггеры могут строится на элементах Особенностью этих триггеров является, то что они имеют дополнительный вход управлений который называется - синхронизированный в отсутствии сигнала....