Función tamiz de campo

En matemáticas, la Criba de Campo de Función es uno de los algoritmos más eficientes para resolver el Problema del Logaritmo Discreto (PLD) en un cuerpo finito . Tiene complejidad subexponencial heurística . Leonard Adleman lo desarrolló en 1994 ^[1] y luego lo elaboró ​​junto con MD Huang en 1999. ^[2] Trabajos previos incluyen el trabajo de D. Coppersmith ^[3] sobre el PLD en cuerpos de característica dos.

El problema del logaritmo discreto en un cuerpo finito consiste en resolver la ecuación para , un número primo y un entero. La función para un fijo es una función unidireccional utilizada en criptografía . Varios métodos criptográficos se basan en el DLP como el intercambio de claves Diffie-Hellman , el criptosistema El Gamal y el algoritmo de firma digital . ${\displaystyle a^{x}=b}$ ${\displaystyle a,b\in \mathbb {F} _{p^{n}}}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle f:\mathbb {F} _{p^{n}}\to \mathbb {F} _{p^{n}},a\mapsto a^{x}}$ ${\displaystyle x\in \mathbb {N} }$

Antecedentes de la teoría de números

Campos de función

Sea un polinomio que define una curva algebraica sobre un cuerpo finito . Un cuerpo de funciones puede verse como el cuerpo de fracciones del anillo de coordenadas afines , donde denota el ideal generado por . Este es un caso especial de un cuerpo de funciones algebraicas. Está definido sobre el cuerpo finito y tiene grado de trascendencia uno. El elemento trascendente se denotará por . ${\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}$

Existen biyecciones entre anillos de valoración en cuerpos de funciones y clases de equivalencia de lugares , así como entre anillos de valoración y clases de equivalencia de valoraciones . ^[4] Esta correspondencia se utiliza frecuentemente en el algoritmo Function Field Sieve.

Divisores

Una valoración discreta del campo de funciones , es decir, un anillo de valoración discreta , tiene un ideal máximo único llamado primo del campo de funciones. El grado de es y también definimos . ${\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}]}$

Un divisor es una combinación lineal sobre todos los primos, por lo que donde y solo un número finito de elementos de la suma son distintos de cero. El divisor de un elemento se define como , donde es la valoración correspondiente al primo . El grado de un divisor es . ${\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)}$

Método

El algoritmo Function Field Sieve consiste en un precálculo donde se encuentran los logaritmos discretos de polinomios irreducibles de pequeño grado y un paso de reducción donde se combinan al logaritmo de . ${\displaystyle b}$

Las funciones que se descomponen en funciones irreducibles de grado menor que algún límite se denominan -suaves. Esto es análogo a la definición de un número suave y dichas funciones son útiles porque su descomposición se puede encontrar relativamente rápido. El conjunto de esas funciones se denomina base de factores. Un par de funciones es doblemente suave si y son ambas suaves, donde es la norma de un elemento de sobre , es algún parámetro y se considera como un elemento del cuerpo de funciones de . ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle S=\{g(x)\in \mathbb {F} _{p}[x]\mid {\text{ irreductible with }}\deg(g)<B\}}$ ${\displaystyle (r,s)}$ ${\displaystyle rm+s}$ ${\displaystyle 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}$

El paso de cribado del algoritmo consiste en encontrar pares de funciones doblemente suaves. En el paso siguiente los usamos para encontrar relaciones lineales que incluyen los logaritmos de las funciones en las descomposiciones. Al resolver un sistema lineal, calculamos los logaritmos. En el paso de reducción, expresamos como una combinación del logaritmo que encontramos antes y, de esta manera, resolvemos el DLP. ${\displaystyle \log _{a}(b)}$

Precomputación

Selección de parámetros

El algoritmo requiere los siguientes parámetros: una función irreducible de grado , una función y una curva de grado dado tales que . Aquí está la potencia en el orden del cuerpo base . Sea , el cuerpo de función definido por . ${\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}$

Esto conduce a un isomorfismo y un homomorfismo. Usando el isomorfismo, cada elemento de puede considerarse como un polinomio en . ${\displaystyle \mathbb {F} _{p^{n}}\simeq \mathbb {F} _{p}[x]/f}$ $${\displaystyle \phi :\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}$

También es necesario establecer un límite de suavidad para el factor base . ${\displaystyle B}$ ${\displaystyle S}$

Tamizado

En este paso se encuentran pares de funciones doblemente suaves . ${\displaystyle (r,s)\in \mathbb {F} _{p}[x]\times \mathbb {F} _{p}[x]}$

Se consideran funciones de la forma , luego se dividen por cualquier tantas veces como sea posible. Cualquier que se reduzca a uno en este proceso es -suave. Para implementar esto, se puede utilizar el código Gray para recorrer de manera eficiente los múltiplos de un polinomio dado. ${\displaystyle f=(rm+s)N(ry+s)}$ ${\displaystyle f}$ ${\displaystyle g\in S}$ ${\displaystyle f}$ ${\displaystyle B}$

Esto es completamente análogo al paso de tamizado en otros algoritmos de tamizado como el tamiz de campo numérico o el algoritmo de cálculo de índices . En lugar de números, se tamizan funciones en , pero esas funciones se pueden factorizar en polinomios irreducibles, de la misma manera que los números se pueden factorizar en primos. ${\displaystyle \mathbb {F} _{p}[x]}$

Encontrar relaciones lineales

Esta es la parte más difícil del algoritmo, que involucra los campos de funciones, los lugares y los divisores definidos anteriormente. El objetivo es utilizar los pares de funciones doblemente suaves para encontrar relaciones lineales que involucren los logaritmos discretos de los elementos en la base de factores.

Para cada función irreducible en la base de factores encontramos lugares de que se encuentran sobre ellos y funciones sustitutas que corresponden a los lugares. Una función sustituta que corresponde a un lugar satisface donde es el número de clase de y es cualquier valoración discreta fija con . La función definida de esta manera es única hasta una constante en . ${\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}}$

Por la definición de divisor para . Utilizando esto y el hecho de que obtenemos la siguiente expresión: ${\textstyle {\text{div}}(ry+s)=\sum a_{i}v_{i}}$ ${\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}})}$

donde es cualquier valoración con . Entonces, utilizando el hecho de que el divisor de una función sustituta es único hasta una constante, se obtiene ${\displaystyle v}$ ${\displaystyle f_{v}=1}$

${\displaystyle (ry+s)^{h}=c\prod \alpha _{i}^{a_{i}}{\text{ for some }}c\in F_{p}^{*}}$

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

Ahora usamos el hecho de que y la descomposición conocida de esta expresión en polinomios irreducibles. Sea la potencia de en esta descomposición. Entonces ${\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}$

Aquí podemos llevar el logaritmo discreto de la ecuación hasta una unidad. Esto se llama logaritmo discreto restringido . Está definido por la ecuación para alguna unidad . ${\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),}$

donde es la inversa del módulo . ${\displaystyle h_{1}}$ ${\displaystyle h}$ ${\displaystyle (p^{n}-1)/(p-1)}$

Las expresiones y los logaritmos son desconocidos. Una vez que se encuentran suficientes ecuaciones de esta forma, se puede resolver un sistema lineal para encontrar para todos . Tomar toda la expresión como una incógnita ayuda a ganar tiempo, ya que , , o no tienen que calcularse. Finalmente, para cada uno se puede calcular la unidad correspondiente al logaritmo discreto restringido, lo que da . ${\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}}$ ${\displaystyle \phi (\alpha _{i})}$ ${\displaystyle g\in S}$ ${\displaystyle \log _{a}(g)=\log _{*}(g)-\log _{a}(u)}$

Paso de reducción

Primero se calculan los módulos para un polinomio aleatorio . Con una probabilidad suficientemente alta, este polinomio es -suave, por lo que se puede factorizar como para con . Cada uno de estos polinomios se puede reducir a polinomios de menor grado utilizando una generalización del método Coppersmith . ^[2] Podemos reducir el grado hasta que obtengamos un producto de polinomios -suaves. Luego, llevando el logaritmo a la base , podemos calcular eventualmente ${\displaystyle a^{l}b}$ ${\displaystyle f}$ ${\displaystyle l<n}$ ${\displaystyle {\sqrt {nB}}}$ ${\displaystyle a^{l}b=\prod b_{i}}$ ${\displaystyle b_{i}\in \mathbb {F} _{p}[x]}$ ${\displaystyle \deg(b_{i})<{\sqrt {nB}}}$ ${\displaystyle b_{i}}$ ${\displaystyle B}$ ${\displaystyle a}$

${\displaystyle \log _{a}(b)=\sum _{g_{i}\in S}\log _{a}(g_{i})-l}$, que resuelve el DLP.

Complejidad

Se piensa que la función Field Sieve se ejecuta en tiempo subexponencial 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]}$

utilizando la notación L. No existe una prueba rigurosa de esta complejidad ya que se basa en algunos supuestos heurísticos . Por ejemplo, en el paso de cribado asumimos que los números de la forma se comportan como números aleatorios en un rango dado. ${\displaystyle (rm+s)N(ry+s)}$

Comparación con otros métodos

Hay otros dos algoritmos bien conocidos que resuelven el problema del logaritmo discreto en tiempo subexponencial : el algoritmo de cálculo de índices y una versión de la criba de campo numérico . ^[5] En sus formas más sencillas, ambos resuelven el DLP en un campo finito de orden primo, pero se pueden expandir para resolver el DLP también. ${\displaystyle \mathbb {F} _{p^{n}}}$

El tamiz de campos numéricos para el DLP en tiene una complejidad de ^[6] y, por lo tanto, es ligeramente más lento que el mejor rendimiento del tamiz de campos de funciones. Sin embargo, es más rápido que el tamiz de campos de funciones cuando . No es sorprendente que existan dos algoritmos similares, uno con campos numéricos y el otro con campos de funciones. De hecho, existe una amplia analogía entre estos dos tipos de campos globales . ${\displaystyle \mathbb {F} _{p^{n}}}$ ${\displaystyle L_{p}[1/3,(64/9)^{1/3}+o(1)]}$ ${\displaystyle n<<(\log(p))^{1/2}}$

El algoritmo de cálculo de índices es mucho más fácil de enunciar que el tamiz de cuerpos de funciones y el tamiz de cuerpos de números, ya que no implica ninguna estructura algebraica avanzada. Es asintóticamente más lento con una complejidad de . La razón principal por la que el tamiz de cuerpos de números y el tamiz de cuerpos de funciones son más rápidos es que estos algoritmos pueden ejecutarse con un límite de suavidad más pequeño , por lo que la mayoría de los cálculos se pueden realizar con números más pequeños. ${\displaystyle L_{p}[1/2,{\sqrt {2}}]}$ ${\displaystyle B}$

Véase también

• Campo de funciones algebraicas
• Tamiz de campo numérico
• Algoritmo de cálculo de índices

Referencias

1. L. Adleman. "El tamiz de campo de funciones". En: Teoría algorítmica de números (ANTS-I). Apuntes de clase en informática. Springer (1994), pp.108-121.
2. L. Adleman, MD Huang. "Método de tamiz de campo de función para logaritmos discretos sobre campos finitos". En: Inf. Comput. 151 (mayo de 1999), págs. 5-16. DOI: 10.1006/inco.1998.2761.
3. D. Coppersmith. (1984), "Evaluación rápida de logaritmos discretos en campos de característica dos". En: IEEE Trans. Inform. Theory IT-39 (1984), págs. 587-594.
4. M. Fried y M. Jarden. En: "Field Arithmetic". vol. 11. (enero de 2005). Cap. 2.1. DOI: 10.1007/b138352.
5. D. Gordon. "Logaritmo discreto en GF(P) utilizando la criba del cuerpo numérico". En: Siam Journal on Discrete Mathematics - SIAMDM 6 (febrero de 1993), págs. 124-138. DOI: 10.1137/0406010.
6. R. Barbulescu, P. Gaudry, T. Kleinjung. "El tamiz de campo numérico de la torre". En: Advances in Cryptology – Asiacrypt 2015. Vol. 9453. Springer, mayo de 2015. págs. 31-58