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

Алгоритм Тонелли — Шенкса (названный Шенксом 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) — числоцифр в двоичном представлении p и k — число единиц в двоичномпредставлении p. Если требуемый квадратичный невычет z будетвычисляться проверкой случайно выбранного y на то, является ли оноквадратичным невычетом, то в среднем это требует вычисления двухсимволов Лежандра. Два как среднее число вычисляемых символов Лежандраобъясняется следующим: вероятность того, что y является квадратичнымвычетом, равнаp+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.