10038

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

Доклад

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

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

Русский

2013-03-20

46.5 KB

12 чел.

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

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

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

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

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

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

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

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

;

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

;   ;

,   ;   .

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


 

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

33584. Прохождение государственной службы 86.5 KB
  Прохождение государственной службы Гос.служба деятельность граждан на должностях государственный гражданской службы по обеспечению исполнения полномочий государственных органов и лиц замещающих государственные должности. Цели государственной службы: Социальные выполнение конституционных требований о гос. поддержке соц сферы; реализация обязательств госва по обеспечению определённого урня жизни граждан удовлетворению их материальных и духовных потребностей; обеспечение благосостояния общества Экономические повышение...
33585. Муниципальная служба: задачи, функции, принципы, порядок и условия прохождения 46.5 KB
  Муниципальная служба профессиональная деятельность граждан которая осуществляется на постоянной основе на должностях муниципальной службы замещаемых путем заключения трудового договора контракта. Основные признаки муниципальной службы: 1 это особый вид публичной службы т. в органах местной публичной власти муниципального образования; 2 замещение муниципальным служащим муниципальной должности которая не является выборной должностью; 3 это профессиональная деятельность в органах местного самоуправления за осуществление которой...
33586. Конфликт в организации. Процесс конфликта в организации. Разрешение конфликта в организации 70 KB
  Процесс конфликта в организации. Разрешение конфликта в организации. Разрешение конфликта: силой выигрыш проигрыш через сотрудничество через компромисс уход от конфликта войти в положение другой стороны. Здесь участниками конфликта являются не люди а различные психологические факторы внутреннего мира личности часто кажущиеся или являющиеся несовместимыми: потребности мотивы ценности чувства и т.
33587. Государственный бюджет: доходы и расходы. Проблема дефицита государственного бюджета. Государственный долг 98.5 KB
  Формирование расходов бюджетов РФ. Бюджетная система РФ это основанная на экономических отношениях и государственном устройстве РФ регулируемая нормами права совокупность федерального бюджета бюджетов субъектов РФ местных бюджетов и бюджетов государственных внебюджетных фондов. В отличие от законодательно утверждаемых бюджетов субъектов федерации и федерального бюджета консолидированный бюджет не является законом. В то же время консолидированные бюджеты субъектов РФ состоят из собственно бюджета субъекта РФ и бюджетов муниципальных...
33588. Налоги: сущность, виды, функции. Фискальная политика государства 88 KB
  Налоги: сущность виды функции. Прямые и косвенные налоги. Пропорциональные прогрессивные и регрессивные налоги. Федеральные налоги налоги членов федерации и местные налоги.
33589. Государственно-муниципальные финансы как элемент финансово-кредитной системы 52.5 KB
  Финансовая подсистема ФКС в свою очередь делится на: 1 централизованные финансы: государственный бюджет; внебюджетные фонды; государственный кредит; финансы государственных предприятий; государственное страхование; 2 децентрализованные финансы: финансы коммерческих предприятий и организаций; финансы некоммерческих организаций; финансы кредитных организаций; финансы страховых организаций; 3 финансы домашних хозяйств. Централизованные финансы представляют собой финансы государства и используются для регулирования...
33590. Организация как система. Организация и управления 35 KB
  Характеристики системы. Понятие системы управления. В зависимости от влияния на систему среды и наоборот различают открытые и закрытые системы. Примером закрытой системы является натуральное хозяйство.
33591. Законы организации 39.5 KB
  Законы организации. Закон внутренняя существенная устойчивая связь явлений обусловливающая их необходимое развитие. Законы носят объективный характер и не зависят от сознания людей. Закон синергии.
33592. Социально-экономические и политические процессы: сущность, классификация, особенности исследования 37 KB
  Социальноэкономические и политические процессы: сущность классификация особенности исследования Социально экономические и политические процессы. Управляемые социальноэкономические процессы. Социальноэкономические и политические процессы это изменения в обществе отображающиеся на его благосостоянии политической и экономической стабильности условиях безопасности и пр. Классификация социальных процессов Процессы функционирования обеспечивает воспроизводство качественного состояния объекта и процессы развития обуславливает...