En matemáticas , una base polinomial es la base de un anillo polinomial , visto como un espacio vectorial sobre el campo de coeficientes, o como un módulo libre sobre el anillo de coeficientes. La base polinomial más común es la base monomial que consta de todos los monomios . Otras bases polinomiales útiles son la base de Bernstein y las diversas secuencias de polinomios ortogonales .
En el caso de una extensión finita de un campos finitos , base polinomio también puede referirse a una base de la extensión de la forma
donde α es la raíz de un polinomio primitivo de grado m igual al grado de extensión. [1]
El conjunto de elementos de GF ( p m ) se puede representar como:
usando los logaritmos de Zech .
Adición
La suma usando la base polinomial es tan simple como la suma módulo p . Por ejemplo, en GF (3 m ):
En GF (2 m ), la suma es especialmente fácil, ya que la suma y la resta módulo 2 son lo mismo (por lo que los términos similares se "cancelan") y, además, esta operación se puede realizar en hardware utilizando la puerta lógica XOR básica .
Multiplicación
La multiplicación de dos elementos en la base del polinomio se puede lograr de la forma normal de multiplicación, pero hay varias formas de acelerar la multiplicación, especialmente en hardware. El uso del método sencillo para multiplicar dos elementos en GF ( p m ) requiere hasta m 2 multiplicaciones en GF ( p ) y hasta m 2 - m adiciones en GF ( p ).
Algunos de los métodos para reducir estos valores incluyen:
- Tablas de búsqueda: una tabla de resultados almacenada previamente; Se utiliza principalmente para campos pequeños, de lo contrario, la tabla es demasiado grande para implementar
- El algoritmo de Karatsuba : divide repetidamente la multiplicación en pedazos, disminuye el número total de multiplicaciones pero aumenta el número de sumas. Como se vio anteriormente, la adición es muy simple, pero la sobrecarga de descomponer y recombinar las partes lo hace prohibitivo para el hardware, aunque a menudo se usa en software. Incluso se puede utilizar para la multiplicación general y se realiza en muchos sistemas de álgebra informática .
- Multiplicación basada en registro de desplazamiento de retroalimentación lineal
- Cálculos de subcampo : dividiendo la multiplicación en GF ( p m ) a multiplicaciones en GF ( p x ) y GF ( p y ), donde x × y = m . Esto no se utiliza con frecuencia con fines criptográficos, ya que algunos campos de grados compuestos se evitan debido a ataques conocidos sobre ellos.
- Multiplicadores canalizados: almacenar resultados intermedios en búferes para que los nuevos valores se puedan cargar en el multiplicador más rápido
- Multiplicadores sistólicos: utilizan muchas células que se comunican solo con las células vecinas; Por lo general, los dispositivos sistólicos se utilizan para operaciones de cálculo intensivo en las que los tamaños de entrada y salida no son tan importantes, como la multiplicación.
Cuadratura
El cuadrado es una operación importante porque se puede utilizar para exponenciación general, así como para la inversión de un elemento. La forma más básica de elevar al cuadrado un elemento en la base del polinomio sería aplicar un algoritmo de multiplicación elegido en un elemento dos veces. En el caso general, se pueden realizar pequeñas optimizaciones, específicamente relacionadas con el hecho de que al multiplicar un elemento por sí mismo, todos los bits serán iguales. En la práctica, sin embargo, el polinomio irreducible para el campo se elige con muy pocos coeficientes distintos de cero, lo que hace que el cuadrado en base polinomial de GF (2 m ) sea mucho más simple que la multiplicación. [2]
Inversión
La inversión de elementos se puede lograr de muchas maneras, que incluyen:
- Tablas de búsqueda: una vez más, solo para campos pequeños; de lo contrario, la tabla es demasiado grande para la implementación
- Inversión de subcampos: resolviendo sistemas de ecuaciones en subcampos
- Cuadrado repetido y multiplicado, por ejemplo, en GF (2 m ), A −1 = A 2 m −2
- El algoritmo euclidiano extendido
- El algoritmo de inversión Itoh-Tsujii
Uso
La base polinomial se utiliza con frecuencia en aplicaciones criptográficas que se basan en el problema del logaritmo discreto , como la criptografía de curva elíptica .
La ventaja de la base polinomial es que la multiplicación es relativamente fácil. Por el contrario, la base normal es una alternativa a la base polinomial y tiene una multiplicación más compleja, pero el cuadrado es muy simple. Las implementaciones de hardware de la aritmética de base polinomial generalmente consumen más energía que sus contrapartes de base normal.
Referencias
- ^ Roman, Steven (1995). Teoría de campo . Nueva York: Springer-Verlag. ISBN 0-387-94407-9.
- ^ Huapeng, Wu (2001). "Sobre la complejidad de la cuadratura de base polinomial en F (2 m )". Áreas seleccionadas en criptografía: Séptimo taller internacional anual, SAC 2000, Waterloo, Ontario, Canadá, 14 al 15 de agosto de 2000 . Saltador. pag. 118.