Algoritmo di controllo di primalità

Question

Il controllo di primalità è probabilmente uno di "quei" difficili problemi in matematica. Quindi, qual è l'algoritmo migliore e più veloce disponibile per verificare la primalità di un numero enorme. Il più grezzo e il modo più lento probabilmente è:

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

Recentemente ho letto che l'algoritmo RSA 768-bit è stato craccato usando la forza bruta, utilizzando una matrice di grid computing. Come eseguono la forza bruta su un enorme numero primo? Ogni unità di elaborazione prende una serie di numeri, lo calcola e controlla la primalità di tutto il numero che si trova in quell'intervallo?

Answer 1

Partenza primality tests su Wikipedia per informazioni sulle attuali algoritmi

Per quanto riguarda l'implementazione ingenuo, non notare che si può immediatamente restituire false se il numero è divisibile per 2, che consente di controllare proprio strano numeri. Inoltre, se non trovi un fattore in cui x < = sqrt (i), è primo. Questo perché se hai trovato un fattore più grande di sqrt (i), allora deve essere associato a un fattore più piccolo di sqrt (i). Quindi se non trovi prima quel fattore più piccolo, hai finito.

C'è anche altro paio di trucchi che si possono applicare a un algoritmo ingenuo prima di dover andare trooping off per https://mathoverflow.net/ aiuto :)

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

Suppongo che ci sia un qualche tipo di distribuzione del carico di lavoro, ma dubito che hanno usato tale un semplice algoritmo per il test di primalità. Forse hanno usato il number field sieve o Lenstra's elliptic curve factorization.

Answer 4

Questo dovrebbe essere un po 'più veloce:

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 non coinvolgere direttamente qualsiasi algoritmo di controllo di primalità, piuttosto quello che ci voleva era un algoritmo di fattorizzazione: RSA-768 è il prodotto di due numeri primi molto grandi, e il cracking implica la ricerca di questi numeri primi.

L'algoritmo di fattorizzazione utilizzato era Number Field Sieve di Lenstra.

È possibile leggere l'intero articolo qui: Factorization of a 768-bit RSA modulus.

Answer 6

Test di primalità! = Fattorizzazione.

L'interruzione di una particolare chiave pubblica RSA e il recupero della chiave privata richiedono la fattorizzazione.

Il processo di costruzione di una coppia di chiavi pubbliche/private RSA include test di primalità. La maggior parte dei test di primalità non utilizzati per la fattorizzazione non produce una risposta definita al 100%, ma piuttosto è probabilistic con probabilità arbitrariamente alta (più iterazioni di test = maggiore probabilità).

E tecnicamente si può avere un deterministic primality test che è veloce e non comporta in realtà il calcolo di alcun fattore del numero in questione.

Answer 7

Suggerisco di utilizzare Fermat's Little Theorem. Valore di 'x' è primo if ((a^(x-1))% x) == 1.Dove 'un' è qualsiasi numero e 'x' non è uguale a 1, 0 o 2.