¿Cómo se usan los primos de Mersenne?

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.

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?)

More Interesting

¿Cuál es el valor de [matemáticas] \ sum \ limits_ {k = 1} ^ {p-1} \ left (1-e ^ {\ frac {2k \ pi i} {p}} \ right) ^ {1- p} [/ math] donde [math] p [/ math] es primo?

¿Cuál es el resto cuando (2 ^ 100 + 3 ^ 100 + 4 ^ 100 5 ^ 100) se divide por 7?

¿Cuáles son las propiedades de los números primos y racionales?

¿Cuál es el teorema del resto chino y cómo se usa en la programación competitiva?

¿Cómo se descubren los números primos más grandes?

¿Es posible que la conjetura de Goldbach sea verdadera pero no demostrable?

¿Cuál es el resto cuando 9 ^ 17 se divide por 7?

Si abcde = a + b + c + d + e, ¿cuántos quíntuples ordenados (a, b, c, d, e) satisfacen la ecuación?

¿Me estoy perdiendo algo: son números pares 1346269 y 2178309?

¿Por qué tomó tanto tiempo demostrar la conjetura de que las matemáticas elípticas son duales a las matemáticas modulares?

Cómo evaluar la suma [matemáticas] \ sum_ {n = 1} ^ {\ infty} (- 1) ^ {n} \ frac {[\ log (2n + 1)] ^ 2} {2n + 1} [/ matemáticas]

Cómo demostrar que la diferencia entre cualquier número entero impar y cualquier número entero par es impar

Deje que [math] K [/ math] sea un campo. Considere [math] A = \ underset {\ mathbf {N} _0} {\ bigoplus} K [/ math] con una estructura aditiva natural. ¿Cómo encuentras que algunas o mejor describen todas las estructuras multiplicativas en [matemáticas] A [/ matemáticas] convirtiéndolas en un anillo conmutativo ([matemáticas] K [/ matemáticas] -álgebra) con identidad?

¿Por qué todos los enteros negativos más pequeños que los enteros positivos?

¿Por qué los matemáticos creían que el último teorema de Fermat era cierto cuando no había pruebas disponibles? Si Fermat no tenía pruebas, ¿cómo tuvo la idea de establecer un teorema que fuera realmente cierto y probado después de 300 años?