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

Алгоритм Тонелли — Шенкса (названный Шенксом RESSOL алгоритмом) относится к модулярной арифметике и используется для решения сравнения

x2n(modp),x2n(modp),
  где nn — квадратичный вычет по модулю pp, а pp — нечётное простое число.
 Алгоритм Тонелли — Шенкса не может быть использован для составных модулей; поиск квадратных корней по составному модулю вычислительно эквивалентен факторизации.
 Эквивалентная, но немного более усложнённая версия этого алгоритма была разработана Альберто Тонелли в 1891 году. Версия алгоритма, обсуждаемая здесь, была разработана независимо Дэниелом Шенксом в 1973 году.

Алгоритм


Входные данные: pp — нечётное простое число, nn - целое число, являющееся квадратичным вычетом по модулю pp, другими словами, (np)=1(np)=1, где (ab)(ab) — символ Лежандра.
Результат работы алгоритма: вычет RR, удовлетворяющий сравнению R2n(modp)R2n(modp).

  1. Выделим степени двойки из p1p1, то есть пусть p1=2SQp1=2SQ, где QQ нечётно, S1S1. Заметим, что если S=1S=1, то есть p3(mod4)p3(mod4), тогда решение определяется формулой R±np+14R±np+14. Далее S2S2.
  2. Выберем произвольный квадратичный невычет zz, то есть символ Лежандра (zp)=1(zp)=1, положим czQ(modp)czQ(modp).
  3. Пусть также RnQ+12(modp),tnQ(modp),M=S.RnQ+12(modp),tnQ(modp),M=S.
  4. Выполняем цикл:
    1. Если t1(modp)t1(modp), то алгоритм возвращает RR.
    2. В противном случае в цикле находим наименьшее ii, 0<i<M0<i<M, такое, что t2i1(modp)t2i1(modp) с помощью итерирования возведения в квадрат.
    3. Пусть bc2(Mi1)(modp)bc2(Mi1)(modp), и положим R:≡Rb(modp),t:≡tb2(modp),c:≡b2(modp)R:Rb(modp),t:tb2(modp),c:b2(modp) and M:=iM:=i, возвращаемся к началу цикла.

 После нахождения решения сравнения RR второе решение сравнения находится как pRpR.

Пример


 Решим сравнение x210(mod13)x210(mod13). p=13p=13 — нечётно, и поскольку 101312=1061(mod13)101312=1061(mod13), 10 является квадратичным вычетом по критерию Эйлера.

  • Шаг 1: p1=12=322p1=12=322 поэтому Q=3Q=3, S=2S=2.
  • Шаг 2: Возьмем z=2z=2 — квадратичный невычет (потому что 21312=1(mod13)21312=1(mod13) (снова по критерию Эйлера)). Положим c=238(mod13).c=238(mod13).
  • Шаг 3: R=1024,t1031(mod13),M=2.R=1024,t1031(mod13),M=2.
  • Шаг 4: Начинаем цикл: t1(mod13)t≢1(mod13), так что 0<i<20<i<2, проще говоря i=1i=1.
    • Пусть b822118(mod13)b822118(mod13), тогда b2821(mod13)b2821(mod13).
    • Положим R=487(mod13)R=487(mod13), t111(mod13)t111(mod13), и M=1M=1.
    • Перезапустим цикл, поскольку t1(mod13)t1(mod13) цикл завершен, мы получим R7(mod13).R7(mod13).

 Поскольку 72=4910(mod13)72=4910(mod13), очевидно (±7)26210(mod13)(±7)26210(mod13), отсюда получаем 2 решения сравнения.

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


 Пусть p1=2SQp1=2SQ. Пусть теперь rnQ+12(modp)rnQ+12(modp) и tnQ(modp)tnQ(modp), заметим, что r2nt(modp)r2nt(modp). Последнее сравнение остается истинным после каждой итериации основного цикла алгоритма. Если в какой-то момент t1(modp)t1(modp), то r2n(modp)r2n(modp) и алгоритм завершается с R±r(modp)R±r(modp).
 Если t1(modp)t≢1(modp), то рассмотрим квадратичный невычет zz по модулю pp. Пусть czQ(modp)czQ(modp), тогда c2S(zQ)2Szp11(modp)c2S(zQ)2Szp11(modp) и c2S1zp12(zp)1(modp)c2S1zp12(zp)1(modp), которое показывает, что порядок cc равен 2S2S.
 Сходным образом мы получим, что t2S1(modp)t2S1(modp), поэтому порядок tt делит 2S2S, значит порядок tt равен 2S2S. Так как nn — квадрат по модулю pp, то tnQ(modp)tnQ(modp) тоже квадрат, и значит, $S' Положим, что bc2SS1(modp)bc2SS1(modp) и rbr(modp)rbr(modp), cb2(modp)cb2(modp) и tct(modp)tct(modp). Как и раньше, r2nt(modp)r2nt(modp) сохраняется; однако в этой конструкции как tt, так и cc имеют порядок 2S2S. Отсюда следует, что tt имеет порядок 2S2S′′, где S<SS′′<S.
 Если S=0S′′=0, то t1(modp)t1(modp), и алгоритм останавливается, возвращая R±r(modp)R±r(modp). Иначе мы перезапускаем цикл с аналогичными определениями b,r,c,tb,r′′,c′′,t′′, пока не получим S(j)S(j), который равен 0. Поскольку последовательность натуральных S(j)S(j) строго убывает, то алгоритм завершается.

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


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

2m+2k+S(S1)4+12S19=O(S2)=O(ln2p)2m+2k+S(S1)4+12S19=O(S2)=O(ln2p)
  умножений по модулю, где m=log2p=O(lnp)m=log2p=O(lnp) — число цифр в двоичном представлении pp и kk — число единиц в двоичном представлении pp. Если требуемый квадратичный невычет zz будет вычисляться проверкой случайно выбранного yy на то, является ли оно квадратичным невычетом, то в среднем это требует вычисления двух символов Лежандра. Два как среднее число вычисляемых символов Лежандра объясняется следующим: вероятность того, что yy является квадратичным вычетом, равна p+12p=12+12p>12p+12p=12+12p>12 — вероятность больше половины, поэтому в среднем понадобится около двух проверок, является ли y квадратичным вычетом.
 Это показывает, что практически алгоритм Тонелли — Шенкса будет работать очень хорошо, если модуль p случаен, то есть когда S не особенно велико относительно количества цифр в двоичном представлении p. Алгоритм Чиполлы работает лучше, чем алгоритм Тонелли — Шенкса, если и только если S(S1)>8m+20. Однако если вместо этого использовать алгоритм Сазерленда для выполнения дискретного логарифмирования в 2-Силовской подгруппе в Fp, это позволяет заменить S(S1) в выражении числа умножений на величину, асимптотически ограниченную O(SlnSlnlnS). Действительно, достаточно найти одно e такое, что cenQ и тогда Rce/2n(Q+1)/2 удовлетворяет R2n (заметим, что e кратно 2, поскольку n — квадратичный вычет).
 Алгоритм требует нахождения квадратичного невычета z. На текущий момент неизвестен детерминированный алгоритм, который бы за полиномиальное время от длины p нашел бы такое z. Однако, если обобщенная гипотеза Римана верна, то существует квадратичный невычет z<2ln2p,, который легко найти проверяя z в указанных пределах за полиномиальное время. Это, конечно, оценка в худшем случае, поскольку, как показано было выше, достаточно проверить в среднем 2 случайных z для нахождения квадратичного невычета.

Применение


 Алгоритм Тонелли — Шенкса может быть использован для нахождения точек на эллиптической кривой над полем вычетов. Он также может быть использован для вычислений в криптосистеме Рабина.

Обобщение


 Алгоритм Тонелли — Шенкса может быть обобщён на любую циклическую группу (вместо F×p) и на нахождение корней k-й степени для произвольного натурального k, в частности, на вычисление корней k-й степени в конечном поле.
 Если надо вычислить много квадратных корней в одной и той же циклической группе и S не очень велико, для улучшения и упрощения алгоритма и увеличения его скорости может быть приготовлена таблица квадратных корней квадратов элементов следующим образом:

  1. Выделим степени двойки в p1: пусть Q,S такие, что p1=2SQ, Q нечётно.
  2. Пусть RnQ+12(modp),tnQR2/n(modp).
  3. Найдём корень b по таблице соотношений b2t и положим RR/b
  4. Вернуть R.