Алгоритм знаходження квадратного кореня в простому полі.

Визначення і властивості символу Якобі.

Існує алгоритм, що обчислює т.зв. символ Якоби, який дозволяє, принаймні, вирішити питання, чи є число квадратичним лишком за непарним модулем без його факторизації.

Нехай непарне і має наступний канонічний розклад: .

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

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

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

Нехай - цілі, - непарні числа, більші одиниці.

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

;

;

;

, ;

;

.

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

Приклад. Обчислимо символ Якобі .

.

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

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

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

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

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

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

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

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

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

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

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

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