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

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Алгоритм Шуфа — эффективный алгоритм подсчёта числа точек на эллиптической кривой над конечным полем. Алгоритм имеет приложения в эллиптической криптографии, где важно знать число точек, чтобы судить о трудности решения задачи дискретного логарифмирования на группе точек на эллиптической кривой.

Алгоритм опубликовал в 1985 Шаблон:Не переведено 5 и это был теоретический прорыв, поскольку это был первый детерминированный алгоритм полиномиального времени для Шаблон:Не переведено 5. До алгоритма Шуфа подходы к подсчёту точек на эллиптических кривых, каким был бесхитростный алгоритм малых и больших шагов, были по большей части трудоёмкими и требовали экспоненционального времени работы.

Данная статья объясняет подход Шуфа, делая упор на математические идеи, лежащие в основе алгоритма.

Введение

Пусть <math>E</math> — эллиптическая кривая, определённая над конечным полем <math>\mathbb{F}_{q}</math>, где <math>q=p^n</math> для простого <math>p</math> и целого <math>n \geq 1</math>. Над полем с характеристикой <math>\neq 2, 3</math> эллиптическая кривая может быть задана (коротко) уравнением Вейерштрасса

<math>

y^2 = x^3 + Ax + B </math> с <math>A,B\in \mathbb{F}_{q}</math>. Множество точек, определённых над <math>\mathbb{F}_{q}</math>, состоит из решений <math>(a,b)\in\mathbb{F}_{q}^2</math>, удовлетворяющих уравнению кривой, и бесконечно удалённой точки <math>O</math>. Если использовать групповой закон на эллиптических кривых на этом множестве, можно видеть, что это множество <math>E(\mathbb{F}_{q})</math> образует абелеву группу, в которой <math>O</math> действует как нулевой элемент. Чтобы посчитать точки на эллиптической кривой, мы подсчитываем мощность множества <math>E(\mathbb{F}_{q})</math>. В подходе Шуфа для подсчёта мощности <math>\sharp E(\mathbb{F}_{q})</math> используется теорема Хассе об эллиптических кривых вместе с китайской теоремой об остатках и Шаблон:Не переведено 5.

Теорема Хассе

Шаблон:Main Теорема Хассе утверждает, что если <math>E/\mathbb{F}_{q}</math> является эллиптической кривой над конечным полем <math>\mathbb{F}_{q}</math>, то <math>\sharp E(\mathbb{F}_q)</math> удовлетворяет неравенству

<math>

\mid q + 1 - \sharp E(\mathbb{F}_{q}) \mid \leq 2\sqrt{q}. </math>

Этот сильный результат, полученный Хассе в 1934, упрощает нашу задачу путём сужения <math>\sharp E(\mathbb{F}_{q})</math> к конечному (хотя и большому) множеству возможностей. Если определить <math>t</math> как <math>q + 1 - \sharp E(\mathbb{F}_{q})</math> и использовать этот результат, мы получим, что вычисление мощности <math>t</math> по модулю <math>N</math>, где <math>N > 4\sqrt{q}</math>, достаточно для вычисления <math>t</math>, а потому и для получения <math>\sharp E(\mathbb{F}_{q})</math>. Хотя нет эффективного пути вычисления <math>t \pmod N</math> прямо для чисел <math>N</math> общего вида, можно вычислить <math>t \pmod l</math> для малого простого числа <math>l</math> довольно эффективно. Мы выбираем <math>S=\{l_1,l_2,...,l_r\}</math> в качестве множества различных простых чисел, таких, что <math>\prod l_i = N > 4\sqrt{q}</math>. Если задано <math>t \pmod {l_i}</math> для всех <math>l_i\in S</math>, китайская теорема об остатках позволяет вычислить <math>t \pmod N</math>.

Чтобы вычислить <math>t \pmod l</math> для простого <math>l \neq p</math>, мы используем теорию эндоморфизма Фробениуса <math>\phi</math> и Шаблон:Не переведено 5. Заметим, что рассмотрение простых чисел <math>l \neq p</math> не приводит к проблемам, поскольку мы всегда можем выбрать большее простое число, чтобы обеспечить, чтобы произведение было достаточно велико. В любом случае алгоритм Шуфа наиболее часто используется для случая <math>q=p</math>, поскольку имеются более эффективные, так называемые <math>p</math>-адичные алгоритмы, для полей с малой характеристикой.

Эндоморфизм Фробениуса

Если задана эллиптическая кривая <math>E</math>, определённая над <math>\mathbb{F}_{q}</math>, мы рассматриваем точки на <math>E</math> над <math>\bar{\mathbb{F}}_{q}</math>, Шаблон:Не переведено 5 поля <math>\mathbb{F}_{q}</math>. То есть мы разрешаем точкам иметь координаты в <math>\bar{\mathbb{F}}_{q}</math>. Эндоморфизм Фробениуса <math>\bar{\mathbb{F}}_{q}</math> над <math>\mathbb{F}_q</math> расширяет эллиптическую кривую отображением <math> \phi : (x, y) \mapsto (x^{q}, y^{q})</math>.

Это отображение тождественно на <math>E(\mathbb{F}_{q})</math> и можно расширить его точкой на бесконечности <math>O</math>, что делает его морфизмом группы из<math>E(\bar{\mathbb{F}_{q}})</math> на себя.

Эндоморфизм Фробениуса удовлетворяет квадратному уравнению, связанному с мощностью <math>E(\mathbb{F}_{q})</math> по следующей теореме:

Теорема: Эндоморфизм Фробениуса, заданный отображением <math>\phi</math>, удовлетворяет характеристическому уравнению

<math> \phi ^2 - t\phi + q = 0</math>, где <math> t = q + 1 - \sharp E(\mathbb{F}_q) </math>

Тогда для всех <math>P=(x, y) \in E</math> имеем <math>(x^{q^{2}}, y^{q^{2}} ) + q(x, y) = t(x^{q}, y^{q})</math>, где + означает сложение эллиптической кривой, а <math>q(x,y)</math> и <math>t(x^{q},y^{q})</math> означают скалярное произведение точки <math>(x,y)</math> на <math>q</math> и точки <math>(x^{q},y^{q})</math> на <math>t</math>.

Можно попытаться в символьном виде вычислить эти точки <math>(x^{q^{2}}, y^{q^{2}})</math>, <math>(x^{q}, y^{q})</math> и <math>q(x, y)</math> как функции на Шаблон:Не переведено 5 <math>\mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B)</math> на кривой <math>E</math>, а затем искать значение <math>t</math>, которое удовлетворяет уравнению. Однако степени получаются очень большими и такой подход практического значения не имеет.

Идея Шуфа заключалась в выполнении таких вычислений, ограничиваясь точками порядка <math>l</math> для различных малых простых чисел <math>l</math>. Фиксируя нечётное простое число <math>l</math> мы переходим к решению задачи определения <math>t_{l}</math>, определённого как <math>t \pmod l</math>, для заданного простого <math>l \neq 2, p</math>. Если точка <math>(x, y)</math> находится в подгруппе <math>l</math>-кручения <math>E[l]=\{P\in E(\bar{\mathbb{F}_{q}}) \mid lP=O \}</math>, то <math>qP = \bar{q}P</math>, где <math>\bar{q}</math> является единственным целым числом, таким, что <math>q \equiv \bar{q} \pmod l</math> и <math>\mid \bar{q} \mid< l/2</math>. Заметим, что <math>\phi(O) = O</math> и что для любого целого <math>r</math> мы имеем <math>r\phi (P) = \phi (rP)</math>. Таким образом, <math>\phi (P)</math> имеет тот же порядок, что и <math>P</math>. Тогда для <math>(x, y)</math>, принадлежащего <math>E[l]</math>, мы имеем также <math>t(x^{q}, y^{q})= \bar{t}(x^{q}, y^{q})</math>, если <math>t \equiv \bar{t} \pmod l</math>. Следовательно, мы свели нашу задачу к решению уравнения

<math> (x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y) \equiv \bar{t}(x^{q}, y^{q}),</math>

где <math>\bar{t}</math> и <math>\bar{q}</math> лежат в интервале <math>[-(l-1)/2,(l-1)/2]</math>.

Вычисления по простому модулю

Шаблон:Не переведено 5 с номером Шаблон:Mvar — это такой многочлен, что его корни являются в точности Шаблон:Mvar координатами точек порядка Шаблон:Mvar. Тогда ограничение вычисления <math>(x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y)</math> на точки Шаблон:Mvar-кручения означает вычисление этих выражений как функций координатного кольца Шаблон:Mvar и модуля Шаблон:Mvar-го многочлена деления. То есть мы работаем в <math>\mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{l})</math>. Это, в частности, означает, что степень Шаблон:Mvar и Шаблон:Mvar, определяемых через <math>(X(x,y),Y(x,y)):=(x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y)</math> не превышают 1 по переменной Шаблон:Mvar и <math>(l^2-3)/2</math> по переменной Шаблон:Mvar.

Скалярное произведение <math>\bar{q}(x, y)</math> может быть осуществлено методом удвоить-и-сложить, либо с помощью <math>\bar{q}</math>-го многочлена деления. Второй подход даёт:

<math>

\bar{q} (x,y) = (x_{\bar{q}},y_{\bar{q}}) = \left( x - \frac {\psi_{\bar{q}-1} \psi_{\bar{q}+1}}{\psi^{2}_{\bar{q}}}, \frac{\psi_{2\bar{q}}}{2\psi^{4}_{\bar{q}}} \right) </math>,

где <math>\psi_{n}</math> — Шаблон:Mvar-й многочлен деления. Заметим, что <math>y_{\bar{q}}/y</math> является функцией только от Шаблон:Mvar, обозначим эту функцию через <math>\theta(x)</math>.

Мы должны разбить задачу на два случая: случай, в котором <math>(x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y)</math>, и случай, в котором <math>(x^{q^{2}}, y^{q^{2}}) = \pm \bar{q}(x, y)</math>.

Случай 1: <math>(x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y)</math>

Используя формулу сложения для группы <math>E(\mathbb{F}_{q})</math>, мы получим:

<math>

X(x,y) = \left( \frac{y^{q^{2}} - y_{\bar{q}}}{x^{q^{2}} - x_{\bar{q}}} \right) ^{2} - x^{q^{2}} - x_{\bar{q}}. </math> Заметим, что это вычисление невозможно, если предположение о неравенстве не выполняется.

Мы теперь можем сузить выбор координаты Шаблон:Mvar для <math>\bar{t}</math> до двух возможностей, а именно — положительного и отрицательного случаев. Используя координату Шаблон:Mvar, определяем, который из двух случаев имеет место.

Сначала мы покажем, что Шаблон:Mvar является функцией только от Шаблон:Mvar. Рассмотрим <math>(y^{q^{2}} - y_{\bar{q}})^{2}=y^{2}(y^{q^{2}-1}-y_{\bar{q}}/y)^{2}</math>. Поскольку <math>q^{2}-1</math> чётно, заменив <math>y^{2}</math> на <math>x^3+Ax+B</math>, мы переписываем выражение как

<math>

(x^3+Ax+B)((x^3+Ax+B)^{\frac{q^{2}-1}{2}}-\theta(x)) </math>

и имеем

<math>

X(x)\equiv (x^3+Ax+B)((x^3+Ax+B)^{\frac{q^{2}-1}{2}}-\theta(x))\bmod \psi_l(x). </math>

Теперь, если <math>X \equiv x^{q} _ {\bar{t}}\bmod \psi_l(x)</math> для <math>\bar{t}\in [0,(l-1)/2]</math>, то для <math>\bar{t}</math> верно равенство

<math>

\phi ^{2}(P) \mp \bar{t} \phi(P) + \bar{q}P = O </math>

для всех точек Шаблон:Mvar Шаблон:Mvar-кручения.

Как было упомянуто ранее, используя Шаблон:Mvar и <math>y_{\bar{t}}^{q}</math>, мы можем теперь определить, какое из двух значений <math>\bar{t}</math> (<math>\bar{t}</math> или <math>-\bar{t}</math>) работает. Это даёт значение <math>t\equiv \bar{t}\pmod l</math>. Алгоритм Шуфа запоминает значения <math>\bar{t}\pmod l</math> в переменной <math>t_l</math> для каждого рассматриваемого простого Шаблон:Mvar.

Случай 2: <math>(x^{q^{2}}, y^{q^{2}}) = \pm \bar{q}(x, y)</math>

Предположим, что <math>(x^{q^{2}}, y^{q^{2}}) = \bar{q}(x, y)</math>. Поскольку Шаблон:Mvar является нечётным простым числом, невозможно, чтобы <math>\bar{q}(x, y)=-\bar{q}(x, y)</math>, а следовательно, <math>\bar{t}\neq 0</math>. Из характеристического уравнения следует, что <math>\bar{t} \phi(P) = 2\bar{q} P</math>, а следовательно, что <math>\bar{t}^{2}\bar{q} \equiv (2q)^{2} \pmod l</math>. Из этого следует, что Шаблон:Mvar является квадратом по модулю Шаблон:Mvar. Пусть <math>q \equiv w^{2} \pmod l</math>. Вычислим <math>w\phi(x,y)</math> в <math>\mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{l})</math> и проверим, выполняется ли <math> \bar{q}(x, y)=w\phi(x,y)</math>. Если так, то <math>t_{l}</math> является <math>\pm 2w \pmod l</math>, в зависимости от координаты y.

Если Шаблон:Mvar окажется не равным квадрату по модулю Шаблон:Mvar или если равенство не выполняется для некоторого Шаблон:Mvar и <math>-w</math>, наше предположение, что <math>(x^{q^{2}}, y^{q^{2}}) = +\bar{q}(x, y)</math> неверно, так что <math>(x^{q^{2}}, y^{q^{2}}) = - \bar{q}(x, y)</math>. Характеристическое уравнение даёт <math>t_l=0</math>.

Дополнительный случай <math>l = 2</math>

Если вспомнить, наши начальные соглашения не рассматривают случая <math>l = 2</math>. Поскольку мы предположили, что Шаблон:Mvar нечётно, <math>q + 1 - t \equiv t \pmod 2</math> и, в частности, <math>t_{2} \equiv 0 \pmod 2</math> тогда и только тогда, когда <math>E(\mathbb{F}_{q})</math> имеет элемент порядка 2. По определению сложения в группе любой элемент порядка 2 должен иметь вид <math>(x_{0}, 0)</math>. Таким образом <math>t_{2} \equiv 0 \pmod 2</math> тогда и только тогда, когда многочлен <math>x^{3} + Ax + B</math> имеет корень в <math>\mathbb{F}_{q}</math>, тогда и только тогда, когда НОД<math>(x^{q}-x, x^{3} + Ax + B)\neq 1</math>.

Алгоритм

    Ввод:
        1. Эллиптическая кривая <math>E = y^{2}-x^{3}-Ax-B</math>.
        2. Целое число Шаблон:Mvar для конечного поля <math>F_q</math> с <math>q=p^{b}, b \ge 1</math>.
    Вывод:
        Число точек Шаблон:Mvar над <math>F_q</math>.
    Выбираем множество нечётных простых чисел Шаблон:Mvar, не содержащее Шаблон:Mvar, такое, что  Шаблон:Nowrap
    Шаблон:Nowrap
    Шаблон:Nowrap. 
    Все вычисления в цикле ниже осуществляются в кольце <math>\mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{l}).</math>
    Шаблон:Nowrap
        Шаблон:Nowrap Шаблон:Nowrap
        Шаблон:Nowrap, y^{q^{2}})</math> и <math>(x_{\bar{q}},y_{\bar{q}})</math>.}}   
        Шаблон:Nowrap\neq x_{\bar{q}}</math>  то}}
            Шаблон:Nowrap
            Шаблон:Nowrap
                Шаблон:Nowrap</math> то}}
                    Шаблон:Nowrap</math> то}}
                        Шаблон:Nowrap
                    иначе
                        Шаблон:Nowrap
        иначе если Шаблон:Mvar является квадратом по модулю Шаблон:Mvar  то 
            Шаблон:Nowrap
            Шаблон:Nowrap
            Шаблон:Nowrap, y^{q^{2}})</math>  то}}
                Шаблон:Nowrap
            Шаблон:Nowrap, -y^{q^{2}})</math> то}}
                Шаблон:Nowrap
            иначе
                Шаблон:Nowrap
        иначе
            Шаблон:Nowrap
    Используем китайскую теорему об остатках для вычисления Шаблон:Mvar по модулю Шаблон:Mvar из уравнения <math>x \equiv t_{l} \pmod l</math>, где <math>l \in S</math>.
    Выводим <math>q+1-t</math>.

Сложность

Большинство вычислений заключаются в вычислении <math>\phi(P)</math> и <math>\phi^{2}(P)</math>, для каждого простого числа <math>l</math>, то есть вычислении <math>x^q</math>, <math>y^q</math>, <math>x^{q^2}</math>, <math>y^{q^2}</math> для каждого простого числа <math>l</math>. Вычисления включают возведение в степень в кольце <math>R = \mathbb{F}_{q}[x, y]/ (y^2-x^3-Ax-B, \psi_l)</math> и требуют <math>O(\log q)</math> умножений. Поскольку степень <math>\psi_l</math> равна <math>\frac{l^2-1}{2}</math>, каждый элемент в кольце является многочленом степени <math>O(l^2)</math>. По теореме о распределении простых чисел имеется около <math>O(\log q)</math> простых чисел размера <math>O(\log q)</math>, что даёт для <math>l</math> значение <math>O(\log q)</math>, и мы получаем <math>O(l^2) = O(\log^2q)</math>. Таким образом, каждое умножение в кольце <math>R</math> требует <math>O(\log^4 q)</math> умножений в <math>\mathbb{F}_{q}</math>, что, в свою очередь, требует, <math>O(\log^2 q)</math> битовых операций. В общей сложности число битовых операций для каждого простого числа <math>l</math> равно <math>O(\log^7 q)</math>. Если принять, что это вычисление требуется провести для каждого из <math>O(\log q)</math> простых чисел, полная сложность алгоритма Шуфа становится <math>O(\log^8 q)</math>. Использование быстрых операций с многочленами и целочисленной арифметики сокращает это время до <math>\tilde{O}(\log^5 q)</math>.

Улучшения алгоритма Шуфа

В 1990-х годах Ноам Элкис, а затем Шаблон:Не переведено 5 придумали улучшения базового алгоритма Шуфа путём ограничения множества простых чисел <math>S = \{l_1, \ldots, l_s\}</math> до чисел определённого вида. Эти числа стали называться простыми Элкиса и простыми Аткина соответственно. Простое число <math>l</math> называется простым Элкиса, если характеристическое равенство <math>\phi^2-t\phi+ q = 0</math> разложим над <math>\mathbb{F}_l</math>, а простые Аткина — это простые, не являющиеся простыми Элкиса. Аткин показал как комбинировать информацию, полученную из простых Аткина, с информацией, полученной из простых Элкиса, чтобы получить эффективный алгоритм, который получил название «Шаблон:Не переведено 5». Первая задача — определить, данное простое является простым Элкиса, или Аткина. Чтобы это получить, используем модулярные многочлены, которые возникают при изучении модулярных форм и интерпретации эллиптических кривых над полем комплексных чисел как решёток. Как только мы определим, какой случай мы имеем, вместо использования Шаблон:Не переведено 5 мы можем работать с многочленами, имеющими меньшие степени по сравнению с многочленами деления: <math>O(l)</math> вместо <math>O(l^2)</math>. Для эффективной имплементации используются вероятностные алгоритмы поиска корней, что делает алгоритм алгоритмом Лас-Вегаса, а не детерминированным алгоритмом. При эвристическом предположении, что примерно половина простых чисел, не превосходящих <math>O(\log q)</math>, являются простыми Элкиса, это даёт алгоритм, который эффективнее алгоритма Шуфа, и ожидаемое время работы этого алгоритма равно <math>O(\log^6 q)</math>, если использовать обычную арифметику, и <math>\tilde{O}(\log^4 q)</math>, если использовать быструю арифметику. Следует заметить, что это эвристическое предположение верно для большинства эллиптических кривых, но не известно для общего случая, даже при верности обобщённой гипотезы Римана.

Имплементации

Некоторые алгоритмы были имплементированы на C++ Майком Скоттом и доступны в исходном коде. Имплементация абсолютно свободная (никаких условий, никаких ограничений), но использует библиотеку MIRACL, которая распространяется под лицензией AGPLv3.

• Алгоритм Шуфа с имплементацией для <math>E(\mathbb{F}_p)</math> с простым <math>p</math>.
• Алгоритм Шуфа с имплементацией для <math>E(\mathbb{F}_{2^m})</math>.

См. также

• Эллиптическая криптография
• Шаблон:Не переведено 5
• Шаблон:Не переведено 5
• Эндоморфизм Фробениуса

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья