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

Алгоритм Кунерта — это алгоритм для вычисления модульного квадратного корня заданного числа. ^{[1] [2]} Алгоритм не требует факторизации модуля и опирается на модульные операции, что часто легко, когда заданное число является простым.

Алгоритм

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

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

для этого необходимо выполнить следующие шаги:

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

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

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

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

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

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

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

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

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

   ${\displaystyle \alpha =w(v+w\beta ),}$

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

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

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

   ${\displaystyle (-37+9x)(1+25x)}$

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

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

Пример

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

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

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

в

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

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

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

${\displaystyle \alpha ==w(v+w\beta )}$

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

Затем разложим на множители следующий многочлен:

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

получение

${\displaystyle (-37+9x)(1+25x)}$

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

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

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

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

Смотрите также

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

Ссылки

1. Адольф Кунерт, "Sitzungsberichte. Academie Der Wissenschaften", том 78 (2), 1878, стр. 327-338 (для алгоритма квадратного уравнения), стр. 338–346 (для модульного квадратичного алгоритма), доступно в Библиотеке Эрнеста Майра, Гарвардский университет url="https://pdfhost.io/v/~OwxzpPNA_KUNERTH_1878" получено="09.09.2024"
2. Леонард Юджин Диксон, «История чисел», т. 2, стр. 382–384.

• Адольф Кунерт, "Sitzungsberichte. Academie Der Wissenschaften", том 75, II, 1877, стр. 7–58.
• Адольф Кунерт, "Sitzungsberichte. Academie Der Wissenschaften", том 82, II, 1880, стр. 342–375.