10038

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

Доклад

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

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

Русский

2013-03-20

46.5 KB

12 чел.

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

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

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

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

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

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

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

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

;

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

;   ;

,   ;   .

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


 

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

60591. ВИКОРИСТАННЯ СОЦІАЛЬНИХ МЕРЕЖ У НАВЧАЛЬНО-ВИХОВНОМУ ПРОЦЕСІ В ЗАГАЛЬНО-ОСВІТНІХ НАВЧАЛЬНИХ ЗАЙЛАДАХ 1.68 MB
  Соціальні мережі дають можливість безпосередньо підводити вихованців до тих чи інших дій. Корисного аналізу того чи іншого питання у неформальні обстановці. Соціальні мережі в певній мірі дають можливість оцінити особисте життя вихованців. Часто розміщені фото, окремі альбоми дозволяють встановити напрямки розвитку уподобань і схильностей учнів.
60592. Особенности развития речи у детей раннего возраста 316 KB
  Овладение речью как средством общения возможно лишь на основе достаточно развитого фонематического слуха, который осуществляет определенный анализ, отделяя высоту звуков от их фонематических особенностей, и тонкое дифференцирование самих фонематических различий.
60593. Игровые моменты и опорные конспекты на уроках истории 1.8 MB
  О первостепенном значении игры для естественного развития ребёнка свидетельствует тот факт что ООН провозгласила игру универсальным и неотъемлемым правом ребёнка. Включаясь в процесс игры дети научаются жить в нашем символическом...
60594. Побудова діаграм і графіків в електронних таблицях MS Excel 1.39 MB
  Пізнавальна мета уроку: закріпити навички роботи з ЕТ Excel; поглибити знання учнів по темі Діаграми; навчити учнів будувати різноманітні типи діаграм графіків у електронній таблиці...
60597. Освітньо-кваліфікаційна характеристика випускника професійно-технічного навчального закладу 284 KB
  Повинен уміти: виконувати операції з базами даних на комп’ютерному устаткуванні введення опрацювання накопичення систематизація та виведення інформації відповідно до затверджених процедур та інструкцій з використанням периферійного обладнання систем передавання приймання даних; готувати до роботи устаткування: магнітні диски стрічки картки папір; працювати в текстовому редакторі з введенням тексту та його редагуванням; оперувати з файлами записувати текст на дискету або переносити на папір за допомогою друкувальних пристроїв;...