Квадратный корень по простому модулю

[Altia]

Здраствуйте.
Не ясен алгоритм - зачем искать обратный элемент в кольце, ведь можно обойтись без него, просто представив r как a в степени t.

Алгоритм решения уравнения x2=a(mod p), где s - const, p - простое, x - из Zp.

1. Вычислить символ Лежандра (a,p)
(a,p)=-1 - решений нет: a - квадр невычет

2. Найти случайное b, такое что (b,p)=-1 (b - квадр невычет)

3. Представить p-1 в виде p-1=2s*t, где t - нечетное

4. Вычислить (a-1)mod p -
обратный элемент в кольце Zp

5. Положить c=(bt)(mod p), r=(a(t+1)/2)(mod p)

6. Цикл с i=1 до s-1:
6.1 Вычислить
d=[(r2*a-1)^(2s-i-1)][mod p]
6.2 Если d=-1(mod p), то r=(r*c)mod p
6.3 Положить c=(c*c)mod p

7. Ответ: r, -r. Можно выбрать один из них, например, положительный.

Алгоритм взят отсюда:
http://algolist.ru/maths/teornum/sqr_mod.php

[Toucan]

Тема перемещена в Карантин.

Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

После того как исправите сообщение, сообщите об этом в теме Сообщение в карантине исправлено.