10038

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

Доклад

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

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

Русский

2013-03-20

46.5 KB

12 чел.

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

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

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

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

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

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

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

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

;

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

;   ;

,   ;   .

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


 

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

10437. Кисень у природі. Фізіологічна дія кисню. Одержання кисню в лабораторії. Реакції розкладу. Поняття про каталізатор. Фізичні властивості кисню 93 KB
  Тема: Кисень у природі. Фізіологічна дія кисню. Одержання кисню в лабораторії. Реакції розкладу. Поняття про каталізатор. Фізичні властивості кисню. Тип уроку: комбінований урок з елементами інтерактивності. Навчальна мета: Розглянути елемент Оксиген та просту ре...
10438. Корозія металів та способи захисту від корозії 60.5 KB
  Корозія металів та способи захисту від корозії. Мета: навчальна: дати поняття про корозію металів як окисновідновний процес ознайомитись з причинами її виникнення; показати шкоду якої завдає корозія; розглянути способи захисту металів від корозії. виховна: фо
10439. Динаміка культурних процесів 97.5 KB
  Динаміка культури характеризує трансформаційні процеси всередині культури й у взаємодіях культур, які специфічні цілісністю, закономірністю, спрямованістю і впорядкованістю провідних тенденцій. Для динаміки культури характерною є усталеність взаємодії компонентів
10440. Загальні методи одержання металів. Метали в природі 84.5 KB
  Тема: Загальні методи одержання металів. Метали в природі. Навчальна мета: спираючись на знання періодичного закону та типи хімічних зв’язків поглибити знання учнів про елементи метали їх місце у періодичній системі та особливості будови атомів сформувати поняття
10441. Метали в природі. Загальні методи одержання металів 53.5 KB
  Тема: Метали в природі. Загальні методи одержання металів. Навчальна мета: спираючись на знання періодичного закону та типи хімічних зв’язків поглибити знання учнів про елементи метали їх місце у періодичній системі та особливості будови атомів; сформувати поняття
10442. Основи таємного діловодства та режиму таємності. Організація таємного діловодства 494.5 KB
  Тема 2. Основи таємного діловодства та режиму таємності. Організація таємного діловодства Затверджено на методичнiй нарадi Кафедри медицини катастроф та вiйськової медицини...
10443. Статут внутрішньої служби ЗСУ Збереження і зміцнення здоровя військовослужбовців 243 KB
  Тема 3: Статут внутрішньої служби ЗСУ Збереження і зміцнення здоров’я військовослужбовців Розділ 6. Збереження і зміцнення здоров'я військовослужбовців ...
10444. Диапазон электромагнитного излучения 776.5 KB
  Диапазон электромагнитного излучения делится на ряд поддиапазонов: Гаммаизлучение рентгеновский ультрафиолетовый видимый инфракрасный радиодиапазон. Для задач дистанционного зондирования земли используются видимый инфракрасный радиодиапазон и отчасти ульт...
10445. Реализация JPEG-подобного алгоритма сжатия изображений 109 KB
  Реализация JPEGподобного алгоритма сжатия изображений. Алгоритмы на основе дискретного косинусного преобразования наиболее распространенным из которых является разработанный в начале 1990х годов алгоритм JPEG Joint Photographic Expert Group являются относительно простыми в реал