10038

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

Доклад

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

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

Русский

2013-03-20

46.5 KB

12 чел.

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

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

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

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

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

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

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

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

;

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

;   ;

,   ;   .

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


 

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

63456. Рекомендации по выбору средств и систем контроля доступа 145.5 KB
  Аппаратура СКД должна убедиться что доступ предоставляется именно тому лицу которое зарегистрировано как законный пользователь т. Известны разработки СКД основанные на считывании и сравнении конфигураций сетки вен на запястье образцов запаха преобразованных в цифровой вид анализе носящего уникальный характер...
63457. Ограждения периметра, отдельных участков территории. Элементы инженерной укреплённости охраняемых объектов 204.5 KB
  Контроль за выполнением требований настоящего руководящего документа осуществляется подразделениями вневедомственной охраны при включении их представителей в комиссии по обследованию и приемке в эксплуатацию объектов.
63458. Элементы инженерной укреплённости охраняемых объектов 6.99 MB
  Двери деревянные. Двери деревянные. Двери деревянные наружные для жилых и общественных зданий. Двери деревянные внутренние для жилых и общественных зданий.
63459. Основы проектирования систем охраны объектов. Методика определения варианта и тактики охраны 541 KB
  Требования к проекту оборудования объекта ТСОС Методика выбора системы сбора и обработки информации. Технические средства охраны. Состояние физических преград инженерных сооружений имеющих большую стойкость и в связи с этим не блокированных...
63462. Строительство в системе народного хозяйства страны 33.5 KB
  Эффективность капитальных вложений во многом определяется их рациональной структурой. Например технологическая структура капитальных вложений представляет собой соотношение между затратами на производство СМР на приобретение технологического оборудования и прочими затратами.