¿Cómo se usan los primos de Mersenne?

Answer 1

La clave para los primos de Mersenne es que para cualquier valor p es muy fácil calcular x mod 2 ^ p-1, cuando p es un número primo, entonces 2 ^ p-1 es un primo de Mersenne. Por lo tanto, se usan siempre que encuentre estas condiciones:

1. Tienes que calcular x mod p muchas veces
2. p necesita ser un número primo
3. No tiene preocupaciones de seguridad acerca de que alguien adivine su número “p”

La condición 3 significa que el uso de primos de Mersenne para RSA es un gran no-no, pero eso no significa que no haya aplicaciones para los números de Mersenne.

Comenzaré a explicar por qué puedes calcular x mod p muy rápido cuando p es un Mersenne prime.

La clave es que puedes calcular x mod p realmente rápido si p es un Mersenne prime.

Imagine que estamos usando 31, que es M5 (2 ^ 5–1).

Queremos calcular 632 mod 31

632 en binario es 100111100, dividimos el número en grupos de 5 bits (porque estamos usando M5): 10011 y 11000, ahora agregamos esas partes:

10011 + 11000 = 101011 ya que el resultado es más largo que 5 bits repetimos:

010011 + 1 = 1100

Y 1100 es 12, entonces 632 mod 31 es 12

¡Observe que hemos calculado una operación de módulo solo haciendo adiciones!

Ahora algunas aplicaciones:

Hashing

Hashing es una aplicación para los primos de Mersenne.

Si tiene una función hash en forma de h (x) = f (x) mod p donde p es un número primo usando un primo de Mersenne puede acelerar el cálculo. La construcción Carter-Wegman para las familias de Universal Hashing puede usar esto.

Números seudoaleatorios

Los primos de Mersenne también se usan en el PRNG twister de Mersenne (generador de números pseudoaleatorios), estos se usan ampliamente en simulaciones, métodos de Montecarlo, etc.

Criptografía

El modo CWC para cifrados de bloque puede usar M127 como número primo porque x mod 2 ^ 127–1 es muy fácil de calcular.

En la criptografía de curva elíptica, GF (2 ^ 521–1) se usa ampliamente porque, una vez más, es muy fácil calcular x mod 2 ^ 521 – 1.

Answer 2

Los primos de Mersenne no se usan en la criptografía RSA.

Hacerlo sería un grave defecto de seguridad. Supongamos que queremos hacer una clave pública RSA de 4096 bits. Sabemos que esta clave es el producto de dos números primos. Digamos que sabíamos de antemano que uno de los primos es un primo de Mersenne. ¿Cuántos primos diferentes de Mersenne tienen la posibilidad de ser un factor de un entero de 4096 bits? La respuesta es simplemente 18 (Solo los primos de Mersenne [matemáticas] 2 ^ p-1 [/ matemáticas] donde [matemáticas] p <4096 [/ matemáticas]). Por lo tanto, podríamos intentar dividir la clave entre estos dieciocho números primos y factorizarlo, rompiendo RSA sin sudar.

Los números primos de Mersenne son de interés solo para matemáticos a quienes les gusta estudiar sus propiedades y para aquellos que intentan romper el récord del número primo más grande conocido. Aparte de eso, no hay aplicaciones prácticas (Edición: estaba equivocado sobre esto, vea la respuesta de Luis Argerich a ¿Cómo se usan los primos de Mersenne?)