Controllo della primalità
Verifica se un numero è primo e scopri esattamente perché: divisione di prova reale fino a √n per numeri piccoli e medi e una vera procedura dettagliata di Miller-Rabin per numeri di dimensioni crittografiche.
Risultato
Il controllo della primalità ti dice se un numero intero è primo e, a differenza della maggior parte dei calcolatori online, ti mostra l'algoritmo effettivo che lo ha dimostrato, non una tabella di ricerca memorizzata nella cache. Digita qualsiasi numero intero, positivo o negativo, piccolo o enorme, e lo strumento decide quale algoritmo reale eseguire in base alla sua dimensione.
Per i numeri inferiori a 10¹² (un trilione), esegue una vera e propria divisione di prova: a partire da 2, prova ogni candidato intero fino al minimo di √n come possibile divisore, fermandosi nel momento in cui uno si divide equamente (composito) o confermando che nessuno lo fa una volta che tutti i candidati fino a √n sono stati controllati (primo). Per conteggi enormi di candidati, la traccia mostrata è limitata ai primi ~18 tentativi più quello finale, con una nota onesta su quanti sono stati saltati sul display, ma ogni singolo candidato viene comunque effettivamente controllato dal codice, nessuno viene saltato nel calcolo.
Per i numeri pari o superiori a tale soglia (l'intervallo di dimensioni utilizzato nella crittografia) la divisione delle prove richiederebbe troppo tempo, quindi lo strumento passa al test di primalità di Miller-Rabin con un insieme fisso e deterministico di 13 testimoni principali (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Questo esatto set di testimoni è un risultato ben noto: non ha falsi positivi per qualsiasi n inferiore a 3.317.044.064.679.887.385.961.981 (circa 3,3 × 10²⁴), un limite stabilito dalla verifica computazionale (vedi Sorenson & Webster, 2015, e la tabella dei testimoni deterministici ampiamente riprodotta a cui appartiene). Al di sopra di tale limite viene comunque eseguito lo stesso test, ma lo strumento ti dice onestamente che la garanzia diventa probabilistica estremamente forte piuttosto che una certezza matematica.
La traccia Miller-Rabin scrive n − 1 = 2ˢ × d con d dispari, quindi percorre l'esponenziazione modulare reale di BigInt - quadrato e moltiplicazione, riducendo il modulo n ad ogni singolo passaggio 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 composizione se il numero risulta non essere primo. Tutto funziona localmente nel tuo browser: nessun server, nessuna API esterna, nessun dato lascia mai il tuo dispositivo.
I tuoi file e input non lasciano mai questo dispositivo. L'elaborazione viene eseguita completamente offline. Sicuro al 100%.
Formati e regole accettati
- Traccia della divisione di prova: candidati da 2 fino a √n, con il divisore che dimostra la compositività o la prova onesta della primalità '√n check, nessun divisore trovato'.
- Miller-Rabin deterministico con i primi 13 testimoni principali (da 2 a 41) - dimostrato corretto sotto 3.317.044.064.679.887.385.961.981 (≈3,3 × 10²⁴).
- Una vera traccia di esponenziazione modulare quadrata e moltiplicativa BigInt, bit per bit, in modo da poter vedere a(^d) mod n effettivamente calcolato.
Vantaggi principali
Casi d'uso
- • Verifica la primalità di un numero per un compito a casa di matematica o di informatica discreto mentre vedi l'effettiva divisione di prova o i passaggi Miller-Rabin, non solo una risposta sì/no.
- • Controlla l'integrità di un grande candidato primo mentre apprendi come RSA e altri sistemi crittografici si basano sul vero algoritmo Miller-Rabin, con l'esponenziazione modulare tracciata bit per bit.
- • Conferma rapidamente se un numero specifico che continua ad apparire in un puzzle o in una serie di problemi è primo prima di costruire ulteriore logica su tale presupposto.
Valuta questo strumento
