Processing math: 100%

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

Алгоритм Чиполлы — это техника решения конгруэнтногоуравнения вида
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)x21y11)1,
y2=(y1(n2a)x21y11)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выполняется x20=nFp.\\Вычисляем
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 .