Функциональное поле сита

В математике « Решето функционального поля» — один из наиболее эффективных алгоритмов решения задачи дискретного логарифмирования (DLP) в конечном поле . Он имеет эвристическую субэкспоненциальную сложность. Леонард Адлеман разработал его в 1994 году. а затем разработал его вместе с доктором медицинских наук Хуангом в 1999 году. Предыдущая работа включает работы Д. Копперсмита. о DLP в полях характеристики два.

Задача дискретного логарифмирования в конечном поле состоит из решения уравнения $a^{x}=b$ для $a,b\in \mathbb {F} _{p^{n}}$, $p$ простое число и $n$ целое число. Функция $f:\mathbb {F} _{p^{n}}\to \mathbb {F} _{p^{n}},a\mapsto a^{x}$ за фиксированную $x\in \mathbb {N}$ — это односторонняя функция, используемая в криптографии . На DLP основано несколько криптографических методов, таких как обмен ключами Диффи-Хеллмана , криптосистема Эль-Гамаля и алгоритм цифровой подписи .

Теоретические основы чисел

Функциональные поля

Основная статья: Поле алгебраической функции

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

Существуют биекции между кольцами нормирования в функциональных полях и классами эквивалентности мест , а также между кольцами нормирования и классами эквивалентности нормирований . Это соответствие часто используется в алгоритме Function Field Sieve.

Делители

Дискретная оценка функционального поля $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)}$.

Метод

Алгоритм Function Field Sieve состоит из предварительного вычисления, на котором находятся дискретные логарифмы неприводимых многочленов малой степени, и этапа приведения, на котором они объединяются с логарифмами $b$.

Функции, которые разлагаются в неприводимую функцию степени, меньшей некоторой границы $B$ называются $B$-гладкий. Это аналогично определению гладкого числа , и такие функции полезны, поскольку их разложение можно найти относительно быстро. Набор этих функций $S=\{g(x)\in \mathbb {F} _{p}[x]\mid {\text{ irreductible with }}\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)$ как комбинацию логарифма, который мы нашли ранее, и таким образом решить DLP.

Предварительные вычисления

Выбор параметров

Алгоритму необходимы следующие параметры: неприводимая функция $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 :\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}}$ для $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$ какая-либо оценка с $f_{v}=1$. Затем, используя тот факт, что делитель суррогатной функции уникален с точностью до константы, получаем

$(ry+s)^{h}=c\prod \alpha _{i}^{a_{i}}{\text{ for some }}c\in 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}$ или $\phi (\alpha _{i})$ не обязательно вычислять.В конце концов для каждого $g\in S$ можно вычислить единицу, соответствующую ограниченному дискретному логарифму, что затем дает $\log _{a}(g)=\log _{*}(g)-\log _{a}(u)$.

Шаг уменьшения

Первый $a^{l}b$ против $f$ рассчитываются случайным образом $l<n$. С достаточно большой вероятностью это ${\sqrt {nB}}$-гладкий, поэтому его можно рассматривать как $a^{l}b=\prod b_{i}$ для $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$, который решает проблему DLP.

Сложность

Считается, что сито функционального поля работает за субэкспоненциальное время .

$\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)$ ведут себя как случайные числа в заданном диапазоне.

Сравнение с другими методами

Есть два других хорошо известных алгоритма, которые решают задачу дискретного логарифма за субэкспоненциальное время : алгоритм исчисления индексов и версия сита числового поля . В своих самых простых формах оба решают задачу DLP в конечном поле простого порядка, но их можно расширить для решения задачи DLP в $\mathbb {F} _{p^{n}}$ также.

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

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

См. также

• Поле алгебраической функции
• Числовое поле сита
• Алгоритм расчета индекса