Тема 6. Квадратичні лишки і нелишки.

37. Алгебраїчні конгруенції другого степеня.

Конгруенція , називається квадратною конгруенцією за модулем . Числоназивається квадратичним лишком за модулем , якщо конгруенція має розв’язки. Число називається квадратичним нелишком за модулем , якщо конгруенція розв’язків не має.

Якщо число є квадратичним лишком за модулем , то називається квадратним коренем з числа за модулем .

Задача знаходження розв’язків квадратичної конгруенції має важливе значення в криптографії.

Виявляється, що у загальному випадку не тільки ця задача, а навіть питання про розв’язуваність квадратичної конгруенції за модулем , який є складеним числом, факторизація якого невідома, є нерозв'язною проблемою. Але для модулів, які є простими числами, ця проблема досить легко розв’язується.

Теорема 1. Якщо – квадратичний лишок за модулем , то конгруенція , , має два розв’язки.

Теорема 2. Зведена система лишків за простим модулем складається з квадратичних лишків, конгруентних числам і квадратичних нелишків.

У разі простого модуля питання про наявність розв’язків конгруенції , , можна з’ясувати за допомогою наступного критерію Ейлера.

Теорема. (критерій Ейлера для визначення квадратичних лишків і нелишків). Нехай – просте непарне число. Число , взаємно просте з , буде квадратичним лишком за модулем тоді і тільки тоді, коли , і буде квадратичним нелишком за модулем тоді і тільки тоді, коли .

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

Існують алгоритми для визначення, чи є дане число квадратичним лишком за простим модулем чи ні. Один з алгоритмів позв'язаний з обчисленням значення символу Лежандра, якій для непарного простого визначається так:

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

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

1) ;

2) Критерій Ейлера: ;

3) ;

4) ;

5) , ;

6) .

7) Квадратичний закон взаємності Гаусса: для будь-яких простих непарних чисел і виконується рівність .

Символ Лежандра можна обчислити за допомогою наступної послідовності дій. (1) Якщо , те виділяємо співмножник ;

(2) приводимо за модулем ;

(3) розкладаємо в добуток ступенів простих чисел, використовуючи мультипликативность символу Лежандра: , потім видаляємо співмножники які є квадратами;

(4) виділяємо двійки, наприклад, якщо , обчислюємо ;

(5) для кожного непарного співмножника застосовуємо квадратичний закон взаємності (зменшуємо величини чисел, що беруть участь в обчисленнях,);

(6) при необхідності переходимо до п.(1).

Приклад. .

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

Символ Якобі має практично всі ті ж властивості, що і символ Лежандра, але за значенням символу Якобі, рівному одиниці, не можна стверджувати, що відповідний лишок – квадратичний.

Для квадратичного лишку символ Якобі, проте, дорівнює одиниці. Отже, коли , то – квадратичний нелишок за модулем .

39. Добування квадратного кореня за простим модулем.

Даний алгоритм призначений для розв’язання відносно порівняння виду за простим модулем . Перед тим як приступити до обчислень, необхідно переконатися внаявності розв'язків порівняння, тобто в тім, що .

Алгоритм розбивається на 3 випадки, в залежності від представлення у виді , , . В алгоритмі істотно використовується критерій Ейлера, який для розв'язного порівняння дає: .

Випадок . Маємо . Помножимо на ліву і праву частину порівняння, одержимо: . Показник праворуч парний, отже, одне з рішень . Оскільки рішень не може бути більш двох, те остаточна відповідь: .

Випадок . Оскільки , те .

Таким чином, вірно одне з двох співвідношень . Оскільки і відомі, то можна перевірити, яке зі співвідношень виконується. Таким чином, можливі наступні два підвипадки.

Якщо вірно , то, очевидно, . Інакше, .

Якщо обидві частини останнього порівняння помножити на число у відомому парному степені, то квадратний корінь з його лівої частини легко записати явно. Ми підберемо зазначений множник так, щоб, крім того, змінився знак у правої частини порівняння.

Таким множником може бути число , оскільки . Отже,

Випадок, . Насамперед, для роботи алгоритму необхідна наявність (довільного) квадратичного нелишку за модулем . Щоб його знайти, приходиться вибирати навмання число, скажемо, і перевіряти співвідношення .

Уточнимо вигляд числа : , де - непарне, очевидно, .

Основна ідея алгоритму – побудувати співвідношення виду .

У випадку успіху, досить помножити обидві частини порівняння на і витягти корінь з обох частин (враховуючи, що число парне). Тому, виходячи з порівняння , ми будемо будувати співвідношення, у яких показник при буде знижуватися вдвічі, поки не стане рівним . Ділення показників на двійки це - послідовне здобуття квадратних коренів з одиниці. На кожнім кроці може з’явитися лише один з коренів: 1 або . При цьому в нас буде досить даних, щоб з'ясувати, який випадок реально має місце. Змінювати знак у ми будемо за допомогою множення частин порівняння на степені числа , причому так, щоб показник степеня в добутку таких додаткових множників завжди залишався парним.