En matemáticas , un primo de Solinas, o primo de Mersenne generalizado, es un número primo que tiene la forma, dónde 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 .
Esta clase de números abarca algunas otras categorías de números primos:
- Primos de Mersenne , que tienen la forma,
- Crandall o pseudo-Mersenne primos, que tienen la forma por pequeños impares . [3]
Algoritmo de reducción modular
Dejar ser un polinomio monico de grado con coeficientes en y supongamos que es una prima de Solinas. Dado un número Con un máximo de bits, queremos encontrar un número congruente con modificación con solo tantos bits como - es decir, con como máximo bits.
Primero, representa en base :
A continuación, genere un -por- matriz al pisar veces el registro de desplazamiento de retroalimentación lineal definido sobre por el polinomio : comenzando con el -registro entero , cambia a la derecha una posición, inyectando a la izquierda y sumando (por componentes) el valor de salida multiplicado por el vector en cada paso (consulte [1] para obtener más detalles). Dejar ser el entero en el th registro en el el paso y tenga en cuenta que la primera fila de es dado por . Entonces, si denotamos por el vector entero dado por:
- ,
se puede comprobar fácilmente que:
- .
Por lo tanto representa un -bit entero congruente con .
Por decisiones juiciosas de (nuevamente, vea [1]), este algoritmo involucra solo un número relativamente pequeño de sumas y restas (¡y no divisiones!), por lo que puede ser mucho más eficiente que el algoritmo de reducción modular ingenuo ().
Ejemplos de primos de Solinas
Cuatro de los números primos recomendados en el documento del NIST "Curvas elípticas recomendadas para uso del gobierno federal" son números primos de Solinas:
- p-192
- p-224
- p-256
- p-384
Ver también
Referencias
- ^ Solinas, Jerome A. (1999). Números de Mersenne generalizados (PDF) (Informe técnico). Centro de Investigación Criptográfica Aplicada, Universidad de Waterloo. CORR-99-39.
- ^ Solinas, Jerome A. (2011). "Generalizado Mersenne Prime". En Tilborg, furgoneta de Henk CA; Jajodia, Sushil (eds.). Enciclopedia de Criptografía y Seguridad . Springer EE. UU. págs. 509 –510. doi : 10.1007 / 978-1-4419-5906-5_32 . ISBN 978-1-4419-5905-8.
- ^ 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.