Перегляд вихідного коду сторінки Алгоритм Шуфа

'''Алгори́тм Шу́фа'''&nbsp;— ефективний [[алгоритм]] підрахунку числа точок на [[Еліптична крива|еліптичній кривій]] над [[Скінченне поле|скінченним полем]]. Має застосування в [[Еліптична криптографія|еліптичній криптографії]], де важливо знати кількість точок, щоб оцінити складність розв'язання [[Дискретний логарифм|задачі дискретного логарифма]] в [[Група (математика)|групі]] точок на еліптичній кривій.

Алгоритм опублікував {{не перекладено|Рене Шуф|Рене Шуф|en|René Schoof}} в 1985 році. Це був теоретичний прорив, бо це перший [[детермінований алгоритм]], який виконується за поліноміальний час, для {{не перекладено|Підрахунок точок на еліптичних кривих|підрахунку точок на еліптичних кривих|en|Counting points on elliptic curves}}. До алгоритму Шуфа підходи до підрахунку точок на еліптичних кривих були здебільшого трудомісткими та виконувались за експоненціальний час.

== Вступ ==
Нехай <math>E</math>&nbsp;– еліптична крива над скінченним полем <math>\mathbb{F}_q</math>, де <math>q=p^n</math>, <math>p</math>&nbsp;– [[просте число]] та <math>n \in \mathbb{N}</math>. Над полем, характеристика якого не дорівнює ''2'' або ''3'', еліптична крива може бути задана рівнянням Вейєрштрасса
: <math>y^2=x^3+Ax+B~</math>,

де <math>A, B \in \mathbb{F}_q</math>. Множина точок, визначених над <math>\mathbb{F}_q</math>, складається з розв'язків <math>(x,y) \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>\#E(\mathbb{F}_q)</math> використовує [[Теорема Гассе про еліптичні криві|теорему Гассе про еліптичні криві]] разом з [[Китайська теорема про остачі|китайською теоремою про остачі]] та {{не перекладено|Поліноми ділення|поліномами ділення|en|Division polynomials}}.

== Теорема Гассе ==
{{main|Теорема Гассе про еліптичні криві}}

Теорема Гассе стверджує, що якщо <math>E(\mathbb{F}_{q})</math> є еліптичною кривою над скінченним полем <math>\mathbb{F}_q</math>, то <math>
\#E(\mathbb{F}_q)</math> задовольняє нерівність
: <math>\mid q + 1 - \# E(\mathbb{F}_{q}) \mid \leq 2\sqrt{q}.</math>

Цей сильний результат, отриманий Гассе в 1934 році, спрощує нашу задачу, звужуючи до скінченного (хоча і великого) набору можливих значень <math>\# E(\mathbb{F}_{q})</math>. Позначимо <math>t = q + 1 - \# E(\mathbb{F}_{q})</math>, обчислення значення <math>t</math> по модулю <math>N > 4\sqrt{q}</math> буде достатньо для знаходження самого значення <math>t</math>, а з нього&nbsp;– значення <math>\# 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> та поліноми ділення. Розгляд простих чисел <math>l \neq p</math> не є проблемою, бо завжди можна вибрати більше просте число, яке займе місце <math>p</math>, так щоб добуток вище задовольняв відповідну нерівність.

== Ендоморфізм Фробеніуса ==
Нехай <math>E</math>&nbsp;– еліптична крива, визначена над <math>\mathbb{F}_{q}</math>, розглянемо точки на <math>E</math> над <math>\bar{\mathbb{F}}_{q}</math>, де <math>\bar{\mathbb{F}}_{q}</math>&nbsp;– [[алгебраїчне замикання]]м <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 - \# 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>+</math>»&nbsp;– операція додавання точок на еліптичній кривій за груповим законом, а <math>q(x,y)</math> та <math>t(x^{q},y^{q})</math>&nbsp;– множення точок <math>(x,y)</math> та <math>(x^{q},y^{q})</math> на скаляри <math>q</math> та <math>t</math>, відповідно.

Можна спробувати обчислити <math>(x^{q^{2}}, y^{q^{2}})</math>, <math>(x^{q},y^{q})</math> і <math>q(x, y)</math> як функції на {{не перекладено|Координатне кільце|координатному кільці|en|Imaginary hyperelliptic curve#Coordinate ring}} <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>&nbsp;– єдине ціле, таке що <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) \in 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{q}, \bar{t} \in [-(l-1)/2,(l-1)/2]</math>.

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

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

Скалярний добуток <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>&nbsp;– {{mvar|n}}-ий поліном ділення. Функція <math>y_{\bar{q}}/y</math> залежить тільки від {{mvar|x}}, позначимо її через <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> (тут рівність по модулю <math>\psi_l</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|x}} до двох можливих варіантів, різних за знаком та рівних по модулю. Потім використовуючи {{mvar|y}}-координату знайдемо який з варіантів має місце.

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

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

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

для всіх <math>P \in E[l]</math>.

Як згадувалося раніше, використовуючи <math>Y</math> та <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|l}}.

'''Випадок 2: <math>(x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y)</math>'''

Спочатку припустимо, що <math>(x^{q^{2}}, y^{q^{2}}) = +\bar{q}(x, y)</math>. Для точки <math>P \in E(\mathbb{F}_{q})</math>, що задовольняє це, з характеристичного рівняння отримуємо <math>\bar{t}\phi(P)=2\bar{q}P</math>. А отже, <math>\bar{t}^{2}\bar{q} P \equiv (2q)^{2}P  \pmod l</math>. З цього випливає, що <math>q</math> є квадратом по модулю <math>l</math>. Нехай <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}=\pm 2w \pmod l</math>, де знак залежить від {{mvar|y}}-координати.

Якщо <math>q</math> не є квадратом по модулю {{mvar|l}} або рівність не виконується для жодного <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|q}} непарне та зокрема, <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>\text{НСД}(x^{q}-x, x^{3} + Ax + B)\neq 1</math>.

== Алгоритм ==

     Ввід:
         1. Еліптична крива <math>E = y^{2}-x^{3}-Ax-B</math>;
         2. Натуральне число <math>q=p^{b}, b \in \mathbb{N}</math>, для скінченного поля <math>F_q</math>.
     Вивід:
         Число точок {{mvar|E}} над <math>F_q</math>.
     Вибираємо множину непарних простих чисел {{mvar|S}}, яка не містить {{mvar|p}}, {{nowrap|така що <math>N=\prod_{l\in S} l > 4\sqrt{q}.</math>}}
     {{nowrap|'''Покладемо''' <math>t_2=0</math> '''якщо''' <math>\text{НСД}(x^{q}-x, x^{3} + Ax + B)\neq 1</math>, '''інакше''' <math>t_2=1</math>.}}
     {{nowrap|Обчислюємо поліном ділення <math>\psi_l</math>.}}
     Всі обчислення в циклі нижче виконуються {{nowrap|в кільці <math>\mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{l}).</math>}}
     {{nowrap|'''Для''' <math>l \in S</math> '''виконуємо''':}}
         {{nowrap|'''Нехай''' <math>\bar{q}</math> &nbsp;– єдине ціле}} {{nowrap|таке що,  <math>q \equiv \bar{q}  \pmod l</math> and <math>\mid \bar{q} \mid< l/2</math>.}}
         {{nowrap|Обчислюємо <math>(x^{q}, y^{q})</math>, <math>(x^{q^{2}}, y^{q^{2}})</math> та <math>(x_{\bar{q}},y_{\bar{q}})</math>.}}
         {{nowrap|'''Якщо''' <math>x^{q^{2}}\neq x_{\bar{q}}</math>, '''то'''}}
             {{nowrap|Обчислюємо <math>(X,Y)</math>.}}
             {{nowrap|'''для''' <math>1\leq \bar{t} \leq (l-1)/2</math> '''виконуємо''':}}
                 {{nowrap|'''якщо''' <math>X = x^{q} _ {\bar{t}}</math>, '''то'''}}
                     {{nowrap|'''якщо''' <math>Y = y^{q} _ {\bar{t}}</math>, '''то'''}}
                         {{nowrap|<math>t_{l}=\bar{t}</math>;}}
                     '''інакше'''
                         {{nowrap|<math>t_{l}=-\bar{t}</math>.}}
         '''інакше якщо''' {{mvar|q}} є квадратом по модулю {{mvar|l}}, '''то'''
             {{nowrap|обчислюємо {{mvar|w}}, для якого <math>q\equiv w^{2} \pmod l</math>}}
             {{nowrap|обчислюємо <math>w(x^{q}, y^{q})</math>}}
             {{nowrap|'''якщо''' <math>w(x^{q}, y^{q})=(x^{q^{2}}, y^{q^{2}})</math>, '''то'''}}
                 {{nowrap|<math>t_l=2w</math>}}
             {{nowrap|'''інакше якщо''' <math>w(x^{q}, y^{q})=(x^{q^{2}}, -y^{q^{2}})</math>, '''то'''}}
                 {{nowrap|<math>t_l=-2w</math>}}
             '''інакше'''
                 {{nowrap|<math>t_{l}=0</math>}}
         '''інакше'''
             {{nowrap|<math>t_{l}=0</math>}}
     Використовуємо китайську теорему про остачі для обчислення {{mvar|t}} по модулю {{mvar|N}}
         з рівнянь <math>t \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=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>. Тут <math>\tilde{O}</math> означає <math>O</math> зі знехтуваними логарифмічним множниками.

== Модифікація алгоритму Шуфа ==
{{main|Алгоритм Шуфа — Елкіса — Аткіна}}
У 1990-х роках {{не перекладено|Ноам Елкіс|Ноам Елкіс|en|Noam Elkies}}, а за ним {{не перекладено|А. О. Л. Аткін|А. О. Л. Аткін|en|A. O. L. Atkin}}, вдосконалили алгоритм Шуфа через обмеження множини простих чисел <math>S = \{l_1, \ldots, l_s\}</math>, розглянутої раніше, до простих чисел певного виду. Просте число <math>l</math> називається простим числом Елкіса, якщо характеристичне рівняння <math>\phi^2-t\phi+ q = 0</math> розкладається над <math>\mathbb{F}_l</math>, а прості числа Аткіна&nbsp;– це прості числа, які не є простими Елкіса. Аткін показав як комбінувати інформацію, отриману з простих чисел Аткіна, з інформацією, отриманою з простих чисел Елкіса, щоб отримати більш ефективний алгоритм, який отримав назву [[алгоритм Шуфа — Елкіса — Аткіна]]. Перша задача, яку потрібно вирішити,&nbsp;– чи є задане просте число простим Аткіна, чи простим Елкіса. Для цього використовуються модулярні поліноми, які виникають при вивченні [[Модулярна форма|модулярних форм]] та інтерпретації [[Еліптична крива|еліптичних кривих над полем комплексних чисел]] як решіток. Після того, як визначимо, у якому випадку перебуваємо, замість того, щоб використовувати поліноми ділення, ми зможемо працювати з поліномами, які мають нижчий степінь, ніж відповідні поліноми ділення: <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> при використанні швидкої арифметики. Хоч це евристичне припущення вірне для багатьох еліптичних кривих, але невідомо чи воно виконується в загальному випадку, навіть при істинності [[Узагальнені гіпотези Рімана|узагальненої гіпотези Рімана]].

== Джерела ==
* 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|url=https://web.archive.org/web/20210304070259/http://www.mat.uniroma2.it/~schoof/ctpts.pdf |date=4 березня 2021 }}
* 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|url=https://web.archive.org/web/20210127080935/http://www.mat.uniroma2.it/~schoof/ctg.pdf |date=27 січня 2021 }}
* G. Musiker: Schoof's Algorithm for Counting Points on <math>E(\mathbb{F}_{q})</math>. Available at http://www.math.umn.edu/~musiker/schoof.pdf {{Webarchive|url=https://web.archive.org/web/20160303190701/http://www.math.umn.edu/~musiker/schoof.pdf |date=3 березня 2016 }}
* 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|url=https://web.archive.org/web/20200728080414/http://lecturer.ukdw.ac.id/vmueller/publications.php |date=28 липня 2020 }}
* 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

{{Алгоритми теорії чисел}}
[[Категорія:Теорія чисел]]
[[Категорія:Алгоритми теорії чисел]]
[[Категорія:Еліптичні криві]]
[[Категорія:1985 у науці]]