Test Miller–Rabin deterministico

Il test di Miller–Rabin deterministico decide se un intero n è primo eseguendo il test del testimone di primo probabilmente forte su un elenco breve e fisso di basi note per risolvere ogni intero sotto un limite di garanzia pubblicato. A differenza di un’esecuzione probabilistica di Miller–Rabin che estrae testimoni casuali e stima solo l’errore, questa capacità usa sempre le stesse basi, restituisce sempre lo stesso verdetto per lo stesso n e rifiuta l’ingresso che supera il limite in cui tali basi non sono più dimostrate sufficienti. Lei invia un unico intero almeno due e al più il limite, e riceve un indicatore di primalità, l’elenco dei testimoni, il limite stesso e—quando il numero è composto—il primo testimone che lo ha dimostrato.

Come funziona il test di primo probabilmente forte a basi fisse

Miller–Rabin riscrive un candidato dispari n come n meno uno uguale a d per due alla s con d dispari, poi per ogni testimone a calcola a elevato a d modulo n. Se quella potenza vale uno o n meno uno, il testimone passa. Altrimenti l’algoritmo eleva al quadrato il valore fino a s meno una volte e accetta il testimone solo se un quadrato intermedio vale n meno uno; qualsiasi altro percorso dimostra che n è composto per quella base.

Un numero che supera ogni testimone si dice primo probabilmente forte rispetto a quelle basi. Per insiemi fissi scelti con cura, risultati di teoria dei numeri mostrano che non esiste un composto sotto una soglia nota che inganni tutte le basi dell’insieme—così l’esito di primo probabilmente forte diventa un vero primo entro il limite. Questa capacità usa le sette basi due, tre, cinque, sette, undici, tredici e ventitré, sufficienti per ogni intero a sessantaquattro bit e quindi per ogni intero sicuro JavaScript fino a nove quadrilioni.

I primi minuscoli due e tre si risolvono come primi. Quando un testimone divide n ed è minore di n, quel testimone viene segnalato come base fallita perché n è un multiplo evidente.

Quando serve un test di primalità a basi fisse

I corsi di crittografia e i trainer CTF usano un test di Miller–Rabin deterministico per mostrare agli studenti la differenza tra controlli probabilistici con testimoni casuali e certificati a basi fisse che nominano il limite di garanzia nella risposta. Gli autori di librerie ancorano test unitari su primi noti, pseudoprimi forti e composti così un refactor dell’esponenziazione modulare non può invertire un verdetto in silenzio.

Gli sviluppatori di applicazioni convalidano valori di configurazione a forma di primo, semi di puzzle o parametri giocattolo Diffie–Hellman prima di una pipeline più lunga, catturando i pari e i piccoli composti senza erigere un sistema di algebra computazionale. Preferisca questo strumento quando l’intento di ricerca è specificamente l’algoritmo di Miller–Rabin deterministico con testimoni fissi e un limite rigido—non quando le serve il minimo divisore di un composto, la fattorizzazione prima completa, Lucas–Lehmer per i numeri di Mersenne o test probabilistici con un elenco di testimoni personalizzato che fornisce Lei.