|
Математика: Теория чисел.
Квадратный корень по простому модулю.
Алгоритм решения уравнения 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
![](../../gif/3arrow1.gif) Вверх по странице, к оглавлению и навигации.
| |