Calcolatore Test di Miller-Rabin (Primalita')

Test di primalita' di Miller-Rabin: probabilistico multi-round con probabilità' errore (1/4)^k, deterministico per n<3.3e24, confronto con Fermat e Carmichael.

Parametri di calcolo
Scegli la variante del test.
Numero intero da testare (2 <= n <= 1e15 per calcolo JS esatto).
Base a per il testimone singolo. 2 e' la piu' usata.
Numero di testimoni casuali. Probabilita' di errore <= (1/4)^k.
Questo calcolatore ti è stato utile?

Il test di Miller-Rabin

Il test di primalita' di Miller-Rabin e' l'algoritmo più' usato al mondo per decidere se un numero naturale e' primo. Sviluppato da Gary Miller (1976) come algoritmo deterministico condizionato all'ipotesi di Riemann generalizzata, e modificato da Michael O. Rabin (1980) in forma probabilistica incondizionata, e' la base di ogni generazione di chiavi RSA, DSA, Diffie-Hellman e dei test di primalita' nelle librerie crittografiche di OpenSSL, GnuPG, Wolfram Mathematica, Python (sympy.isprime), Java (BigInteger.isProbablePrime).

L'algoritmo in breve

Dato n dispari > 3, scriviamo n − 1 = d · 2^s con d dispari. Per testare con la base a:

  1. Calcola x0 = ad mod n.
  2. Se x0 = 1 o x0 = n − 1, n probabilmente primo.
  3. Altrimenti calcola xi+1 = xi2 mod n per i = 0, ..., s − 2. Se qualche xi = n − 1, n probabilmente primo.
  4. Se nessuna condizione e' verificata, n e' sicuramente composto e a e' un testimone di compostezza.

Il test deriva dal fatto che, in ℤ/pℤ con p primo, gli unici quadrati non banali di 1 sono ±1. Trovare un b con b² ≡ 1 (mod n) ma b ≠ ±1 dimostra che n e' composto.

Le quattro modalita' del calcolatore

  1. Singolo test: esegue Miller-Rabin con una base specifica a e mostra tutti i passaggi intermedi. Utile per didattica.
  2. Multi-round casuale: esegue k round con basi casuali. Probabilità' di falso positivo (composto che passa il test) <= (1/4)k. Per k = 20: errore < 10-12.
  3. Deterministico: usa basi fisse {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} per garantire risultato deterministico per n < 3,317·1024 (Sorenson-Webster 2015). Più' veloce dell'algoritmo AKS.
  4. Confronto con Fermat: mostra come Miller-Rabin differenzia Carmichael da primi veri, dove Fermat fallisce.

Probabilità' di errore

Rabin (1980) dimostro' il teorema chiave: per ogni composto n, almeno 3/4 delle basi in [2, n − 2] sono testimoni di compostezza. Quindi un singolo round con base casuale ha probabilità' di errore <= 1/4 (se n e' composto, ha al massimo 1/4 di probabilità' di passare). Con k round indipendenti, errore <= (1/4)k. In pratica il rapporto e' molto più' favorevole: per quasi tutti i composti, più' del 99% delle basi sono testimoni, quindi l'errore reale e' molto più' piccolo del bound teorico.

Variante deterministica

Se si testa un insieme sufficientemente ricco di basi fisse, Miller-Rabin diventa deterministico per n limitato:

  • Per n < 2.047: basta testare a = 2.
  • Per n < 1.373.653: basta {2, 3}.
  • Per n < 9.080.191: {31, 73}.
  • Per n < 4.759.123.141: {2, 7, 61}.
  • Per n < 3,317·1024: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} (Sorenson-Webster 2015).

Per n più' grandi, Miller-Rabin rimane probabilistico ma con errore praticamente nullo per k = 20-40 round. Per certezza assoluta esiste l'algoritmo AKS (Agrawal-Kayal-Saxena 2002, complessità' O(log6+ε n)), ma e' molto più' lento di Miller-Rabin nella pratica.

I numeri di Carmichael

I numeri di Carmichael (scoperti nel 1910) sono composti che superano il test di Fermat per ogni base coprima con n. I primi sono:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, ...

Il 1729 e' il famoso numero di Hardy-Ramanujan, 561 = 3·11·17 il più' piccolo. Alford-Granville-Pomerance (1994) dimostrarono che ci sono infiniti Carmichael, ma sono rari: tra i primi 109 ce ne sono solo 2.163. Miller-Rabin li rileva correttamente proprio grazie al controllo dei quadrati non banali di 1.

Applicazioni pratiche

  • Generazione chiavi RSA: generazione di primi grandi (1024-2048 bit) testando candidati random con Miller-Rabin k = 40 round. Probabilità' di errore trascurabile (< 10-24).
  • TLS handshake: parametri Diffie-Hellman e curve ellittiche richiedono primi verificati.
  • Blockchain: generazione di chiavi per indirizzi Bitcoin, Ethereum usa Miller-Rabin su primi di curve ellittiche (secp256k1).
  • OpenSSL: BN_is_prime_ex() usa una combinazione di trial division + Miller-Rabin.
  • Python: sympy.isprime() e gmpy2.is_prime() implementano Miller-Rabin con varianti BPSW per velocità'.
  • Certificati digitali: CA devono verificare la primalita' dei numeri nella firma RSA dei certificati X.509.

Confronto con altri test

  • Trial division: test completo fino a √n. Esatto ma O(√n), troppo lento per n > 1012.
  • Fermat: O(log n) per round, ma ingannato dai Carmichael. Usato raramente da solo.
  • Solovay-Strassen (1977): simile a Miller-Rabin ma con simbolo di Legendre-Jacobi. Probabilità' di errore <= 1/2 per round, peggiore di Miller-Rabin.
  • Baillie-PSW (BPSW): combinazione di Miller-Rabin base 2 + test di Lucas. Nessun contresempio noto fino a 264, congetturato deterministico.
  • AKS (2002): primo test deterministico in tempo polinomiale. Complessità' O((log n)6+ε). Tempo reale su n da 100 cifre: ore.
  • ECPP (elliptic curve primality proving): produce certificato di primalita' verificabile. Complessità' O((log n)4), usato per record mondiali.

Aggiornato a luglio 2026

Domande frequenti

Cos'e il test di Miller-Rabin?

E l'algoritmo di primalita piu usato al mondo per decidere se un numero e primo. Sviluppato da Miller nel 1976 (deterministico sotto l'ipotesi di Riemann generalizzata) e reso probabilistico incondizionato da Rabin nel 1980, e velocissimo e affidabilissimo, alla base di RSA, TLS e delle criptovalute.

Come funziona l'algoritmo?

Per n dispari si scrive n-1 = d x 2^s con d dispari. Scelta una base a, si calcola x = a^d mod n: se x = 1 o x = n-1, n e probabilmente primo. Altrimenti si eleva ripetutamente al quadrato; se qualche valore diventa n-1, n e probabilmente primo, altrimenti e composto con testimone a.

Quali modalita offre il calcolatore?

Quattro: singolo round con una base scelta, multi-round con k testimoni casuali e stima dell'errore, test deterministico con basi fisse, e confronto diretto fra Fermat e Miller-Rabin. Ogni modalita segnala i numeri di Carmichael e mostra i passaggi dell'algoritmo.

Quanto e affidabile un test probabilistico?

Ogni round ha probabilita di errore al massimo 1/4 per un composto, e i round sono indipendenti: con k testimoni l'errore scende a (1/4)^k. Con 40 round (come in RSA) l'errore e sotto 10^-24, molto piu basso della probabilita che un raggio cosmico corrompa la memoria durante il calcolo.

Cos'e un numero di Carmichael?

E un numero composto che inganna il test di Fermat: soddisfa a^(n-1) congruo a 1 mod n per ogni base coprima con n, pur non essendo primo. I primi sono 561, 1105, 1729, 2465. Miller-Rabin non viene ingannato grazie al controllo delle radici quadrate non banali di 1.

Che differenza c'e con il test di Fermat?

Il test di Fermat verifica solo a^(n-1) congruo a 1 mod n e fallisce con i numeri di Carmichael. Miller-Rabin aggiunge il controllo che, elevando al quadrato, non appaia una radice non banale di 1 (diversa da +1 e -1). Questa condizione piu forte rende Miller-Rabin robusto dove Fermat sbaglia.

Il test puo essere deterministico?

Si. Per numeri sotto una soglia nota, testare un insieme fisso di basi garantisce un risultato certo: le basi {2,3,5,7,11,13,17,19,23,29,31,37} sono deterministiche per n < 3,3 x 10^24 (Sorenson-Webster 2015). Per n fino a 10^12 bastano {2,3,5,7,11}, per n fino a 10^9 bastano {2,7,61}.

Dove si usa Miller-Rabin?

Nella generazione di chiavi RSA (con circa 40 round), nello scambio di chiavi TLS e Diffie-Hellman, nelle curve ellittiche come secp256k1 di Bitcoin, e in librerie come OpenSSL, sympy e gmpy2. E il metodo standard perche combina velocita e affidabilita praticamente assoluta.

Formula

n - 1 = d · 2^s con d dispari. x = a^d mod n. Se x = 1 o n-1: probably_prime. Quadrati: se x^2 = 1 e x != ±1: composto.

Commenti (0)

Ancora nessun commento. Sii il primo!