Алгоритм Шуфа

Алгори́тм Шу́фа — ефективний алгоритм підрахунку числа точок на еліптичній кривій над скінченним полем. Має застосування в еліптичній криптографії, де важливо знати кількість точок, щоб оцінити складність розв'язання задачі дискретного логарифма в групі точок на еліптичній кривій.

Алгоритм опублікував Рене Шуф в 1985 році. Це був теоретичний прорив, бо це перший детермінований алгоритм, який виконується за поліноміальний час, для підрахунку точок на еліптичних кривих. До алгоритму Шуфа підходи до підрахунку точок на еліптичних кривих були здебільшого трудомісткими та виконувались за експоненціальний час.

Вступ

Нехай $E$ – еліптична крива над скінченним полем $\mathbb {F} _{q}$, де $q=p^{n}$, $p$ – просте число та $n\in \mathbb {N}$. Над полем, характеристика якого не дорівнює 2 або 3, еліптична крива може бути задана рівнянням Вейєрштрасса

$y^{2}=x^{3}+Ax+B~$,

де $A,B\in \mathbb {F} _{q}$. Множина точок, визначених над $\mathbb {F} _{q}$, складається з розв'язків $(x,y)\in \mathbb {F} _{q}^{2}$, які задовольняють рівняння кривої, та точки на нескінченності $O$. Застосовуючи груповий закон на еліптичних кривих до цієї множини отримаємо абелеву групу $E(\mathbb {F} _{q})$, у якій $O$ буде нейтральним елементом. Кількість точок на еліптичній кривій дорівнює потужності множини $E(\mathbb {F} _{q})$. Підхід Шуфа для обчислення потужності $\#E(\mathbb {F} _{q})$ використовує теорему Гассе про еліптичні криві разом з китайською теоремою про остачі та поліномами ділення.

Теорема Гассе

Теорема Гассе стверджує, що якщо $E/\mathbb {F} _{q}$ є еліптичною кривою над скінченним полем $\mathbb {F} _{q}$, то $\#E(\mathbb {F} _{q})$ задовольняє нерівність

$\mid q+1-\#E(\mathbb {F} _{q})\mid \leq 2{\sqrt {q}}.$

Цей сильний результат, отриманий Гассе в 1934 році, спрощує нашу задачу, звужуючи до скінченного (хоча і великого) набору можливих значень $\#E(\mathbb {F} _{q})$. Позначимо $t=q+1-\#E(\mathbb {F} _{q})$, обчислення значення $t$ по модулю $N>4{\sqrt {q}}$ буде достатньо для знаходження самого значення $t$, а з нього – значення $\#E(\mathbb {F} _{q})$. Хоча немає прямого ефективного шляху обчислення $t{\pmod {N}}$ для довільного $N$, проте можна обчислити $t{\pmod {l}}$ для малого простого числа $l$ більш ефективно. Виберемо множину різних простих чисел $S=\{l_{1},l_{2},...,l_{r}\}$, для яких $\prod l_{i}=N>4{\sqrt {q}}$. Після отримання значень $t{\pmod {l_{i}}}$ для кожного $l_{i}\in S$ обчислимо $t{\pmod {N}}$ за допомогою китайської теореми про лишки.

Для того, щоб обчислити $t{\pmod {l}}$ для простого $l\neq p$, використаємо ендоморфізм Фробеніуса $\phi$ та поліноми ділення. Розгляд простих чисел $l\neq p$ не є проблемою, бо завжди можна вибрати більше просте число, яке займе місце $p$, так щоб добуток вище задовольняв відповідну нерівність.

Ендоморфізм Фробеніуса

Нехай $E$ – еліптична крива, визначена над $\mathbb {F} _{q}$, розглянемо точки на $E$ над ${\bar {\mathbb {F} }}_{q}$, де ${\bar {\mathbb {F} }}_{q}$ – алгебраїчне замиканням $\mathbb {F} _{q}$. Тобто ми дозволяємо точки з координатами в ${\bar {\mathbb {F} }}_{q}$. Ендоморфізм Фробеніуса ${\bar {\mathbb {F} }}_{q}$ над $\mathbb {F} _{q}$ розширює еліптичну криву відображенням $\phi :(x,y)\mapsto (x^{q},y^{q})$.

Це відображення тотожне на $E(\mathbb {F} _{q})$, можна розширити його точкою на нескінченності $O$, що зробить його морфізмом з $E({\bar {\mathbb {F} }}_{q})$ на себе.

Ендоморфізм Фробеніуса задовольняє квадратне рівняння, пов'язане з потужністю $E(\mathbb {F} _{q})$, за наступною теоремою:

Теорема. Ендоморфізм Фробеніуса, заданий відображенням $\phi$, задовольняє характеристичне рівняння $\phi ^{2}-t\phi +q=0,$ де $t=q+1-\#E(\mathbb {F} _{q})$

Тоді для всіх $P=(x,y)\in E$ матимемо $(x^{q^{2}},y^{q^{2}})+q(x,y)=t(x^{q},y^{q})$, де «$+$» – операція додавання точок на еліптичній кривій за груповим законом, а $q(x,y)$ та $t(x^{q},y^{q})$ – множення точок $(x,y)$ та $(x^{q},y^{q})$ на скаляри $q$ та $t$, відповідно.

Можна спробувати обчислити $(x^{q^{2}},y^{q^{2}})$, $(x^{q},y^{q})$ і $q(x,y)$ як функції на координатному кільці $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)$ кривої $E$, а потім шукати значення $t$, яке задовольняє рівняння. Однак, на практиці, коли степені стають занадто великими, такий підхід буде недоцільним.

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

$(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)\equiv {\bar {t}}(x^{q},y^{q})$, де ${\bar {q}},{\bar {t}}\in [-(l-1)/2,(l-1)/2]$.

Обчислення по простому модулю

Позначимо $(X(x,y),Y(x,y)):=(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)$ (пам'ятаємо, що ми працюємо по модулю l).

Скалярний добуток ${\bar {q}}(x,y)$ можна обчислити методом подвоїти та додати або використовуючи ${\bar {q}}$-ий поліном ділення. Останній підхід дає:

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

де $\psi _{n}$ – n-ий поліном ділення. Функція $y_{\bar {q}}/y$ залежить тільки від x, позначимо її через $\theta (x)$.

Розглянемо два випадки: $(x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)$ та $(x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)$ (тут рівність по модулю $\psi _{l}$).

Випадок 1: $(x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)$

Використовуючи формулу додавання для групи $E(\mathbb {F} _{q})$ отримаємо:

$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}}.$

У випадку рівності таке обчислення буде неправильним.

Далі можна звузити вибір координати x до двох можливих варіантів, різних за знаком та рівних по модулю. Потім використовуючи y-координату знайдемо який з варіантів має місце.

Покажемо, шо $X$ є функцією тільки від $x$. Розглянемо $(y^{q^{2}}-y_{\bar {q}})^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {q}}/y)^{2}$. Замінимо $y^{2}$ на $x^{3}+Ax+B$, тоді отримаємо

$(x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x))$

Оскільки $q^{2}-1$ парне, то така заміна означає, що ми працюємо у факторкільці $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)$.

Якщо $X\equiv x_{\bar {t}}^{q}{\bmod {\psi }}_{l}(x)$ для деякого ${\bar {t}}\in [0,(l-1)/2]$, то виконується рівність

$\phi ^{2}(P)\mp {\bar {t}}\phi (P)+{\bar {q}}P=O$

для всіх $P\in E[l]$.

Як згадувалося раніше, використовуючи $Y$ та $y_{\bar {t}}^{q}$, можна визначити, яке з двох значень ${\bar {t}}$ (${\bar {t}}$ або $-{\bar {t}}$) працює. Це дає значення $t\equiv {\bar {t}}{\pmod {l}}$. Далі алгоритм Шуфа зберігає значення ${\bar {t}}{\pmod {l}}$ в змінній $t_{l}$ для кожного розглянутого простого l.

Випадок 2: $(x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)$

Спочатку припустимо, що $(x^{q^{2}},y^{q^{2}})=+{\bar {q}}(x,y)$. Для точки $P\in E(\mathbb {F} _{q})$, що задовольняє це, з характеристичного рівняння отримуємо ${\bar {t}}\phi (P)=2{\bar {q}}P$. А отже, ${\bar {t}}^{2}{\bar {q}}P\equiv (2q)^{2}P{\pmod {l}}$. З цього випливає, що $q$ є квадратом по модулю $l$. Нехай $q\equiv w^{2}{\pmod {l}}$. Обчислимо $w\phi (x,y)$ в $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})$ та перевіримо чи ${\bar {q}}(x,y)=w\phi (x,y)$. Якщо це так, то $t_{l}=\pm 2w{\pmod {l}}$, де знак залежить від y-координати.

Якщо $q$ не є квадратом по модулю l або рівність не виконується для жодного $w$, то припущення, що $(x^{q^{2}},y^{q^{2}})=+{\bar {q}}(x,y)$ невірне, тому $(x^{q^{2}},y^{q^{2}})=-{\bar {q}}(x,y)$. Характеристичне рівняння дає $t_{l}=0$.

Додатковий випадок: $l=2$

Якщо згадати, наші початкові міркування опускають випадок $l=2$. Припускалось, що q непарне та зокрема, $t_{2}\equiv 0{\pmod {2}}$ тоді і тільки тоді, коли $E(\mathbb {F} _{q})$ містить елемент порядку 2. За означенням додавання в цій групі будь-який елемент порядку 2 має вигляд $(x_{0},0)$. Таким чином $t_{2}\equiv 0{\pmod {2}}$ тоді і тільки тоді, коли $x^{3}+Ax+B$ має корінь з $\mathbb {F} _{q}$ тоді і тільки тоді, коли ${\text{НСД}}(x^{q}-x,x^{3}+Ax+B)\neq 1$.

Алгоритм

    Ввід:
        1. Еліптична крива $E=y^{2}-x^{3}-Ax-B$;
        2. Натуральне число $q=p^{b},b\in \mathbb {N}$, для скінченного поля $F_{q}$.
    Вивід:
        Число точок E над $F_{q}$.
    Вибираємо множину непарних простих чисел S, яка не містить p, така що $N=\prod _{l\in S}l>4{\sqrt {q}}.$
    Покладемо $t_{2}=0$ якщо ${\text{НСД}}(x^{q}-x,x^{3}+Ax+B)\neq 1$, інакше $t_{2}=1$.
    Обчислюємо поліном ділення $\psi _{l}$.
    Всі обчислення в циклі нижче виконуються в кільці $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l}).$
    Для $l\in S$ виконуємо:
        Нехай ${\bar {q}}$  – єдине ціле таке що,  $q\equiv {\bar {q}}{\pmod {l}}$ and $\mid {\bar {q}}\mid <l/2$.
        Обчислюємо $(x^{q},y^{q})$, $(x^{q^{2}},y^{q^{2}})$ та $(x_{\bar {q}},y_{\bar {q}})$.
        Якщо $x^{q^{2}}\neq x_{\bar {q}}$, то
            Обчислюємо $(X,Y)$.
            для $1\leq {\bar {t}}\leq (l-1)/2$ виконуємо:
                якщо $X=x_{\bar {t}}^{q}$, то
                    якщо $Y=y_{\bar {t}}^{q}$, то
                        $t_{l}={\bar {t}}$;
                    інакше
                        $t_{l}=-{\bar {t}}$.
        інакше якщо q є квадратом по модулю l, то
            обчислюємо w, для якого $q\equiv w^{2}{\pmod {l}}$
            обчислюємо $w(x^{q},y^{q})$
            якщо $w(x^{q},y^{q})=(x^{q^{2}},y^{q^{2}})$, то
                $t_{l}=2w$
            інакше якщо $w(x^{q},y^{q})=(x^{q^{2}},-y^{q^{2}})$, то
                $t_{l}=-2w$
            інакше
                $t_{l}=0$
        інакше
            $t_{l}=0$
    Використовуємо китайську теорему про остачі для обчислення t по модулю N
        з рівнянь $t\equiv t_{l}{\pmod {l}}$, де $l\in S$.
    Виводимо $q+1-t$.

Складність

Більшість обчислень припадає на $\phi (P)$ та $\phi ^{2}(P)$ для кожного простого $l$, тобто на обчислення $x^{q}$, $y^{q}$, $x^{q^{2}}$, $y^{q^{2}}$ для кожного простого $l$. Ці обчислення включають піднесення до степені $R=\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})$ та потребують $O(\log q)$ множень. Степінь $\psi _{l}$ дорівнює ${\frac {l^{2}-1}{2}}$, тобто $O(l^{2})$. За теоремою про розподіл простих чисел існує близько $O(\log q)$ простих чисел розміру $O(\log q)$, це дає $l=O(\log q)$, маємо $O(l^{2})=O(\log ^{2}q)$. Таким чином, множення в кільці $R$ потребує $O(\log ^{4}q)$ множень $\mathbb {F} _{q}$, що в свою чергу потребує $O(\log ^{2}q)$ бітових операцій. Загалом, кількість бітових операцій для кожного простого $l$ дорівнює $O(\log ^{7}q)$. Оскільки обчислення необхідно провести для $O(\log q)$ простих чисел, то повна складність алгоритму Шуфа дорівнює $O(\log ^{8}q)$. Використання швидких операцій з поліномами та цілочисельної арифметики скорочує цей час до ${\tilde {O}}(\log ^{5}q)$. Тут ${\tilde {O}}$ означає $O$ зі знехтуваними логарифмічним множниками.

Модифікація алгоритму Шуфа

У 1990-х роках Ноам Елкіс, а за ним А. О. Л. Аткін, вдосконалили алгоритм Шуфа через обмеження множини простих чисел $S=\{l_{1},\ldots ,l_{s}\}$, розглянутої раніше, до простих чисел певного виду. Просте число $l$ називається простим числом Елкіса, якщо характеристичне рівняння $\phi ^{2}-t\phi +q=0$ розкладається над $\mathbb {F} _{l}$, а прості числа Аткіна – це прості числа, які не є простими Елкіса. Аткін показав як комбінувати інформацію, отриману з простих чисел Аткіна, з інформацією, отриманою з простих чисел Елкіса, щоб отримати більш ефективний алгоритм, який отримав назву алгоритм Шуфа-Елкіса-Аткіна. Перша задача, яку потрібно вирішити, – чи є задане просте число простим Аткіна, чи простим Елкіса. Для цього використовуються модулярні поліноми, які виникають при вивченні модулярних форм та інтерпретації еліптичних кривих над полем комплексних чисел як решіток. Після того, як визначимо, у якому випадку перебуваємо, замість того, щоб використовувати поліноми ділення, ми зможемо працювати з поліномами, які мають нижчий степінь, ніж відповідні поліноми ділення: $O(l)$ замість $O(l^{2})$. Для ефективної реалізації використовуються ймовірнісні алгоритми знаходження коренів, що робить алгоритм алгоритмом Лас-Вегаса, а не детермінованим алгоритмом.

При евристичному припущенні, що приблизно половина простих чисел, які не перевищують $O(\log q)$, є простими числами Елкіса, це дає більш ефективний алгоритм ніж алгоритм Шуфа з очікуваним часом роботи $O(\log ^{6}q)$ при використанні звичайної арифметики та ${\tilde {O}}(\log ^{4}q)$ при використанні швидкої арифметики. Хоч це евристичне припущення вірне для багатьох еліптичних кривих, але невідомо чи воно виконується в загальному випадку, навіть при істинності узагальненої гіпотези Рімана.

Джерела

• R. Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. Math. Comp., 44(170):483–494, 1985. Available at http://www.mat.uniroma2.it/~schoof/ctpts.pdf
• R. Schoof: Counting Points on Elliptic Curves over Finite Fields. J. Theor. Nombres Bordeaux 7:219–254, 1995. Available at http://www.mat.uniroma2.it/~schoof/ctg.pdf
• G. Musiker: Schoof's Algorithm for Counting Points on $E(\mathbb {F} _{q})$. Available at http://www.math.umn.edu/~musiker/schoof.pdf
• V. Müller : Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern. Master's Thesis. Universität des Saarlandes, Saarbrücken, 1991. Available at http://lecturer.ukdw.ac.id/vmueller/publications.php
• A. Enge: Elliptic Curves and their Applications to Cryptography: An Introduction. Kluwer Academic Publishers, Dordrecht, 1999.
• L. C. Washington: Elliptic Curves: Number Theory and Cryptography, 2nd Ed. Chapman & Hall/CRC, New York, 2008.
• Н. Коблиц: Курс теории чисел и криптографии, Научное издательство «ТВП», 2001