10038

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

Доклад

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

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

Русский

2013-03-20

46.5 KB

12 чел.

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

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

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

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

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

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

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

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

;

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

;   ;

,   ;   .

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


 

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

81123. У царстві рослин 44.5 KB
  Мета: ознайомити учнів із розмаїттям рослин; формувати поняття дерева кущі трав’янисті рослини; вчити визначати плоди дерев; розвивати у дітей активне спостереження; виховувати любов до природи бажання охороняти і примножувати її красу.
81124. Погода в рідному краї в різні пори року. Предбачення погоди за народними прикметами 51.5 KB
  Мета: продовжувати формувати поняття Твій рідний край; сформувати поняття про погоду в рідному краї; ознайомити учнів із процесом утворення вітру; збагатити уявлення дітей про опади; наголосити на значенні прогнозу погоди для людини; розвивати пізнавальний інтерес, спостережливість...
81125. Лялька мотанка «Дзвіночок» 39 KB
  Обладнання: Шматки тканини круглої форми і різного розміру (одна менше другої), резинки для скручування, газета,шматок тканини білого кольору прямокутної форми, шматок тканини трикутної форми різного кольору. Ляльки для демонстрації: обрядові – 3 штуки, інші – 4 штуки.
81126. Шов «вперед голку», його призначення, прийоми виконання. Оброблення швом серветки 43 KB
  Мета: навчити виконувати шов вперед голку та оздоблювати ним виріб з тканини розвивати увагу мислення виховувати естетичні смаки культуру праці любов до матері націлювати шанобливе ставлення до професії вишивальниці та швачки. Чи хочете ви так навчитись шити і вишивати?
81127. Українська хата. Обереги 73 KB
  Мета: навчити розрізняти давню українську хату від будинків сьогодення; розширити і поглибити знання дітей про особливості українського інтерєру значення оберегів; розвивати мовленнєві уміння збагачувати словниковий запас засвоїти назви предметів українського побуту...
81128. Безопасное поведение дома. Пользование бытовой техникой. Причины возникновения пожаров, аварий. Осторожное отношение к лекарствам 61 KB
  Цель: обобщить и систематизировать знания детей о поведении в чрезвычайных ситуациях; научить учащихся действовать в экстремальных ситуациях; работать с памятками безопасного обращения с огнем, электроприборами, лекарствами, газом, поведения в ситуации «Один дома»...
81129. Человеческие добродетели. Добро начинается с тебя 43 KB
  Цель: продолжить знакомить учащихся с человеческими добродетелями; учить характеризовать действия и явления как проявление добра и зла; раскрыть моральное содержание доброты; воспитывать чувство доброты сопереживания щедрости.
81130. Зима щедра святами 49 KB
  Бесіда Які свята ми святкуємо взимку Якого свята чекаєте з нетерпінням Чому Вірш учень 1 Хоч рік Новий іще не близько Хоч холодно надворі й слизько Та до нас вже скоро Миколай прийде до школиІ принесе усім гостинці Та подарунки у торбинці. Бесіда Яке свято приходить у кожен дім разом з ялинкою?
81131. Надзвичайні ситуації. Дитина та аварійна ситуація 44.5 KB
  Мета: узагальнити знання учнів про аварії, їх негативний вплив на життя людини; навчити правил поведінки під час аварій на підприємствах; виховувати самодисципліну, рішучість, милосердя. Обладнання: зошит, підручник, картки, мультімідійна дошка.