Test di Primalità
Verifica se un numero è primo e scopri esattamente perché: divisione per tentativi fino a √n per numeri piccoli e medi, e una dimostrazione autentica del test di Miller–Rabin per numeri di taglia crittografica.
🔒 Elaborato interamente nel tuo browser: nulla di ciò che inserisci qui verrà mai caricato.
Risultato
Il test di primalità ti dice se un intero è primo, e — a differenza della maggior parte dei calcolatori online — ti mostra l'algoritmo reale che lo ha dimostrato, non una tabella di lookup precalcolata. Inserisci un intero qualsiasi, positivo o negativo, piccolo o enorme, e lo strumento decide quale algoritmo reale eseguire in base alla sua dimensione.
Per numeri inferiori a 10¹² (un bilione), esegue una vera divisione per tentativi: partendo da 2, prova ogni intero candidato fino alla parte intera di √n come possibile divisore, fermandosi non appena uno divide esattamente (numero composto) oppure confermando che nessuno lo fa dopo aver controllato tutti i candidati fino a √n (numero primo). Per conteggi di candidati molto alti, la traccia mostrata è limitata ai primi 18 provati più l'ultimo, con un'onesta nota su quanti sono stati omessi nella visualizzazione — ma ogni singolo candidato viene comunque effettivamente verificato dal codice, nessuno viene saltato nel calcolo.
Per numeri pari o superiori a quella soglia — l'intervallo di dimensioni usato in crittografia — la divisione per tentativi impiegherebbe troppo tempo, quindi lo strumento passa al test di primalità di Miller–Rabin con un insieme fisso e deterministico di 13 numeri primi come testimoni (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Questo esatto insieme di testimoni è un risultato ben noto: non ha falsi positivi per alcun n inferiore a 3.317.044.064.679.887.385.961.981 (circa 3,3×10²⁴), un limite stabilito tramite verifica computazionale (si veda Sorenson & Webster, 2015, e la diffusissima tabella di testimoni deterministici di cui fa parte). Oltre quel limite, lo stesso test viene comunque eseguito, ma lo strumento ti avvisa onestamente che la garanzia diventa una garanzia probabilistica estremamente forte, non una certezza matematica.
La traccia di Miller–Rabin scrive n − 1 = 2ˢ × d con d dispari, poi percorre una vera esponenziazione modulare BigInt — square-and-multiply, riducendo modulo n a ogni singolo passo in modo che i numeri non esplodano mai — bit per bit per il primo testimone, e riporta il verdetto di ciascun testimone, incluso quale testimone dimostra la non primalità se il numero risulta non essere primo. Tutto viene eseguito localmente nel tuo browser: nessun server, nessuna API esterna, nessun dato lascia mai il tuo dispositivo.