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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}})}$,

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

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

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

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

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

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

${\displaystyle \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),}$,

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

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

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

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

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

${\displaystyle \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-нотацію. Немає строгого доведення цієї складності, оскільки вона ґрунтується на деяких евристичних припущеннях. Наприклад, на етапі просіювання ми припускаємо, що числа у вигляді ${\displaystyle (rm+s)N(ry+s)}$ поводяться як випадкові числа в заданому діапазоні.

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

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

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

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