Алгоритм Чиполлы

Алгоритм Чиполлы — это техника решения конгруэнтного уравнения вида
x2n(modp),
x2n(modp),

 где x,nFpx,nFp, так что n будет квадратом числа x, и где pp является нечётным простым числом. Здесь FpFp обозначает конечное поле с pp элементами {0,1,,p1}{0,1,,p1}. Алгоритм носит имя итальянского математика , открывшего метод в 1907.

Алгоритм


Вход:

  • pp, нечётное простое число,
  • nFpnFp, квадрат числа.

Выход:

  • число xFpxFp, удовлетворяющее равенству x2=n.x2=n.

 Шаг 1. Находим число aFpaFp, такое, что a2na2n не является квадратом. Алгоритм для поиска таких чисел aa неизвестен, за исключением метода проб и ошибок. Просто выбираем какое-либо число aa и вычисляем символ Лежандра (a2n|p)(a2n|p), чтобы удостовериться, что aa удовлетворяет условию. Шанс, что случайное число aa подходит, равен (p1)/2p(p1)/2p. Если pp достаточно велико, эта величина примерно равна 1/21/2. Таким образом, ожидаемое число попыток для получения подходящего a равно 2.
 Шаг 2. Получаем x путём вычисления x=(a+a2n)(p+1)/2x=(a+a2n)(p+1)/2 в поле Fp2=Fp(a2n)Fp2=Fp(a2n). Это число x будет одним из корней уравнения x2=n.x2=n.
 Если x2=nx2=n, то (x)2=n(x)2=n также выполняется. Поскольку p нечётно, xxxx, так что для найденного решения x всегда существует второе решение, равное -x.

Пример


 (Замечание: Все элементы до второго шага принадлежат полю F13F13, а все элементы второго шага — полю F132F132). Ищем число x, такое, что x2=10.x2=10.
 Прежде чем применять алгоритм, нужно проверить, что число 1010 является на самом деле квадратом в поле F13F13, что означает, что символ Лежандра (10|13)(10|13) должен быть равен 1. Проверить это можно с помощью критерия Эйлера: (10|13)1061mod13(10|13)1061mod13. Это подтверждает, что 10 является квадратом и к нему можно применить алгоритм.

  • Шаг 1: Находим число a, такое что a2na2n не является квадратом. Как было указано выше, нужно использовать метод проб и ошибок. Выберем число a=2a=2, для него a2na2n буде равно 7. Символ Лежандра (7|13)(7|13) равен -1, что можно опять получить с помощью критерия Эйлера, 76=343252251mod1376=343252251mod13. Таким образом, число a=2a=2 подходит.
  • Шаг 2: Вычисляем x=(a+a2n)(p+1)/2=(2+6)7.x=(a+a2n)(p+1)/2=(2+6)7.

(2+6)2=4+466=2+46.
(2+6)2=4+466=2+46.

(2+6)4=(2+46)2=136.
(2+6)4=(2+46)2=136.

(2+6)6=(2+46)(136)=9+26.
(2+6)6=(2+46)(136)=9+26.

(2+6)7=(9+26)(2+6)=6.
(2+6)7=(9+26)(2+6)=6.

 Таким образом, x=6x=6 является решением, как и x=6mod13=(6+13)mod13=7.x=6mod13=(6+13)mod13=7. Действительно,  62=36mod13=10 62=36mod13=10 и 72=49mod13=10.72=49mod13=10.

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


 В первой части доказательства убедимся, что Fp2=Fp(a2n)={x+ya2n:x,yFp}Fp2=Fp(a2n)={x+ya2n:x,yFp} действительно является полем. Для простоты выкладок введём число ωω, равное a2na2n. Конечно, a2na2n не является квадратичным вычетом, так что квадратный корень не существует в FpFp. Это ωω, грубо говоря, можно рассматривать как аналог комплексного числа i. Арифметика поля вполне очевидна. Сложение определяется как
(x1+y1ω)+(x2+y2ω)=(x1+x2)+(y1+y2)ω
(x1+y1ω)+(x2+y2ω)=(x1+x2)+(y1+y2)ω
. Умножение также определяется обычным путём. Если помнить, что ω2=a2nω2=a2n, получим
(x1+y1ω)(x2+y2ω)=x1x2+x1y2ω+y1x2ω+y1y2ω2
(x1+y1ω)(x2+y2ω)=x1x2+x1y2ω+y1x2ω+y1y2ω2

=(x1x2+y1y2(a2n))+(x1y2+y1x2)ω
=(x1x2+y1y2(a2n))+(x1y2+y1x2)ω
. Теперь нужно проверить свойства поля. Замкнутость по операциям сложения и умножения, ассоциативность, коммутативность и дистрибутивность легко проверить, поскольку поле Fp2Fp2 похоже на поле комплексных чисел (где ωω служит аналогом i).\\Нейтральным элементом по сложению служит 00 или, более формально, 0+0ω0+0ω — если αFp2αFp2, то
α+0=(x+yω)+(0+0ω)=(x+0)+(y+0)ω=x+yω=α
α+0=(x+yω)+(0+0ω)=(x+0)+(y+0)ω=x+yω=α
. Нейтральным элементом по умножению служит 11, точнее 1+0ω1+0ω:
α1=(x+yω)(1+0ω)=(x1+0y(a2n))+(x0+1y)ω=x+yω=α
α1=(x+yω)(1+0ω)=(x1+0y(a2n))+(x0+1y)ω=x+yω=α
. Осталось проверить только, что в Fp2Fp2 существуют обратные элементы по сложению и умножению. Легко видеть, что обратным элементом по сложению числа x+yωx+yω является число xyωxyω, которое также содержится в поле Fp2Fp2, поскольку x,yFpx,yFp. Чтобы показать, что любой ненулевой элемент αα имеет обратный по умножению элемент, выпишем представления α=x1+y1ωα=x1+y1ω и α1=x2+y2ωα1=x2+y2ω. Другими словами,
(x1+y1ω)(x2+y2ω)=(x1x2+y1y2(n2a))+(x1y2+y1x2)ω=1
(x1+y1ω)(x2+y2ω)=(x1x2+y1y2(n2a))+(x1y2+y1x2)ω=1
. Получаем два уравнения, x1x2+y1y2(n2a)=1x1x2+y1y2(n2a)=1 и x1y2+y1x2=0x1y2+y1x2=0. Решаем эту систему относительно x2x2 и y2y2, получим
x2=y11x1(y1(n2a)x21y11)1
x2=y11x1(y1(n2a)x21y11)1
,
y2=(y1(n2a)x21y11)1
y2=(y1(n2a)x21y11)1
. Обратные элементы в выражениях для x2x2 и y2y2 существуют, поскольку они являются элементами поля FpFp. Тем самым мы завершаем первую часть доказательства.
 Во второй части доказательства покажем, что для любого элемента x+yωFp2:(x+yω)p=xyωx+yωFp2:(x+yω)p=xyω. По определению ω2=a2nω2=a2n не является квадратом в FpFp. Тогда критерий Эйлера даёт
ωp1=(ω2)p12=1
ωp1=(ω2)p12=1
. Таким образом, ωp=ωωp=ω. Это, вместе с малой теоремой Ферма (утверждающей, что xp=xxp=x для всех xFpxFp) и знанием, что в полях характеристикой выполняется равенство (a+b)p=ap+bp(a+b)p=ap+bp, показывает желаемый результат
(x+yω)p=xp+ypωp=xyω
(x+yω)p=xp+ypωp=xyω
.
 Третья и последняя часть доказательства показывает, что в случае x0=(a+ω)p+12Fp2x0=(a+ω)p+12Fp2 выполняется x20=nFpx20=nFp.\\Вычисляем
x20=(a+ω)p+1=(a+ω)(a+ω)p=(a+ω)(aω)=a2ω2=a2(a2n)=n
x20=(a+ω)p+1=(a+ω)(a+ω)p=(a+ω)(aω)=a2ω2=a2(a2n)=n
. Заметим, что эти вычисления имеют место в Fp2, так что x0Fp2. утверждает, что ненулевой многочлен степени n имеет не более n корней над полем K. Если учесть, что многочлен x2n имеет 2 корня в Fp, никаких других корней быть не может Fp2. Было показано, что x0 и x0 являются корнями многочлена x2n в Fp2, так что должно выполняться x0,x0Fp.

Скорость


 После нахождения подходящего a число операций, требуемых алгоритмом, составляет 4m+2k4 умножений и 4m2 сложений, где m — число знаков в двоичном представлении числа p, а k — число число единиц в этом представлении. Чтобы найти a методом проб и ошибок, ожидаемое число вычислений символа Лежандра равно 2. Однако может посчастливиться с первого раза, но может потребоваться и более 2 попыток. В поле Fp2 выполняются следующие два равенства
(x+yω)2=(x2+y2ω2)+((x+y)2x2y2)ω,
где ω2=a2n заранее известно. Это вычисление требует 4 умножения и 4 сложения.
(x+yω)2(c+ω)=(cdb(x+d))+(d2by)ω,
где d=(x+yc) and b=ny. Эта операция требует 6 умножений и 4 сложения.
 Если предположить, что p1(mod4), (в случае p3(mod4), прямое вычисление x±np+14 много быстрее) двоичное выражение (p+1)/2 имеет m1 знаков, из которых k равны единице. Таким образом, для вычисления (p+1)/2-ой степени числа (a+ω) первую формулу нужно применить nk1 раз, а вторую — k1 раз.
 Алгорим Чиполлы лучше, чем Алгоритм Гельфонда — Шенкса тогда и только тогда, когда S(S1)>8m+20, где 2S максимальная степень 2, на которую делится p1 .