Algoritmo de verificación de primalidad

Question

Primal Check es probablemente uno de "esos" problemas difíciles en matemáticas. Entonces, ¿cuál es el mejor y más rápido algoritmo disponible para verificar la primalidad de un gran número? El más crudo y la manera más lenta, probablemente es:

public static bool IsPrime(int i) 
{ 
    for (var x = 2; x < i - 1; i++) 
    { 
     if (i % x == 0) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

recientemente he leído que el algoritmo RSA de 768 bits se ha resquebrajado el uso de la fuerza bruta, usando una matriz de computación en red. ¿Cómo realizan la fuerza bruta en un enorme número primo? ¿Asume cada unidad de procesamiento una serie de números, factoriza y verifica la primalidad de todos los números que se encuentran en ese rango?

Answer 1

Salida primality tests en la Wikipedia para saber cómo dirigirse a los algoritmos actuales

Con respecto a su aplicación ingenua, tenga en cuenta que puede devolver inmediatamente falsa si el número es divisible por 2, lo que le permite simplemente comprueba extraña números. Además, si no encuentra un factor donde x < = sqrt (i), es primo. Esto se debe a que si encontró un factor mayor que sqrt (i), entonces debe asociarse con un factor menor que sqrt (i). Entonces, si primero no encuentras el factor más pequeño, terminaste.

También hay par más trucos que se pueden aplicar a un algoritmo ingenuo antes de tener que ir en tropel fuera a https://mathoverflow.net/ ayuda :)

Answer 2

public static bool IsPrime(int i) 
{ 
    for (var x = 2; x < (i/2); x++) 
    { 
     if (i % x == 0) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

Answer 3

supongo que hay algún tipo de distribución de la carga de trabajo, pero dudo que utilizan tales un algoritmo simple para la prueba de primalidad. Tal vez usaron el number field sieve o el Lenstra's elliptic curve factorization.

Answer 4

Esto debería ser un poco más rápido:

public static bool IsPrime(int i) {   
    // only go up to the root of i 
    // +1 to be save from floating point rounding errors, ceil should work too. 
    var max = sqrt(i) + 1; 

    // skip numbers dividable by 2, except 2 itself 
    if (i == 2) return true; 
    if (i % 2 == 0) return false; 
    for (var x = 3; x < max; x+=2) { 
     if (i % x == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

Answer 5

Cracking RSA-768 no implicar directamente a cualquier algoritmo de comprobación de primalidad, más bien lo que se necesitaba era un algoritmo factorización: RSA-768 es el producto de dos números primos muy grandes, y descifrarlo implica encontrar estos números primos. El algoritmo de factorización utilizado fue el Number Field Sieve de Lenstra.

Puede leer el artículo completo aquí: Factorization of a 768-bit RSA modulus.

Answer 6

Pruebas de primalización! = Factorización.

Romper una clave pública RSA en particular y recuperar la clave privada, requiere factorización.

El proceso de construcción de un par de claves pública/privada RSA incluye pruebas de primalidad. La mayoría de las pruebas de primalidad no utilizadas para la factorización no producen una respuesta 100% definitiva, sino que es probabilistic con una probabilidad arbitrariamente alta (más iteraciones de prueba = mayor probabilidad).

Y técnicamente puede tener un deterministic primality test que sea rápido y no implique realmente calcular ningún factor del número en cuestión.

Answer 7

Sugiero usar Fermat's Little Theorem. Valor de 'x' es primo si ((a^(x-1))% x) == 1.Donde 'a' es cualquier número y 'X' no es igual a 1, 0 o 2.