10038

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

Доклад

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

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

Русский

2013-03-20

46.5 KB

12 чел.

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

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

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

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

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

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

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

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

;

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

;   ;

,   ;   .

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


 

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

37228. Практика и перспективы использования технических средств в учреждении культуры 40.5 KB
  Кроме финансовой затратности изготовления жестких декораций имеется и несколько отрицательных художественнопостановочных моментов их применения. Смена жестких декораций не всегда возможна в течение концерта или спектакля по техническим и экономическим причинам. Проекционные декорации создаваемые позволяют радикальным образом решить все проблемы связанные с использованием жестких декораций следующим образом. Проецируемый слайд точно вписывается в подвешенный экран без геометрических искажений создавая полную иллюзию реальности создаваемых...
37229. Электромузыкальные инструменты 69 KB
  Электромузыкальные инструменты Принцип действия Виды электромузыкальных инструментов Потребительские свойства электромузыкальных инструментов Хранение инструментов Заключение Введение Эмоциональный мир человека невозможно представить без музыки. А термин электрический музыкальный инструмент используется для обозначения инструментов звук которых воспроизводится механически и усиливается или изменяется с помощью электроники. Появлению электромузыкальных инструментов ЭМИ предшествовали инструменты построенные на...
37230. Фотоаппаратура в СКД 106 KB
  Фотоаппаратура в СКД История фотоаппаратуры Виды фотоаппаратов Основные детали фотоаппаратов Современная фотоаппаратура Управление современной фотоаппаратурой Режимы фотоаппаратов Заключение Введение Постоянный обмен информацией короткое время производства экономия финансов польза для окружающей среды вот только несколько причин которые объясняют гигантский рост интереса к фотоаппаратам . Фотоаппарат устройство для получения и фиксации неподвижных изображений материальных объектов при помощи света. Фотоаппарат фотокамера...
37231. Разработка художественно-технических приемов обеспечения проведения социально-культурного мероприятия техническими средствами СКД на основе сценарного плана социально-культурного мероприятия 141.5 KB
  Проведение школьной дискотеки 1.Интерьер помещения для дискотеки 1.Световое оборудование Заключение Введение В большинстве случаев к сожалению дискотеки в школах получают неудовлетворительную оценку. Раньше для успеха дискотеки достаточно было использовать кассету с зарубежными хитами а в качестве освещения использовать 4 фонаря и зеркальный шар.
37232. Техническое обеспечение социально-культурных мероприятий 87 KB
  Функции технических средств на каждом этапе подготовки мероприятия Технические средства и монтаж Заключение Введение В настоящее время всё больше актуализируется вопрос технического оснащения социальнокультурных мероприятий. При этом технические средства могут выступать не только в качестве оснащения социальнокультурной программы мероприятия но и содействовать при разработке этой программы от начального до завершающего этапа облегчать работу режиссёру творческой и технической группе. Если художественное оформление...
37233. Средства пожарной безопасности клубных помещений 75.5 KB
  Основные первичные средства пожаротушения: Огнетушители. Огнетушители предназначаются для тушения очагов горения в начальной их стадии а также для противопожарной защиты небольших сооружений машин и механизмов. Огнетушители бывают переносные и передвижные. Огнетушители с большим объемом заряда с массой не менее 20 но не более 400 кг; могут иметь одну или несколько емкостей с огнетушащим веществом относятся к передвижным их корпуса устанавливаются на специальные тележки.
37234. Разработка плана (схемы) технического оснащения учреждения культуры системой озвучивания 110 KB
  Важнейшей характеристикой колебаний звука является частота число показывающее сколько полных колебаний в секунду совершает например маятник часов струна и т. Система озвучивания зала в учреждении культуры представляет собой усилительную систему применяемую в случаях если звуковая мощность источника звука оратора актеров оркестра недостаточна для обеспечения нормальной слышимости на сравнительно большой зоне расположения слушателей или когда в этой зоне имеются значительные шумы или если у помещения плохие акустические свойства....
37235. Система озвучивания социально-культурных мероприятий 146.5 KB
  Система озвучивания социальнокультурных мероприятий 1. Система озвучивания На протяжении столетий в концертных залах театрах лекционных залах церквах и др. Все это вызвало существенные изменения в требованиях к акустическим параметрам современных больших залов многоцелевого назначения и привело к широкому использованию в них систем озвучивания и звукоусиления. Системой озвучивания называется комплекс электроакустических устройств состоящий из излучателей микрофонов усилителей различных корректоров и др.
37236. Теле и видео аппаратура в СКД 94 KB
  Сейчас весь мир пользуется множеством различных устройств, в разных сферах индустрии. Прогресс не стоит на месте, каждый год, месяц появляются различные устройства. Одними из таких устройств являются устройства теле и видео, которые в свою очередь считаются одними из популярных устройств