Алгоритм Тонелли – Шэнкса

Тонелли -Шенкса Алгоритм (называемый Шэнксом алгоритмом RESSOL) используется в модульной арифметике для решения r в конгруэнции формы r ² ≡ n (mod p ), где p — простое число : то есть найти квадратный корень из n по модулю p .

Тонелли-Шэнкса нельзя использовать для составных модулей: нахождение квадратных корней по модулю составных чисел является вычислительной проблемой, эквивалентной целочисленной факторизации .

Эквивалентная, но несколько более избыточная версия этого алгоритма была разработана Альберто Тонелли в 1891 году. Обсуждаемая здесь версия была независимо разработана Дэниелом Шэнксом в 1973 году, который объяснил:

Мое опоздание с изучением этих исторических ссылок было связано с тем, что я одолжил первый том « Диксона» Истории другу, и он так и не был возвращен.

По словам Диксона, Алгоритм Тонелли может извлекать квадратные корни из x по модулю простых степеней p. ^л кроме простых чисел.

Основные идеи

Учитывая ненулевое значение $n$ и простое $p>2$ (который всегда будет нечетным), критерий Эйлера говорит нам, что $n$ имеет квадратный корень (т. $n$ является квадратичным вычетом ) тогда и только тогда, когда:

$n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}$.

Напротив, если число $z$ не имеет квадратного корня (является невычетом), критерий Эйлера говорит нам, что:

$z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$.

найти такой не сложно $z$, поскольку половина целых чисел от 1 до $p-1$ иметь это свойство. Итак, мы предполагаем, что у нас есть доступ к такому неостатку.

Путем (обычного) многократного деления на 2 мы можем написать $p-1$ как $Q2^{S}$, где $Q$ странно. Обратите внимание: если мы попробуем

$R\equiv n^{\frac {Q+1}{2}}{\pmod {p}}$,

затем $R^{2}\equiv n^{Q+1}=(n)(n^{Q}){\pmod {p}}$. Если $t\equiv n^{Q}\equiv 1{\pmod {p}}$, затем $R$ является квадратным корнем из $n$. В противном случае для $M=S$, у нас есть $R$ и $t$ удовлетворительно:

• $R^{2}\equiv nt{\pmod {p}}$; и
• $t$ это $2^{M-1}$корень -й степени из 1 (поскольку $t^{2^{M-1}}=t^{2^{S-1}}\equiv n^{Q2^{S-1}}=n^{\frac {p-1}{2}}$).

Если при наличии выбора $R$ и $t$ для конкретного $M$ удовлетворяющие вышеизложенному (где $R$ не является квадратным корнем из $n$), мы можем легко вычислить другое $R$ и $t$ для $M-1$ такие, что выполняются приведенные выше соотношения, то мы можем повторять это до тех пор, пока $t$ становится $2^{0}$корень -й степени из 1, т.е. $t=1$. В этот момент $R$ является квадратным корнем из $n$.

Мы можем проверить, является ли $t$ это $2^{M-2}$корень -й степени из 1, возведя его в квадрат $M-2$ раз и проверяем, равен ли он 1. Если да, то ничего делать не нужно, так как тот же выбор $R$ и $t$ работает. Но если это не так, $t^{2^{M-2}}$ должно быть -1 (поскольку при возведении в квадрат получается 1, а из 1 могут быть только два квадратных корня 1 и -1 по модулю $p$).

Чтобы найти новую пару $R$ и $t$, мы можем умножить $R$ по фактору $b$, предстоит определить. Затем $t$ необходимо умножить на коэффициент $b^{2}$ держать $R^{2}\equiv nt{\pmod {p}}$. Итак, когда $t^{2^{M-2}}$ равно -1, нам нужно найти коэффициент $b^{2}$ так что $tb^{2}$ это $2^{M-2}$-й корень из 1 или эквивалентно $b^{2}$ это $2^{M-2}$корень -й степени из -1.

Хитрость здесь в том, чтобы использовать $z$, известный неостаток. Критерий Эйлера применяется к $z$ показано выше говорит, что $z^{Q}$ это $2^{S-1}$корень -й степени из -1. Итак, возведя в квадрат $z^{Q}$ неоднократно, у нас есть доступ к последовательности $2^{i}$корень -й степени из -1. Мы можем выбрать тот, который будет служить в качестве $b$. После небольшого обслуживания переменных и тривиального сжатия регистров приведенный ниже алгоритм возникает естественным образом.

Алгоритм

Операции и сравнения над элементами мультипликативной группы целых чисел по модулю p $\mathbb {Z} /p\mathbb {Z}$ неявно являются mod p .

Входы :

• п , простое число
• n , элемент $\mathbb {Z} /p\mathbb {Z}$ такие, что решения сравнения r ² = n существует; в этом случае мы говорим, что n — квадратичный вычет по модулю p .

Выходы :

• захожу ​ $\mathbb {Z} /p\mathbb {Z}$ такой, что р ² = п

Алгоритм :

1. Вынося степени двойки, найдите Q и S такие, что $p-1=Q2^{S}$ с Q нечетным
2. Найдите букву Z в $\mathbb {Z} /p\mathbb {Z}$ который является квадратичным невычетом
   • Половина элементов набора будут квадратичными невычетами.
   • Кандидатов можно проверить с помощью критерия Эйлера или путем нахождения символа Якоби.
3. Позволять

   ${\begin{aligned}M&\leftarrow S\\c&\leftarrow z^{Q}\\t&\leftarrow n^{Q}\\R&\leftarrow n^{\frac {Q+1}{2}}\end{aligned}}$

4. Петля:
   • Если t = 0, верните r = 0
   • Если t = 1, верните r = R
   • В противном случае используйте повторное возведение в квадрат, чтобы найти наименьшее i , 0 < i < M , такое, что $t^{2^{i}}=1$
   • Позволять $b\leftarrow c^{2^{M-i-1}}$, и установите

     ${\begin{aligned}M&\leftarrow i\\c&\leftarrow b^{2}\\t&\leftarrow tb^{2}\\R&\leftarrow Rb\end{aligned}}$

После того, как вы решили сравнение с r, второе решение будет $-r{\pmod {p}}$. По крайней мере, я такой, что $t^{2^{i}}=1$ есть M , то решения сравнения не существует, т. е. n не является квадратичным вычетом.

Это наиболее полезно, когда p ≡ 1 (mod 4).

Для таких простых чисел, что p ≡ 3 (mod 4), эта проблема имеет возможные решения. $r=\pm n^{\frac {p+1}{4}}{\pmod {p}}$. Если они удовлетворяют $r^{2}\equiv n{\pmod {p}}$, это единственные решения. Если не, $r^{2}\equiv -n{\pmod {p}}$, n — квадратичный невычет, решений нет.

Доказательство

Мы можем показать, что в начале каждой итерации цикла выполняются следующие инварианты цикла :

• $c^{2^{M-1}}=-1$
• $t^{2^{M-1}}=1$
• $R^{2}=tn$

Изначально:

• $c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ (поскольку z является квадратичным невычетом по критерию Эйлера)
• $t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ (поскольку n — квадратичный вычет)
• $R^{2}=n^{Q+1}=tn$

На каждой итерации с M' , c' , t' , R' новые значения заменяют M , c , t , R :

• $c'^{2^{M'-1}}=(b^{2})^{2^{i-1}}=c^{2^{M-i}2^{i-1}}=c^{2^{M-1}}=-1$
• $t'^{2^{M'-1}}=(tb^{2})^{2^{i-1}}=t^{2^{i-1}}b^{2^{i}}=-1\cdot -1=1$
  • $t^{2^{i-1}}=-1$ поскольку у нас это есть $t^{2^{i}}=1$ но $t^{2^{i-1}}\neq 1$ ( i — наименьшее значение такое, что $t^{2^{i}}=1$)
  • $b^{2^{i}}=c^{2^{M-i-1}2^{i}}=c^{2^{M-1}}=-1$
• $R'^{2}=R^{2}b^{2}=tnb^{2}=t'n$

От $t^{2^{M-1}}=1$ и проверку на t = 1 в начале цикла, мы видим, что мы всегда найдем i в 0 < i < M такое, что $t^{2^{i}}=1$. M строго меньше на каждой итерации, поэтому алгоритм гарантированно остановится. Когда мы достигаем условия t = 1 и останавливаемся, последний инвариант цикла подразумевает, что R ² = п .

Порядок т

Мы можем альтернативно выразить инварианты цикла, используя порядок элементов:

• $\operatorname {ord} (c)=2^{M}$
• $\operatorname {ord} (t)|2^{M-1}$
• $R^{2}=tn$ как и раньше

Каждый шаг алгоритма перемещает t в меньшую подгруппу, измеряя точный порядок t и умножая его на элемент того же порядка.

Пример

Решение сравнения r ² ≡ 5 (по модулю 41). 41 является простым, как и требовалось, и 41 ≡ 1 (по модулю 4). 5 является квадратичным вычетом по критерию Эйлера: $5^{\frac {41-1}{2}}=5^{20}=1$ (как и раньше, операции в $(\mathbb {Z} /41\mathbb {Z} )^{\times }$ неявно являются mod 41).

1. $p-1=40=5\cdot 2^{3}$ так $Q\leftarrow 5$, $S\leftarrow 3$
2. Найдите значение z:
   • $2^{\frac {41-1}{2}}=1$, поэтому 2 является квадратичным вычетом по критерию Эйлера.
   • $3^{\frac {41-1}{2}}=40=-1$, поэтому 3 — квадратичный невычет: установите $z\leftarrow 3$
3. Набор
   • $M\leftarrow S=3$
   • $c\leftarrow z^{Q}=3^{5}=38$
   • $t\leftarrow n^{Q}=5^{5}=9$
   • $R\leftarrow n^{\frac {Q+1}{2}}=5^{\frac {5+1}{2}}=2$
4. Петля:
   • Первая итерация:
     • $t\neq 1$, так что мы еще не закончили
     • $t^{2^{1}}=40$, $t^{2^{2}}=1$ так $i\leftarrow 2$
     • $b\leftarrow c^{2^{M-i-1}}=38^{2^{3-2-1}}=38$
     • $M\leftarrow i=2$
     • $c\leftarrow b^{2}=38^{2}=9$
     • $t\leftarrow tb^{2}=9\cdot 9=40$
     • $R\leftarrow Rb=2\cdot 38=35$
   • Вторая итерация:
     • $t\neq 1$, так что мы еще не закончили
     • $t^{2^{1}}=1$ так $i\leftarrow 1$
     • $b\leftarrow c^{2^{M-i-1}}=9^{2^{2-1-1}}=9$
     • $M\leftarrow i=1$
     • $c\leftarrow b^{2}=9^{2}=40$
     • $t\leftarrow tb^{2}=40\cdot 40=1$
     • $R\leftarrow Rb=35\cdot 9=28$
   • Третья итерация:
     • $t=1$, и мы закончили; возвращаться $r=R=28$

Действительно, 28 ² ≡ 5 (по модулю 41) и (−28) ² ≡ 13 ² ≡ 5 (по модулю 41). Таким образом, алгоритм дает два решения нашего сравнения.

Скорость алгоритма

Алгоритм Тонелли – Шэнкса требует (в среднем по всем возможным входным данным (квадратичные остатки и квадратичные невычеты))

$2m+2k+{\frac {S(S-1)}{4}}+{\frac {1}{2^{S-1}}}-9$

модульные умножения, где $m$ количество цифр в двоичном представлении $p$ и $k$ количество единиц в двоичном представлении $p$. Если искомый квадратичный невычет $z$ можно найти, проверив, является ли случайно выбранное число $y$ является квадратичным невычетом, для него требуется (в среднем) $2$ вычисления символа Лежандра . Среднее значение двух вычислений символа Лежандра объясняется следующим образом: $y$ является квадратичным вычетом со случайностью ${\tfrac {\tfrac {p+1}{2}}{p}}={\tfrac {1+{\tfrac {1}{p}}}{2}}$, что меньше, чем $1$ но $\geq {\tfrac {1}{2}}$, поэтому нам в среднем нужно будет проверить, есть ли $y$ является квадратичным вычетом два раза.

По сути, это показывает, что алгоритм Тонелли – Шэнкса работает очень хорошо, если модуль $p$ является случайным, то есть если $S$ не особенно велик по отношению к количеству цифр в двоичном представлении $p$. Как написано выше, алгоритм Чиполлы работает лучше, чем алгоритм Тонелли-Шэнкса, если (и только если) $S(S-1)>8m+20$. Однако если вместо этого использовать алгоритм Сазерленда для выполнения вычисления дискретного логарифма в 2-силовской подгруппе $\mathbb {F} _{p}^{\ast }$, можно заменить $S(S-1)$ с выражением, которое асимптотически ограничено $O(S\log S/\log \log S)$. Явно вычисляется $e$ такой, что $c^{e}\equiv n^{Q}$ а потом $R\equiv c^{-e/2}n^{(Q+1)/2}$ удовлетворяет $R^{2}\equiv n$ (Обратите внимание, что $e$ кратно 2, потому что $n$ является квадратичным вычетом).

Алгоритм требует от нас найти квадратичный невычет $z$. Не существует известного детерминированного алгоритма, работающего за полиномиальное время для поиска такого значения. $z$. Однако если обобщенная гипотеза Римана верна, существует квадратичный невычет $z<2\ln ^{2}{p}$, что дает возможность проверить каждый $z$ до этого предела и найти подходящее $z$ за полиномиальное время . Однако имейте в виду, что это наихудший сценарий; в общем, $z$ как указано выше, обнаруживается в среднем в двух исследованиях.

Использование

Алгоритм Тонелли-Шэнкса можно (естественно) использовать для любого процесса, в котором необходимы квадратные корни по простому модулю. Например, его можно использовать для поиска точек на эллиптических кривых . Это также полезно для вычислений в криптосистеме Рабина и на этапе просеивания квадратичного сита .

Обобщения

Тонелли – Шэнкса можно обобщить на любую циклическую группу (вместо $(\mathbb {Z} /p\mathbb {Z} )^{\times }$) и к корням k -й степени для произвольного целого числа k , в частности к извлечению корня k- й степени из элемента конечного поля .

Если в одной и той же циклической группе необходимо получить много квадратных корней и S не слишком велико, можно заранее подготовить таблицу квадратных корней из элементов 2-степенного порядка, а алгоритм упростить и ускорить следующим образом.

1. Вынесите степени 2 из p - 1, определив Q и S как: $p-1=Q2^{S}$ с Q нечетным.
2. Позволять $R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n$
3. Находить $b$ из таблицы так, что $b^{2}\equiv t$ и установить $R\equiv R/b$
4. вернуть Р. ​

Алгоритм Тонелли будет работать с mod p^k.

Согласно «Теории чисел» Диксона.

А. Тонелли дал явную формулу для корней $x^{2}=c{\pmod {p^{\lambda }}}$

В справочнике Диксона показана следующая формула для квадратного корня из $x^{2}{\bmod {p^{\lambda }}}$.

когда $p=4\cdot 7+1$, или $s=2$ (s должно быть 2 для этого уравнения) и $A=7$ такой, что $29=2^{2}\cdot 7+1$

для $x^{2}{\bmod {p^{\lambda }}}\equiv c$ затем

$x{\bmod {p^{\lambda }}}\equiv \pm (c^{A}+3)^{\beta }\cdot c^{(\beta +1)/2}$ где $\beta \equiv a\cdot p^{\lambda -1}$

отмечая, что $23^{2}{\bmod {29^{3}}}\equiv 529$ и отмечая, что $\beta =7\cdot 29^{2}$ затем

$(529^{7}+3)^{7\cdot 29^{2}}\cdot 529^{(7\cdot 29^{2}+1)/2}{\bmod {29^{3}}}\equiv 24366\equiv -23$

Возьмем другой пример: $2333^{2}{\bmod {29^{3}}}\equiv 4142$ и

$(4142^{7}+3)^{7\cdot 29^{2}}\cdot 4142^{(7\cdot 29^{2}+1)/2}{\bmod {29^{3}}}\equiv 2333$

Диксон также приписывает Тонелли следующее уравнение:

$X{\bmod {p^{\lambda }}}\equiv x^{p^{\lambda -1}}\cdot c^{(p^{\lambda }-2p^{\lambda -1}+1)/2}$ где $X^{2}{\bmod {p^{\lambda }}}\equiv c$ и $x^{2}{\bmod {p}}\equiv c$;

С использованием $p=23$ и используя модуль $p^{3}$ математика следующая:

$1115^{2}{\bmod {23^{3}}}=2191$

Сначала найдите модульный мод квадратного корня $p$ что можно сделать с помощью обычного алгоритма Тонелли:

$1115^{2}{\bmod {23}}\equiv 6$ и таким образом ${\sqrt {6}}{\bmod {23}}\equiv 11$

И применяя уравнение Тонелли (см. выше):

$11^{23^{2}}\cdot 2191^{(23^{3}-2\cdot 23^{2}+1)/2}{\bmod {23^{3}}}\equiv 1115$

Справка Диксона ясно показывает, что алгоритм Тонелли работает с модулями $p^{\lambda }$.

Ссылки

• Иван Нивен; Герберт С. Цукерман; Хью Л. Монтгомери (1991). Введение в теорию чисел (5-е изд.). Уайли. стр. 110–115 . ISBN  0-471-62546-9 .
• Дэниел Шэнкс. Пять теоретико-числовых алгоритмов. Материалы второй Манитобской конференции по вычислительной математике. Стр. 51–70. 1973.
• Альберто Тонелли, Замечания о разрешении квадратичных сравнений. Новости Королевского общества наук и Гёттингенского университета имени Георга Августа. стр. 344–346. 1891. [1]
• Гаган Тара Нанда - Математика 115: Алгоритм RESSOL [2]
• Гонсало Торнария [3]