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

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

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

Вступ

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

$y^2=x^3+Ax+B$,

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

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

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

$\mid q+1-\mathrm{\#}E({𝔽}_q)\mid \le 2\sqrt{q}.$

Цей сильний результат, отриманий Гассе в 1934 році, спрощує нашу задачу, звужуючи до скінченного (хоча і великого) набору можливих значень $\mathrm{\#}E({𝔽}_q)$. Позначимо $t=q+1-\mathrm{\#}E({𝔽}_q)$, обчислення значення $t$ по модулю $N>4\sqrt{q}$ буде достатньо для знаходження самого значення $t$, а з нього – значення $\mathrm{\#}E({𝔽}_q)$. Хоча немає прямого ефективного шляху обчислення $t(\mathrm{mod}N)$ для довільного $N$, проте можна обчислити $t(\mathrm{mod}l)$ для малого простого числа $l$ більш ефективно. Виберемо множину різних простих чисел $S=\{l_1,l_2,...,l_r\}$, для яких $\prod l_i=N>4\sqrt{q}$. Після отримання значень $t(\mathrm{mod}{l}_i)$ для кожного $l_i\in S$ обчислимо $t(\mathrm{mod}N)$ за допомогою китайської теореми про лишки.

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

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

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

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

Ендоморфізм Фробеніуса задовольняє квадратне рівняння, пов'язане з потужністю $E({𝔽}_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)$ як функції на Шаблон:Не перекладено ${𝔽}_q[x,y]/(y^2-x^3-Ax-B)$ кривої $E$, а потім шукати значення $t$, яке задовольняє рівняння. Однак, на практиці, коли степені стають занадто великими, такий підхід буде недоцільним.

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

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

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

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

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

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

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

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

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

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

$X(x,y)={\left(\frac{y^{q^2}-y_{\overline{q}}}{x^{q^2}-x_{\overline{q}}}\right)}^2-x^{q^2}-x_{\overline{q}}.$

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

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

Покажемо, шо $X$ є функцією тільки від $x$. Розглянемо $(y^{q^2}-y_{\overline{q}}{)}^2=y^2(y^{q^2-1}-y_{\overline{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$ парне, то така заміна означає, що ми працюємо у факторкільці ${𝔽}_q[x,y]/(y^2-x^3-Ax-B)$.

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

${\varphi }^2(P)\mp \overline{t}\varphi (P)+\overline{q}P=O$

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

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

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

Спочатку припустимо, що $(x^{q^2},y^{q^2})=+\overline{q}(x,y)$. Для точки $P\in E({𝔽}_q)$, що задовольняє це, з характеристичного рівняння отримуємо $\overline{t}\varphi (P)=2\overline{q}P$. А отже, ${\overline{t}}^2\overline{q}P\equiv (2q{)}^{2}P(\mathrm{mod}l)$. З цього випливає, що $q$ є квадратом по модулю $l$. Нехай $q\equiv w^2(\mathrm{mod}l)$. Обчислимо $w\varphi (x,y)$ в ${𝔽}_q[x,y]/(y^2-x^3-Ax-B,{\psi }_l)$ та перевіримо чи $\overline{q}(x,y)=w\varphi (x,y)$. Якщо це так, то $t_l=\pm 2w(\mathrm{mod}l)$, де знак залежить від Шаблон:Mvar-координати.

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

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

Якщо згадати, наші початкові міркування опускають випадок $l=2$. Припускалось, що Шаблон:Mvar непарне та зокрема, $t_2\equiv 0(\mathrm{mod}2)$ тоді і тільки тоді, коли $E({𝔽}_q)$ містить елемент порядку 2. За означенням додавання в цій групі будь-який елемент порядку 2 має вигляд $(x_0,0)$. Таким чином $t_2\equiv 0(\mathrm{mod}2)$ тоді і тільки тоді, коли $x^3+Ax+B$ має корінь з ${𝔽}_q$ тоді і тільки тоді, коли $\text{НСД}(x^q-x,x^3+Ax+B)\ne 1$.

Алгоритм

    Ввід:
        1. Еліптична крива $E=y^2-x^3-Ax-B$;
        2. Натуральне число $q=p^b,b\in \mathbb{N}$, для скінченного поля $F_q$.
    Вивід:
        Число точок Шаблон:Mvar над $F_q$.
    Вибираємо множину непарних простих чисел Шаблон:Mvar, яка не містить Шаблон:Mvar, Шаблон:Nowrap
    Шаблон:Nowrap
    Шаблон:Nowrap
    Всі обчислення в циклі нижче виконуються Шаблон:Nowrap
    Шаблон:Nowrap
        Шаблон:Nowrap Шаблон:Nowrap
        Шаблон:Nowrap
        Шаблон:Nowrap
            Шаблон:Nowrap
            Шаблон:Nowrap
                Шаблон:Nowrap
                    Шаблон:Nowrap
                        Шаблон:Nowrap
                    інакше
                        Шаблон:Nowrap
        інакше якщо Шаблон:Mvar є квадратом по модулю Шаблон:Mvar, то
            Шаблон:Nowrap
            Шаблон:Nowrap
            Шаблон:Nowrap
                Шаблон:Nowrap
            Шаблон:Nowrap
                Шаблон:Nowrap
            інакше
                Шаблон:Nowrap
        інакше
            Шаблон:Nowrap
    Використовуємо китайську теорему про остачі для обчислення Шаблон:Mvar по модулю Шаблон:Mvar
        з рівнянь $t\equiv t_l(\mathrm{mod}l)$, де $l\in S$.
    Виводимо $q+1-t$.

Складність

Більшість обчислень припадає на $\varphi (P)$ та ${\varphi }^2(P)$ для кожного простого $l$, тобто на обчислення $x^q$, $y^q$, $x^{q^2}$, $y^{q^2}$ для кожного простого $l$. Ці обчислення включають піднесення до степені $R={𝔽}_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)$ множень ${𝔽}_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$ зі знехтуваними логарифмічним множниками.

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

Шаблон:Main У 1990-х роках Шаблон:Не перекладено, а за ним Шаблон:Не перекладено, вдосконалили алгоритм Шуфа через обмеження множини простих чисел $S=\{l_1,\dots ,l_s\}$, розглянутої раніше, до простих чисел певного виду. Просте число $l$ називається простим числом Елкіса, якщо характеристичне рівняння ${\varphi }^2-t\varphi +q=0$ розкладається над ${𝔽}_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 Шаблон:Webarchive
• 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 Шаблон:Webarchive
• G. Musiker: Schoof's Algorithm for Counting Points on $E({𝔽}_q)$. Available at http://www.math.umn.edu/~musiker/schoof.pdf Шаблон:Webarchive
• 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 Шаблон:Webarchive
• 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