Алгоритм Кунерта

Алгоритм Кунерта — это алгоритм вычисления модульного квадратного корня заданного числа. Алгоритм не требует факторизации модуля и основан на модульных операциях, которые часто просты, когда данное число является простым.

Алгоритм

Чтобы найти y по заданному значению

$B=y^{2}{\bmod {N}},$

он предпринимает следующие шаги:

1. найти модульный квадратный корень из $r\equiv {\sqrt {\pm N}}{\pmod {B}}$. Этот шаг довольно прост, независимо от того, насколько велико N , когда $B$ является простым числом.
2. решить квадратное уравнение, связанное с модульным квадратным корнем из $w^{2}=A\cdot z^{2}+B\cdot z+C$. В большинстве примеров Кунерта в его оригинальной статье это уравнение решается, если C представляет собой целочисленный квадрат и, таким образом, устанавливает z равным нулю.

   Разложите следующее уравнение, чтобы получить квадратичное уравнение

   $((B\cdot z+r)^{2}\pm N)/B=w^{2}.$

   Всегда можно убедиться, что квадратичное уравнение можно решить, изменив модуль N в приведенном выше уравнении. Таким образом

   $((B\cdot z+r)^{2}+(B\cdot F+N))/B=w^{2}$

   обеспечит квадратичное значение $A\cdot z^{2}+D\cdot z+C+F$.

   Затем можно отрегулировать F, чтобы убедиться, что $C+F$ представляет собой квадрат. Для больших модулей, таких как ${\sqrt {67}}{\bmod {67F+RSA260}}$, можно быстро вычислить квадратные корни с помощью этого метода.

   Параметры полиномиального разложения достаточно гибки, поскольку $((67z+r)^{2}+X\cdot RSA260)/(67y)$ можно сделать, например. Довольно легко выбрать X и Y так, что $(r^{2}+X\cdot RSA260)/(67y)$ представляет собой квадрат. Модульный квадратный корень из ${\sqrt {67y}}{\bmod {RSA260}}$ можно принять таким образом.

3. Решив соответствующее квадратное уравнение, мы теперь имеем переменные w и полагаем v = r (если C в квадратном уравнении является натуральным квадратом).
4. Решить переменные $\alpha$ и $\beta$ следующее уравнение:

   $\alpha =w(v+w\beta ),$

5. Получите значение X посредством факторизации следующего полинома:

   $\alpha ^{2}\cdot x^{2}+(2\alpha \beta -N)x+(\beta ^{2}-(y^{2}{\bmod {N}}))$

   получить ответ типа

   $(-37+9x)(1+25x)$

6. Получите модульный квадратный корень с помощью уравнения. Не забудьте установить X так, чтобы указанный выше член был равен нулю. Таким образом, X будет 37/9 или -1/25.

   $y\equiv \alpha X+\beta {\pmod {N}}.$

Пример

Чтобы получить ${\sqrt {41}}{\bmod {856}},$ сначала получить ${\sqrt {-856}}\equiv 13{\pmod {41}}$.

Затем разложим полином:

$((41z+13)^{2}+856)/41=w^{2}$

в

$25+26z+41z^{2}$

Поскольку в данном случае терм C представляет собой квадрат, возьмем $w=5$ и вычислить $v=13$ (в общем, $v=41\cdot z+13$).

Решите для $\alpha$ и $\beta$ следующее уравнение

$\alpha ==w(v+w\beta )$

получение решения $\alpha =15$ и $\beta =-2$. (Могут существовать и другие пары решений этого уравнения.)

Затем факторизуйте следующий полином:

$\alpha ^{2}x^{2}+(2\alpha \beta -856)x+(\beta ^{2}-41)$

получение

$(-37+9x)(1+25x)$

Затем получите модульный квадратный корень через

$15\cdot (37\cdot 9^{-1})+(-2)\equiv 345{\pmod {856}}.$

Убедитесь, что $345^{2}\equiv 41{\pmod {856}}.$

В случае, если ${\sqrt {-856}}{\bmod {41}}$ не имеет ответа, тогда $r\equiv {\sqrt {-856}}{\pmod {b\cdot 856+41}}$ вместо этого можно использовать.

См. также

• Методы вычисления квадратных корней

Ссылки

• Адольф Кунерт, «Отчеты о заседаниях Академии наук», том 75, II, 1877, стр. 7–58.
• Адольф Кунерт, «Отчеты о заседаниях Академии наук», том 82, II, 1880, стр. 342–375.