6037

Символи Лежандра та Якобі

Лабораторная работа

Математика и математический анализ

Символи Лежандра та Якобі Означення. Нехай p - просте, a - ціле число. Символ Лежандра визначається так: Критерій Ейлера. Число a, яке не ділиться на непарне просте p, є квадратичним лишком за модулем p тоді і тільки тоді, коли...

Украинкский

2012-12-27

101.5 KB

2 чел.

Символи Лежандра та Якобі

Означення. Нехай p – просте, a – ціле число. Символ Лежандра  визначається так:

=

Критерій Ейлера. Число a, яке не ділиться на непарне просте p, є квадратичним лишком за модулем p тоді і тільки тоді, коли  º 1 (mod p), і квадратичним нелишком тоді і тільки тоді коли  º -1 (mod p).

Доведення. За теоремою Ферма ap-1  1 (mod p) при НСД(a, p) = 1 та НСД(2, p) = 1. Або:

0 mod p

Звідси вираз в одній із дужок ділиться на p. Обидві дужки не можуть ділитися на p, оскільки тоді на p ділилася б і їх різниця, яка дорівнює 2, а за умовою теореми p – непарне просте число. Якщо a є квадратичним лишком, то a = x2 (mod p) для деякого такого x, що НСД(x, p) = 1. Маємо: º xp-1 º 1 mod p, тобто  º 1 mod p або  - 1 ділиться на p. Якщо a є квадратичним нелишком, то  - 1 не ділиться на p, звідки  + 1 повинно ділитися на p, або  º -1 mod p.

Наслідок.  º (mod p). Якщо число a є квадратичним лишком за модулем p, то за означенням символа Лежандра = 1, а за критерієм Ейлера  (mod p) º 1. Відповідно якщо число a є квадратичним нелишком за модулем p, то = -1 і (mod p)  º -1, звідки і випливає твердження.

Приклад. Чи існує розв’язок рівняння x2  5 (mod 7).

Якщо існує розв’язок рівняння, то число 5 повинно бути квадратичним лишком за модулем 7. Перевіримо це за критерієм Ейлера:

 º 53 (mod 7) º 25 * 5 (mod 7) º 4 * 5 (mod 7) º 20 (mod 7) º -1 (mod 7). Звідси випливає, що 5 є квадратичним нелишком за модулем 7 і рівняння розв’язків не має.

Властивості символа Лежандра.

1.  º (mod p). Вказана властивість є наслідком критерія Ейлера.

Зокрема = 1 та  = .

Отже -1  Qp якщо p  1 (mod 4) та  -1   якщо p º 3 (mod 4).

2.  = *. Властивість випливає з послідовності очевидних порівнянь:

    *   * (mod p).

Зокрема, якщо a  Zp* , то  = 1 та  = .

3. Якщо a º b (mod p), то  = . Властивість випливає з того, що числа одного класа є одночасно або квадратичними лишками, або нелишками. Випливаючи з цієї властивості, можна записати:  = , t  Z.

4. = 1. Одиниця є квадратичним лишком для довільного непарного простого p. Ця властивість випливає з того, що порівняння x2  1 (mod p) завжди має розв’язки x = ± 1 (mod p).

5.  = .

Якщо p = 8k ± 1, то  =  =  = 8k2 ± 2k – парне число.

Якщо p = 8k ± 3, то  =  =  = 8k2 ± 6k + 1 – непарне число.

Отже =1,  якщо p  1 або 7 (mod 8) та  = -1, якщо p  3 або 5 (mod 8).

6. Закон взаємності непарних простих чисел. Якщо p – просте непарне число, відмінне від q, то

*  = .

Помноживши цю рівність на , отримаємо:  =  * . Якщо виконується хоча б одна з рівностей p (mod 4)  1 чи q (mod 4)  1, то  = , інакше  = -.

Символ Якобі є узагальненням символу Лежандра на випадок коли n є непарним, але не обовя’язково простим.

Означення. Нехай n – непарне ціле число, n ³ 3. Відомо, що , де pi – прості числа. Символ Якобі  визначається так:

= ...

Зазначимо, що якщо n просте, то символ Якобі стає символом Лежандра.

Властивості символа Якобі

1. може приймати одне з трьох значень: -1, 0 чи 1. При цьому  = 0 тоді і тільки тоді коли НСД(a, n)  1.

2.  = *. Якщо a  Zn* , то  = 1.

3.  = *.

4. Якщо a  b (mod n), то  = .

5. = 1.

6. =. Отже = 1, якщо n  1 (mod 4) та  = -1, якщо n  3 (mod 4).

7.  = .

Отже =1,  якщо p  1 або 7 (mod 8) та  = -1, якщо p  3 або 5 (mod 8).

8.  =  .

З властивостей символу Якобі випливає, що якщо n непарне, а число a подати у вигляді a = 2ka1, де a1 – непарне число, то

=  =  

Ця формула дає можливість обчислити значення символа Якобі не маючи розкладу числа n на прості множники.

На відміну від символу Лежандра, символ Якобі  не визначає, чи є число a квадратичним лишком за модулем n. Справді, якщо a  Qn , то = 1, але з того що = 1 не випливає a  Qn.

Означення. Нехай n – непарне ціле число, n ³ 3. Число a будемо називати псевдопростим за модулем n, якщо = 1. Множину псевдопростих чисел позначатимо через  = Jn - Qn, де Jn = {a  Zn* |  = 1}.


 

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

21317. Состав текущих затрат, сформированный в зависимости от производственно-хозяйственных целей предприятия РГБ 195.5 KB
  Все затраты на производство и реализацию продукции (работ, услуг) должны быть документально обоснованы и иметь исключительно целевое назначение. Поскольку издержки производства и обращения являются главной составляющей при расчете прибыли организации, они участвуют в расчете налогооблагаемой прибыли...
21318. Категории атак на информацию 317.5 KB
  Существуют четыре основных категории атак: атаки доступа; атаки модификации; атаки на отказ в обслуживании; атаки на отказ от обязательств. Атаки такого рода наиболее разрушительны. Атаки нацеленные на захват информации хранящейся в электронном виде имеют одну интересную особенность: информация не похищается а копируется. Определение атаки доступа Атака доступа это попытка получения злоумышленником информации для просмотра которой у него нет разрешений.
21319. Предмет і завдання екології. Місце екології у системі інших наук. Значення екології для людської цивілізації. Глобальні проблеми екології 56 KB
  З розвитком виробництва очевидною стає обмеженість традиційно використовуваних природних багатств суші, тому в наш час перспективи розвитку виробництва все в більшій мірі звязують з використанням ресурсів Світового океану та космічного простору. Тому можна сказати, що в наш час екологічні проблеми поширилися навіть за межі Землі.
21320. Безопасность сетей 113.46 KB
  Обеспечение безопасности сетей представляет собой сумму мероприятий направленных на предотвращение несанкционированного доступа к ресурсам сети а именно: Безопасность входа в систему Безопасность доступа к файловой системе Безопасность передачи данных по сети Физическая защита оборудования и помещений. Следует отметить что доступ к сети вообще говоря не означает полного доступа ко всем ресурсам. Поэтому в решении этой задачи предусмотрены как средства аутентификации пользователя так и средства описывающие права доступа к различным...
21321. Виртуальная частная сеть. Концепция построения виртуальных частных сетей VPN 161.96 KB
  Концепция построения виртуальных частных сетей VPN. Виртуальной частной сетью Virtual Private Network VPN называют объединение локальных сетей через открытую внешнюю среду глобальную сеть в единую корпоративную сеть обеспечивающую безопасное циркулирование данных. Объединение осуществляется на основе создания туннеля VPN в глобальной сети по которому передаются криптографически защищенные пакеты сообщений. Безопасность использования туннеля основана на взаимной аутентификации сторон криптографическом закрытии передаваемых данных...
21322. Жестовые методики ввода информации в интерактивных системах компьютерной визуализации 41 KB
  Трёхмерность, особенно в случае использования средств виртуальной реальности или “больших” экранов (то есть экранов, диагональ которых измеряется метрами, а количество пикселей – десятками миллионов) требует и новые средства ввода и связанные с ними новые пользовательские интерфейсы
21324. Криптографическая защита информации 144.5 KB
  Кpиптоанализ исследование возможности расшифровывания информации без знания ключей.Шеннона €œТеория связи в секретных системах€ стала началом новой эры научной криптологии с секретными ключами. Классификация криптографических систем Тайнопись Криптография с ключом Симметричные криптоалгоритмы Шифры перестановки Шифры замены подстановки Простой замены Сложной замены Сложные составные шифры Асимметричные криптоалгоритмы Комбинированные гибридные криптосистемы Тайнопись Отправитель и получатель производят над сообщением...
21325. Симметричное и асимметричное шифрование 1.88 MB
  Шифрование это преобразование данных в нечитабельную форму используя ключи шифрования расшифрования дешифрования. Она состоит из: одного или более алгоритмов шифрования математических формул; ключей используемых этими алгоритмами шифрования; системы управления ключами; незашифрованного текста; и зашифрованного текста шифртекста. Существуют две методологии криптографической обработки информации с использованием ключей симметричная и асимметричная. Симметричная секретная методология где и для шифрования и для расшифровки...