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

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

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

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

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

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

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

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

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

;

;

;

,;

;

.

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-10-15