solinas prime

Número primo de la forma que permite una rápida reducción modular.

En matemáticas , un primo de Solinas, o primo de Mersenne generalizado , es un número primo que tiene la forma , donde es un polinomio de bajo grado con coeficientes enteros pequeños . ^{[1] [2]} Estos números primos permiten algoritmos de reducción modular rápidos y se utilizan ampliamente en criptografía . Llevan el nombre de Jerónimo Solinas. ${\displaystyle f(2^{m})}$ ${\displaystyle f(x)}$

Esta clase de números abarca algunas otras categorías de números primos:

• Primos de Mersenne , que tienen la forma , ${\displaystyle 2^{k}-1}$
• Primos de Crandall o pseudo-Mersenne, que tienen la forma de impares pequeños . ^[3] ${\displaystyle 2^{k}-c}$ ${\displaystyle c}$

Algoritmo de reducción modular

Sea un polinomio mónico de grado con coeficientes en y supongamos que es un primo de Solinas. Dado un número con hasta bits, queremos encontrar un número congruente con mod solo con tantos bits como , es decir, con como máximo bits. ${\displaystyle f(t)=t^{d}-c_{d-1}t^{d-1}-...-c_{0}}$ ${\displaystyle d}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle p=f(2^{m})}$ ${\displaystyle n<p^{2}}$ ${\displaystyle 2md}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle md}$

Primero, representa en base : ${\displaystyle n}$ ${\displaystyle 2^{m}}$

${\displaystyle n=\sum _{j=0}^{2d-1}A_{j}2^{mj}}$

A continuación, genere una matriz por pasos multiplicando por el registro de desplazamiento de retroalimentación lineal definido por el polinomio : comenzando con el registro entero , desplace una posición hacia la derecha, inyectando a la izquierda y sumando (por componentes) el valor de salida multiplicado por el vector en cada paso (ver [1] para más detalles). Sea el número entero en el registro ésimo en el paso ésimo y tenga en cuenta que la primera fila de está dada por . Entonces si denotamos por el vector entero dado por: ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle X=(X_{i,j})}$ ${\displaystyle d}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle f}$ ${\displaystyle d}$ ${\displaystyle [0|0|...|0|1]}$ ${\displaystyle 0}$ ${\displaystyle [c_{0},...,c_{d-1}]}$ ${\displaystyle X_{i,j}}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle X}$ ${\displaystyle (X_{0,j})=[c_{0},...,c_{d-1}]}$ ${\displaystyle B=(B_{i})}$

${\displaystyle (B_{0}...B_{d-1})=(A_{0}...A_{d-1})+(A_{d}...A_{2d-1})X}$,

se puede comprobar fácilmente que:

${\displaystyle \sum _{j=0}^{d-1}B_{j}2^{mj}\equiv \sum _{j=0}^{2d-1}A_{j}2^{mj}\mod p}$.

Por tanto, representa un número entero de bits congruente con . ${\displaystyle B}$ ${\displaystyle md}$ ${\displaystyle n}$

Para elecciones juiciosas (nuevamente, ver [1]), este algoritmo implica solo un número relativamente pequeño de sumas y restas (¡y ninguna división!), por lo que puede ser mucho más eficiente que el ingenuo algoritmo de reducción modular ( ). ${\displaystyle f}$ ${\displaystyle n-p\cdot (n/p)}$

Ejemplos

Cuatro de los números primos recomendados en el documento del NIST "Curvas elípticas recomendadas para uso del gobierno federal" son primos de Solinas:

• p-192 ${\displaystyle 2^{192}-2^{64}-1}$
• p-224 ${\displaystyle 2^{224}-2^{96}+1}$
• p-256 ${\displaystyle 2^{256}-2^{224}+2^{192}+2^{96}-1}$
• p-384 ${\displaystyle 2^{384}-2^{128}-2^{96}+2^{32}-1}$

Curve448 utiliza la prima de Solinas ${\displaystyle 2^{448}-2^{224}-1.}$

Ver también

• Mersenne prima

Referencias

1. Solinas, Jerome A. (1999). Números generalizados de Mersenne (PDF) (Informe técnico). Centro de Investigación Criptográfica Aplicada, Universidad de Waterloo. CORR-99-39.
2. Solinas, Jerome A. (2011). "Mersenne Prime generalizado". En Tilborg, furgoneta Henk CA; Jajodia, Sushil (eds.). Enciclopedia de Criptografía y Seguridad . Springer Estados Unidos. págs. 509–510. doi :10.1007/978-1-4419-5906-5_32. ISBN 978-1-4419-5905-8.
3. Patente estadounidense 5159632, Richard E. Crandall, "Método y aparato para el intercambio de claves públicas en un sistema criptográfico", emitida el 27 de octubre de 1992, asignada a NeXT Computer, Inc.