Русская Википедия:Алгоритм Чиполлы

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

<math>x^2\equiv n \pmod{p},</math>

где <math>x,n \in \mathbf{F}_{p}</math>, так что n будет квадратом числа x, и где <math>p</math> является нечётным простым числом. Здесь <math>\mathbf{F}_p</math> обозначает конечное поле с <math>p</math> элементами <math>\{0,1,\dots,p-1\}</math>. Алгоритм носит имя итальянского математика Шаблон:Не переведено 5, открывшего метод в 1907.

Алгоритм

Вход:

• <math>p</math>, нечётное простое число,
• <math>n \in \mathbf{F}_p</math>, квадрат числа.

Выход:

• число <math>x \in \mathbf{F}_p</math>, удовлетворяющее равенству <math> x^2= n . </math>

Шаг 1. Находим число <math>a \in \mathbf{F}_p</math>, такое, что <math>a^2 - n</math> не является квадратом. Алгоритм для поиска таких чисел <math>a</math> неизвестен, за исключением метода проб и ошибок. Просто выбираем какое-либо число <math>a</math> и вычисляем символ Лежандра <math>(a^2-n|p)</math>, чтобы удостовериться, что <math>a</math> удовлетворяет условию. Шанс, что случайное число <math>a</math> подходит, равен <math>(p-1)/2p</math>. Если <math>p</math> достаточно велико, эта величина примерно равна <math>1/2</math>Шаблон:Sfn. Таким образом, ожидаемое число попыток для получения подходящего a равно 2.

Шаг 2. Получаем x путём вычисления <math>x=\left( a + \sqrt{a^2-n} \right)^{(p+1)/2}</math> в поле <math>\mathbf{F}_{p^2} = \mathbf{F}_p(\sqrt{a^2-n})</math>. Это число x будет одним из корней уравнения <math> x^2 =n .</math>

Если <math>x^2 = n</math>, то <math>(-x)^2 = n</math> также выполняется. Поскольку p нечётно, <math> x \neq -x </math>, так что для найденного решения x всегда существует второе решение, равное -x.

Пример

(Замечание: Все элементы до второго шага принадлежат полю <math>\mathbf{F}_{13}</math>, а все элементы второго шага — полю <math>\mathbf{F}_{13^2}</math>). Ищем число x, такое, что <math>x^2 = 10.</math>

Прежде чем применять алгоритм, нужно проверить, что число <math>10</math> является на самом деле квадратом в поле <math>\mathbf{F}_{13}</math>, что означает, что символ Лежандра <math>(10 | 13)</math> должен быть равен 1. Проверить это можно с помощью критерия Эйлера: <math>(10 | 13) \equiv 10^6 \equiv 1 \bmod 13</math>. Это подтверждает, что 10 является квадратом и к нему можно применить алгоритм.

• Шаг 1: Находим число a, такое что <math>a^2 - n</math> не является квадратом. Как было указано выше, нужно использовать метод проб и ошибок. Выберем число <math>a=2</math>, для него <math>a^2 - n</math> буде равно 7. Символ Лежандра <math>(7 | 13)</math> равен -1, что можно опять получить с помощью критерия Эйлера, <math>7^6 = 343^2 \equiv 5^2 \equiv 25 \equiv -1 \bmod 13</math>. Таким образом, число <math>a=2</math> подходит.
• Шаг 2: Вычисляем <math>x = \left( a + \sqrt{a^2-n} \right)^{(p+1)/2} = \left( 2 + \sqrt{-6}\right)^7 .</math>

<math>\left(2+\sqrt{-6}\right)^2 = 4 + 4\sqrt{-6} - 6 = -2 + 4 \sqrt{-6} .</math>

<math>\left(2+\sqrt{-6}\right)^4 = \left(-2+4\sqrt{-6}\right)^2 = -1-3\sqrt{-6} .</math>

<math>\left(2+\sqrt{-6}\right)^6 = \left(-2 + 4\sqrt{-6}\right)\left(-1-3\sqrt{-6}\right) = 9+2\sqrt{-6} .</math>

<math>\left(2+\sqrt{-6}\right)^7 = \left(9+2\sqrt{-6}\right)\left(2+ \sqrt{-6}\right) = 6 .</math>

Таким образом, <math>x = 6 </math> является решением, как и <math>x = -6 \bmod 13 = (-6+13) \bmod 13 = 7.</math> Действительно, <math>\ 6^2 = 36 \bmod 13 = 10</math> и <math> 7^2 = 49 \bmod 13 = 10 .</math>

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

В первой части доказательства убедимся, что <math>\mathbf{F}_{p^2} = \mathbf{F}_p(\sqrt{a^2-n}) = \{x + y\sqrt{a^2-n} : x,y \in \mathbf{F}_p\}</math> действительно является полем. Для простоты выкладок введём число <math>\omega</math>, равное <math>\sqrt{a^2-n}</math>. Конечно, <math>a^2-n</math> не является квадратичным вычетом, так что квадратный корень не существует в <math>\mathbf{F}_p</math>. Это <math>\omega</math>, грубо говоря, можно рассматривать как аналог комплексного числа i. Арифметика поля вполне очевидна. Сложение определяется как

<math>\left(x_1 + y_1 \omega \right) + \left(x_2 + y_2 \omega \right) = \left(x_1 + x_2 \right) + \left(y_1 + y_2\right) \omega</math>.

Умножение также определяется обычным путём. Если помнить, что <math>\omega^2 = a^2-n</math>, получим

<math>\left(x_1 + y_1 \omega \right)\left(x_2 + y_2 \omega \right) = x_1 x_2 + x_1 y_2 \omega + y_1 x_2 \omega + y_1 y_2 \omega^2</math>

<math> = \left( x_1 x_2 + y_1 y_2 \left(a^2-n\right)\right) + \left(x_1 y_2 + y_1 x_2 \right) \omega</math>.

Теперь нужно проверить свойства поля. Замкнутость по операциям сложения и умножения, ассоциативность, коммутативность и дистрибутивность легко проверить, поскольку поле <math>\mathbf{F}_{p^2}</math> похоже на поле комплексных чисел (где <math>\omega</math> служит аналогом i).
Нейтральным элементом по сложению служит <math>0</math> или, более формально, <math>0 + 0\omega</math> — если <math>\alpha \in \mathbf{F}_{p^2}</math>, то

<math>\alpha + 0 = (x+y\omega) + (0 + 0\omega) = (x + 0) + (y + 0)\omega = x+y\omega = \alpha</math>.

Нейтральным элементом по умножению служит <math>1</math>, точнее <math> 1 + 0\omega</math>:

<math>\alpha \cdot 1 = (x+y\omega)(1 + 0\omega) = \left(x\cdot 1 + 0 \cdot y \left(a^2-n\right)\right) + (x\cdot 0 + 1 \cdot y)\omega = x+y\omega = \alpha</math>.

Осталось проверить только, что в <math>\mathbf{F}_{p^2}</math> существуют обратные элементы по сложению и умножению. Легко видеть, что обратным элементом по сложению числа <math>x+y\omega</math> является число <math>-x-y\omega</math>, которое также содержится в поле <math>\mathbf{F}_{p^2}</math>, поскольку <math>-x,-y \in \mathbf{F}_p</math>. Чтобы показать, что любой ненулевой элемент <math>\alpha</math> имеет обратный по умножению элемент, выпишем представления <math>\alpha = x_1 + y_1 \omega</math> и <math>\alpha^{-1} = x_2 + y_2 \omega</math>. Другими словами,

<math>(x_1 + y_1 \omega)(x_2 + y_2 \omega) = \left( x_1 x_2 + y_1 y_2 \left(n^2-a\right)\right) + \left(x_1 y_2 + y_1 x_2 \right) \omega = 1</math>.

Получаем два уравнения, <math>x_1x_2 + y_1y_2(n^2-a) = 1</math> и <math>x_1y_2 + y_1x_2 = 0</math>. Решаем эту систему относительно <math>x_2</math> и <math>y_2</math>, получим

<math>x_2 = -y_1^{-1}x_1\left(y_1\left(n^2-a\right)-x_1^2y_1^{-1}\right)^{-1}</math>,

<math>y_2 = \left( y_1 \left(n^2-a\right) - x_1^2y_1^{-1}\right)^{-1}</math>.

Обратные элементы в выражениях для <math>x_2</math> и <math>y_2</math> существуют, поскольку они являются элементами поля <math>\mathbf{F}_p</math>. Тем самым мы завершаем первую часть доказательства.

Во второй части доказательства покажем, что для любого элемента <math>x+y\omega \in \mathbf{F}_{p^2} : (x+y\omega)^p = x - y\omega</math>. По определению <math>\omega^2=a^2-n</math> не является квадратом в <math>\mathbf{F}_p</math>. Тогда критерий Эйлера даёт

<math>\omega^{p-1} = \left(\omega^2\right)^{\frac{p-1}{2}} = -1</math>.

Таким образом, <math>\omega^p = -\omega</math>. Это, вместе с малой теоремой Ферма (утверждающей, что <math>x^p = x</math> для всех <math>x \in \mathbf{F}_{p}</math>) и знанием, что в полях характеристикой выполняется равенство <math>\left(a+b\right)^p = a^p + b^p</math>, показывает желаемый результат

<math>(x+y\omega)^p = x^p + y^p \omega^p = x - y\omega</math>.

Третья и последняя часть доказательства показывает, что в случае <math>x_0=\left(a+\omega \right)^{\frac{p+1}{2}} \in \mathbf{F}_{p^2}</math> выполняется <math>x_0^2=n \in \mathbf{F}_p</math>.
Вычисляем

<math>x_0^2 = \left(a+\omega \right)^{p+1} = (a+\omega)(a+\omega)^{p}=(a+\omega)(a-\omega)=a^2 - \omega^2 = a^2 - \left(a^2 - n \right) = n</math>.

Заметим, что эти вычисления имеют место в <math>\mathbf{F}_{p^2}</math>, так что <math>x_0 \in \mathbf{F}_{p^2}</math>. Теорема Лагранжа утверждает, что ненулевой многочлен степени n имеет не более n корней над полем K. Если учесть, что многочлен <math>x^2-n</math> имеет 2 корня в <math>\mathbf{F}_p</math>, никаких других корней быть не может <math>\mathbf{F}_{p^2}</math>. Было показано, что <math>x_0</math> и <math>-x_0</math> являются корнями многочлена <math>x^2-n</math> в <math>\mathbf{F}_{p^2}</math>, так что должно выполняться <math>x_0, -x_0 \in \mathbf{F}_p</math>.

Скорость

После нахождения подходящего a число операций, требуемых алгоритмом, составляет <math>4m + 2k - 4</math> умножений и <math>4m-2</math> сложений, где m — число знаков в двоичном представлении числа p, а k — число число единиц в этом представлении. Чтобы найти a методом проб и ошибок, ожидаемое число вычислений символа Лежандра равно 2. Однако может посчастливиться с первого раза, но может потребоваться и более 2 попыток. В поле <math>\mathbf{F}_{p^2}</math> выполняются следующие два равенства

<math>(x+y\omega)^2 = \left(x^2 + y^2 \omega^2 \right) + \left(\left(x+y\right)^2-x^2-y^2\right)\omega,</math>

где <math>\omega^2 = a^2-n</math> заранее известно. Это вычисление требует 4 умножения и 4 сложения.

<math>\left(x+y\omega\right)^2\left(c + \omega \right) = \left( cd - b\left(x+d\right)\right) + \left(d^2 - by\right)\omega,</math>

где <math>d=(x+yc)</math> and <math>b=ny</math>. Эта операция требует 6 умножений и 4 сложения.

Если предположить, что <math>p \equiv 1 \pmod 4,</math> (в случае <math>p \equiv 3 \pmod 4</math>, прямое вычисление <math>x \equiv \pm n^{\frac{p+1}{4}}</math> много быстрее) двоичное выражение <math>(p+1)/2</math> имеет <math>m-1</math> знаков, из которых k равны единице. Таким образом, для вычисления <math>(p+1)/2</math>-ой степени числа <math>\left(a + \omega \right)</math> первую формулу нужно применить <math>n-k-1</math> раз, а вторую — <math>k-1</math> раз.

Алгоритм Чиполлы лучше, чем алгоритм Тонелли — Шенкса тогда и только тогда, когда <math>S(S-1) > 8m+20</math>, где <math>2^{S}</math> максимальная степень 2, на которую делится <math>p-1</math> .

Литература

• Шаблон:Книга

Ссылки

• E. Bach, J.O. Shallit Algorithmic Number Theory: Efficient algorithms MIT Press, (1996)