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

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

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

Алгоритм


Вход:

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

Выход:

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

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

Пример


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

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

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

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

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

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

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

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


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

=(x1x2+y1y2(a2n))+(x1y2+y1x2)ω
. Теперь нужно проверить свойства поля. Замкнутость по операциям сложения и умножения, ассоциативность, коммутативность и дистрибутивность легко проверить, поскольку поле Fp2 похоже на поле комплексных чисел (где ω служит аналогом i).\\Нейтральным элементом по сложению служит 0 или, более формально, 0+0ω — если αFp2, то
α+0=(x+yω)+(0+0ω)=(x+0)+(y+0)ω=x+yω=α
. Нейтральным элементом по умножению служит 1, точнее 1+0ω:
α1=(x+yω)(1+0ω)=(x1+0y(a2n))+(x0+1y)ω=x+yω=α
. Осталось проверить только, что в Fp2 существуют обратные элементы по сложению и умножению. Легко видеть, что обратным элементом по сложению числа x+yω является число xyω, которое также содержится в поле Fp2, поскольку x,yFp. Чтобы показать, что любой ненулевой элемент α имеет обратный по умножению элемент, выпишем представления α=x1+y1ω и α1=x2+y2ω. Другими словами,
(x1+y1ω)(x2+y2ω)=(x1x2+y1y2(n2a))+(x1y2+y1x2)ω=1
. Получаем два уравнения, x1x2+y1y2(n2a)=1 и x1y2+y1x2=0. Решаем эту систему относительно x2 и y2, получим
x2=y11x1(y1(n2a)x12y11)1
,
y2=(y1(n2a)x12y11)1
. Обратные элементы в выражениях для x2 и y2 существуют, поскольку они являются элементами поля Fp. Тем самым мы завершаем первую часть доказательства.
 Во второй части доказательства покажем, что для любого элемента x+yωFp2:(x+yω)p=xyω. По определению ω2=a2n не является квадратом в Fp. Тогда критерий Эйлера даёт
ωp1=(ω2)p12=1
. Таким образом, ωp=ω. Это, вместе с малой теоремой Ферма (утверждающей, что xp=x для всех xFp) и знанием, что в полях характеристикой выполняется равенство (a+b)p=ap+bp, показывает желаемый результат
(x+yω)p=xp+ypωp=xyω
.
 Третья и последняя часть доказательства показывает, что в случае x0=(a+ω)p+12Fp2 выполняется x02=nFp.\\Вычисляем
x02=(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 .