Решето поля функцій

У математиці Решето поля функцій — один з найефективніших алгоритмів для розв'язання задачі дискретного логарифмування в скінченному полі. Він працює за еврістичний субекспоненційний час. Леонард Адлеман розробив його 1994 року, а згодов розробив його разом з М. Д. Хуангом 1999 року. Попередня робота включає роботу Д. Копперсміта про задачу дискретного логарифмування у полях характеристики два.

Задача дискретного логарифмування в скінченному полі полягає в розв'язуванні рівняння $a^{x}=b$ при $a,b\in \mathbb {F} _{p^{n}}$, простого числа $p$ та $n\in \mathbb {N}$. Функція $f\colon \mathbb {F} _{p^{n}}\to \mathbb {F} _{p^{n}},\ a\mapsto a^{x}$ при фіксованому $x\in \mathbb {N}$ є односторонньою функцією, яка застосовується в криптографії. Кілька криптографічних методів ґрунтуються на задачі дискретного логарифмування, як-от: Протокол Діффі-Геллмана, схема Ель-Гамаля та DSA (алгоритм цифрового підпису).

Теоретичне підґрунтя числа

Поля функцій

Нехай $C(x,y)$ — многочлен, що визначений на алгебраїчній кривій над скічненним полем $\mathbb {F} _{p}$. Поле функцій можна розглядати як поле часток кільця афінних координат $\mathbb {F} _{p}[x,y]/(C(x,y))$, де $(C(x,y))$ — ідеал, породжений $C(x,y)$. Це частинний випадок поля алгебраїчної функції. Він визначений над скінченним полем $\mathbb {F} _{p}$ та має степінь трансцендентності один. Трансцендентний елемент позначають за $x$.

Існує бієкція як між кільцями нормувань в полях функцій та класами еквівалентності місць, так і між кільцями нормувань та класами еквівалетності нормувань. Ця відповідність часто використовується в алгоритмі решета поля функцій.

Дільники

Дискретне нормування поля функцій $K/\mathbb {F} _{p}$, а саме дискретне кільце нормувань $\mathbb {F} _{p}\subset O\subset K$, має єдиний максимальний ідеал $P$, який називають простим ідеалом поля функцій. Степенем $P$ є $\deg(P)=[O/P:\mathbb {F} _{p}]$, надалі позначимо $f_{O}=[O/P:\mathbb {F} _{p}]$.

Дільником називають $\mathbb {Z}$-лінійну комбінацію всіх простих ідеалів, тобто ${\textstyle d=\sum \alpha _{P}P}$, де $\alpha _{P}\in \mathbb {Z}$ та лише скінченне число ненулевих елементів суми. Дільник елемента $x\in K$ визначається як ${\textstyle {\text{div}}(x)=\sum v_{P}(x)P}$, де $v_{P}$ — нормування, що відповідає простому ідеалу $P$. Степенем дільника є ${\textstyle \deg(d)=\sum \alpha _{P}\deg(P)}$.

Спосіб

Алгоритм решета поля функцій складається з попереднього обчислення, де знаходять дискретні логарифми незвідних многочленів малого степеня, і кроку зведення, на якому вони об'єднуються до логарифму $b$.

Функції, які розкладаються на незвідні функції степенів, менші за деяку межу $B$, називаються $B$-гладкими. Це аналогічно визначенню гладкого числа. Такі функції корисні, оскільки їхнє розкладання можна знайти відносно швидко. Набір цих функцій $S=\{g(x)\in \mathbb {F} _{p}[x]\mid g$ незвідні, $\deg(g)<B\}$ називається розкладеною основою.

Пара функцій $(r,s)$ називається подвійно гладкою, якщо $rm+s,\ N(ry+s)$ — обидва гладкі, де $N(\cdot ,\cdot )$ — норма елемента $K$ над полем $\mathbb {F} _{p}$, $m\in \mathbb {F} _{p}[x]$ — деякий параметр та $ry+s$ розгладється як елемент поля функцій $C$.

Крок просіювання алгоритму полягає у знаходженні подвійно гладких пар функцій. На наступному кроці ми використовуємо їх, щоб знайти лінійні співвідношення, включаючи логарифми функцій у розкладах. Розв'язуючи лінійну систему, ми обчислюємо логарифми. На кроці зведення ми виражаємо $\log _{a}(b)$ як комбінацію логарифмів, знайдених раніше. Таким чином розв'язуємо задачу дискретного логарифмування.

Попереднє обчислення

Вибір параметрів

Даний алгоритм вимагає таких параметрів: незвідна функція $f$ степені $n$, функція $m\in \mathbb {F} _{p}[x]$ та така крива $C(x,y)$ заданого степеня $d$, що $C(x,m)\equiv 0{\text{ mod }}f$. Тут $n$ — степінь в порядку основного поля $\mathbb {F} _{p^{n}}$. Позначимо $K$ за поле функцій, визначений на $C$.

Це приводить до ізоморфізму $\mathbb {F} _{p^{n}}\simeq \mathbb {F} _{p}[x]/f$ та гомоморфізму $\phi \colon \mathbb {F} _{p}[x,y]/C\to \mathbb {F} _{p}[x]/f,\ y\mapsto m.$ Використовуючи ізоморфізм, кожний елемент $\mathbb {F} _{p^{n}}$ можна розглянути як многочлен в $\mathbb {F} _{p}[x]/f$.

Також необхідно покласти межу гладкості $B$ для розкладеної основи $S$.

Просіювання

На цьому кроці подвійно гладкі пари функцій $(r,s)\in \mathbb {F} _{p}[x]\times \mathbb {F} _{p}[x]$ знайдені.

Розглядаються функції вигляду $f=(rm+s)N(ry+s)$, потім ділить $f$ на будь-яку $g\in S$ стільки разів, скільки можливо. Кожна $f$, яка зменшується до одиниці в даному процесі, є $B$-гладкою. Щоб реалізувати це, можна використовувати код Грея для ефективного проходження кратних даного многочлена.

Це повністю аналогічно етапу просіювання в інших алгоритмах решета, таких як решето поля чисел або алгоритм обчислення порядку. Замість чисел можна просіювати функції в $\mathbb {F} _{p}[x]$, але ці функції можна розкласти на незвідні многочлени так само, як числа можна розкласти на прості множники.

Знаходження лінійних співвідношень

Це найскладніша частина алгоритму, яка включає поля функцій, місця та дільники, визначені вище. Мета полягає в тому, щоб використовувати подвійно гладкі пари функцій для знаходження лінійних співвідношень, що містять дискретні логарифми елементів у розкладеній основі.

Для кожної незвідної функції в розкладеній основі знаходимо місця $v_{1},v_{2},...$ поля $K$, які які лежать над ними, та сурогатні функції $\alpha _{1},\alpha _{2},...$, що відповідають цим місцям. Сурогатна функція $\alpha _{i}\in K$, яка відповідає місцю $v_{i}$, задовольняє рівність ${\text{div}}(\alpha _{i})=h(v_{i}-f_{v_{i}}u)$, де $h$ — це номер класу $K$ та $u$ — будь-яке фіксоване дискретне нормування з $f_{u}=1$. Функція, визначена таким чином, єдина з точністю до константи в $\mathbb {F} _{p}$.

За означенням дільника ${\textstyle {\text{div}}(ry+s)=\sum a_{i}v_{i}}$ for $a_{i}=v_{i}(ry+s)$. Використовуючи це і те, що ${\textstyle \sum a_{i}f_{v_{i}}=\deg({\text{div}}(ry+s))=0}$, отримуємо такий вираз:

${\text{div}}((ry+s)^{h})=\sum ha_{i}v_{i}=\sum ha_{i}v_{i}-\sum ha_{i}f_{v_{i}}v+hv\sum a_{i}f_{v_{i}}=\sum a_{i}h(v_{i}-f_{v_{i}}v))={\text{div}}(\prod \alpha _{i}^{a_{i}})$,

де $v$ — будь-яке нормування with $f_{v}=1$. Далі, використовуючи той факт, що дільник сурогатної функції єдині з точністю до константи, отримуємо

$(ry+s)^{h}=c\prod \alpha _{i}^{a_{i}}$ для деякого $c\in \mathbb {F} _{p}^{*}$

$\implies \phi ((ry+s)^{h})=\phi (c)\prod \phi (\alpha _{i})^{a_{i}}$

Тепер ми використовуємо той факт, що $\phi (ry+s)=rm+s$, і відомий розклад цього виразу на незвідні многочлени. Нехай $e_{g}$ буде степенем $g\in S$ у цьому розкладанні. Тоді

$\prod _{g\in S}g^{he_{g}}\equiv \phi (c)\prod \phi (\alpha _{i})^{a_{i}}{\text{ mod }}f$

Тут ми можемо взяти дискретний логарифм рівняння з точністю до оборотного елементу. Це називається обмеженим дискретним логарифмом $\log _{*}(x)$. Він визначається рівнянням $a^{\log _{*}(x)}=ux$ для деякого оборотного $u\in \mathbb {F} _{p}$.

$\sum _{g\in S}e_{g}\log _{*}g\equiv \sum a_{i}h_{1}\log _{*}(\phi (\alpha _{i})){\text{ mod }}(p^{n}-1)/(p-1),$,

де $h_{1}$ є оберненим до $h$ за модулем $(p^{n}-1)/(p-1)$.

Вирази $h_{1}\log _{*}(\phi (\alpha _{i}))$ та логарифми $\log _{*}(g)$ невідомі. Коли знайдено достатньо рівнянь цієї форми, можна розв'язати лінійну систему $\log _{*}(g)$ для кожного $g\in S$. Узявши весь вираз $h_{1}log_{*}(\phi (\alpha _{i}))$ за невідому, ми можемо виграти час, оскільки $h$, $h_{1}$, $\alpha _{i}$ or $\phi (\alpha _{i})$ не потрібно обчислювати. Зрештою, для кожного $g\in S$ можна обчислити оборотний елемент, що відповідає обмеженому дискретному логарифму, який потім дає $\log _{a}(g)=\log _{*}(g)-\log _{a}(u)$.

Крок зведення

Спочатку $a^{l}b$ mod $f$ обчислюються для випадкового $l<n$. При достатньо високій ймовірності це буде ${\sqrt {nB}}$-гладкою, тому це можна розкласти як $a^{l}b=\prod b_{i}$ for $b_{i}\in \mathbb {F} _{p}[x]$ з $\deg(b_{i})<{\sqrt {nB}}$. Кожний з цих многочленів $b_{i}$ можна звести до многочлена меншого степеня за допомогою узагальненого метода Копперсміта. Ми можемо зменшувати степінь, поки не отримаємо добуток $B$-гладких многочленів. Потім, беручи логарифм за основою $a$, ми можемо зрештою обчислити

$\log _{a}(b)=\sum _{g_{i}\in S}\log _{a}(g_{i})-l$, що розв'язує задачу дискретного логарифмування.

Складність

Вважається, що решето поля функцій працює за субекспоненційний час

$\exp \left(\left({\sqrt[{3}]{\frac {32}{9}}}+o(1)\right)(\ln p)^{\frac {1}{3}}(\ln \ln p)^{\frac {2}{3}}\right)=L_{p}\left[{\frac {1}{3}},{\sqrt[{3}]{\frac {32}{9}}}\right]$,

використовуючи L-нотацію. Немає строгого доведення цієї складності, оскільки вона ґрунтується на деяких евристичних припущеннях. Наприклад, на етапі просіювання ми припускаємо, що числа у вигляді $(rm+s)N(ry+s)$ поводяться як випадкові числа в заданому діапазоні.

Порівняння з іншими способами

Існують два інших добре відомих алгоритми, які розв'язують задачу дискретного логарифмування за субекспоненційний час: алгоритм обчилення порядку та решето поля чисел. У своїх найпростіших формах обидва розв'язують задачу дискретного логарифмування в скінченних полях простого порядку, але їх можна розширити, щоб розв'язати задачу також у $\mathbb {F} _{p^{n}}$.

Решето поля чисел для задачі дискретного логарифмування у $\mathbb {F} _{p^{n}}$ має складність $L_{p}[1/3,(64/9)^{1/3}+o(1)]$ і тому трохи повільніше, ніж найкраща робота решета поля функцій. Однак це швидше за решето поля функцій при $n\ll (\log(p))^{1/2}$. Не дивно, що існує два схожі алгоритми, один з числовими полями, а інший з функціональними полями. Насправді між цими двома видами глобальних полів існує широка аналогія.

Алгоритм обчилення порядку набагато легше сформулювати, ніж решето поля функцій та решето поля чисел, оскільки він не включає жодних розширених алгебраїчних структур. Це асимптотично повільніше зі складністю $L_{p}[1/2,{\sqrt {2}}]$. Основна причина, чому решето поля чисел та решето поля функцій швидші, полягає в тому, що ці алгоритми можуть працювати з меншою межею гладкості $B$, тому більшість обчислень можна виконувати з меншими числами.

Див. також

• Алгебраїчне поле функцій
• Решето поля чисел
• Алгоритм обчислення порядку