Файл: Теорія чисел в криптографії.pdf

Питання 4. Символ Якобі.

Якобі узагальнив символ Лежандра на випадок, коли модуль конгруенції P є

Теорема 1.

Для символу Якобі вірні всі властивості 1-6 символу Лежандра.

853

Приклад. Обчислити: 1409

Висновки Після вивчення теми 5 ви повинні знати такі факти:

–Квадратична конгруенція має такий загальний вигляд:

ax 2 + bx + c º 0(mod m);

– Зведена квадратична конгруенція має вигляд: y 2 º C(mod P) ;

– Якщо (C, P) = P , то квадратична конгруенція y 2 º C(mod P) завжди має єдиний розв’язок y ≡ 0(mod P)

58

– Якщо модуль є складеним числом m = p1α1 p2α2 ...pk α k , то розв’язання квадратичної конгруенції зводиться до розв’язання системи конгруенцій виду:

особливості розв’язання:

квадратична конгруенція, в якій не ділиться на p , тобто (C , p) = 1, має 2 різних

розв’язки, якщо

p−1

C 2 ≡ 1(mod p),

або зовсім немає розв’язків, якщо

p−1

C 2 ≡ −1(mod p)

Причому розв’язками є класи лишків з повної найменшої системи лишків або з абсолютно найменшої системи лишків.

–Якщо конгруенція y 2 ≡ C(mod p) має розв’язки, то C носить назву

лишка за модулем p , якщо розв’язків немає, то C - нелишок за модулем p .

–Показником наявності розв’язків у квадратичної конгруенції

Лежандра можна використовуючи 6 властивостей.

– Узагальненням символу Лежандра є символ Якобі. Якщо розглядається конгруенція y 2 ≡ a(mod P), де P = p1 p2 ... pk , то символом Якобі називається показник

Після вивчення теми 4 ви повинні вміти:

– Визначати, чи має квадратична конгруенція y 2 ≡ a(mod m) нульовий розв’язок.

–Спираючись на властивості символу Лежандра, обчислити його для конгруенції

y 2 ≡ a(mod p), ( p - просте число) визначивши тим самим чи є лишком за модулем

pчисло a .

–В разі складного модуля квадратичної конгруенції y 2 ≡ a(mod m) обчислювати для неї символ Якобі.

Контрольні питання до теми №4.

1.Дайте означення квадратичної конгруенції за довільним модулем.

2.Укажіть в якому випадку квадратична конгруенція має єдиний нульовий розв’язок.

3.Назвіть спосіб розв’язання квадратичної конгруенції за складеним модулем.

4.Назвіть критерій Ейлера про наявність розв’язків конгруенції x2 ≡ a(mod p)

59

5.Дайте означення лишка і нелишка за модулем p

6.Назвіть слідство з критерію Ейлера про наявність розв’язку квадратичної конгруенції.

7.Назвіть теорему Ейлера про взаємодію лишків і нелишків по певному простому модулю.

8.Назовіть 6 властивостей символу Лежандра.

9.За допомогою символу Лежандра з’ясуйте, чи є лишком 139 за модулем 5, якщо так, знайдіть розв’язок квадратичної конгруенції x2 ≡ 139(mod 5)

10.За допомогою символу Лежандра з’ясуйте, чи є лишком 98 за модулем 5, якщо так, знайдіть розв’язок квадратичної конгруенції x2 ≡ 98(mod 5)

11.Які лишки з повної системи найменших додатних лишків за модулем 7

a = {0,1,2,3,4,5,6} є лишками для квадратичної конгруенції x2 ≡ a(mod 7)? Скільки таких лишків?

12.Дайте означення символу Якобі за складеним модулем P = p1 p2 ... pk

13.Обчисліть символ Якобі для 393 за модулем 455.

60

Список літератури.

1.Виноградов И.М. Основы теории чисел. – Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2005. – 176 с

2.Сушкевич А.К. Теория чисел. Элементарный курс. – Х.:Издательство ХГУ, 1954. – 204 с.

3.А.А. Бухштаб. Теория чисел, изд. 2, испр., М.: «Просвещение», 1966

4.Конспект лекцій з курсу Застосування теорії чисел у криптографії. Розробник Оглобліна О.І., СумДУ, 2009 р.

5.Грибанов В.У., Титов П.И. Сборник упражений по теории чисел. – М.: Просвещение, 1964. – 144 с.

6.А.А. Кочева Задачник-практикум по алгебре и теории чисел. Ч.3, М.: «Просвещение», 1984 – 40 с.

7.В.А. Александров, С.М. Горшенин Задачник-практикум по теории чисел. М.: Просвещение, 1972. . – 80 с.

8.Методичні вказівки та контрольні завдання з дисципліни «Застосування теорії чисел у криптографії» для студентів спеціальностей «Інформатика» та «Прикладна математика», Розробник Оглобліна О.І., СумДУ, 2010 р.

9.О.Н. Василенко Теоретико-числовые алгоритмы в криптографии. – М.:МЦНМО, 2003. -328 с.

10.Н. Коблиц Курс теории чисел и криптографии. – М.: Научное изд-во ТВП, 2001. - 254

с

11.А.В. Черемушкин Лекции по арифметическим алгоритмам в криптографии. – М.:

МЦНМО, 2002. – 104 с.

61