Математика: Теория чисел.

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

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

  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
      

Вверх по странице, к оглавлению и навигации.