Pseudoprimo forte

In rete: www.elegio.it/doc/tn/1976_gary-miller.html

Pseudoprimo forte: attualmente il modo più veloce per denunciare falsi numeri primi.

Uno pseudoprimo forte è un intero che si comporta in modo fortemente simile ad un numero primo quando si ricorre ad un determinato intero come base nelle operazioni di elevamento a potenza in algebra modulare. Lo pseudoprimo è forte nei confronti di quella base ma non necessariamente di tutte. Se lo è nei confronti di tutte, lo pseudoprimo non è pseudo ma è veramente un primo.
Ogni numero dispari N può venire espresso nella forma:
N = ( 2 ·k − 1 ) · 2^p + 1 ; k, p > 0 ; k, p ∈ Z.
Se, dato un intero 1 < a < N, risulta :
a^{2 ·k − 1} ≡ 1 modulo N
oppure:
a^h ≡ − 1 modulo N ; h = ( 2 ·k − 1 ) · 2^q = (N − 1) / 2^{p
− q} ; 0 ≤ q < p
allora N è uno pseudoprimo forte nei confronti di a ossia c'è una forte probabilità che N sia effettivamente un numero primo. Il numero a è un testimone dell'ipotesi di primalità di N ( ossia, in inglese, un witness ) ed è un testimone a favore quando N si comporta da pseudoprimo forte nei suoi riguardi ma... se questo non si verifica, allora a diventa un testimone a carico inconfutabile ossia rappresenta la prova certa che N non è primo.
Più alto è il numero di testimoni a favore, ossia tanto più si verifica che N agisce da pseudoprimo forte, tanto più alta è la probabilità che N sia veramente un numero primo.
Il teorema-congettura di Gary L. Miller (del 1976) sostiene che se tutti gli a con 1 < a < 2 · ( log N )² (essendo log il logaritmo naturale ossia in base e ) sono testimoni a favore ossia se N si comporta da pseudoprimo forte con tutti gli a e se N non è divisibile da nessun a, allore N è sicuramente un numero primo.... purché sia vera una generalizzazione dell'ipotesi di Riemann che è una congettura molto, molto credibile ma che tuttora (siamo nel 2005) non è stata rigorosamente dimostata.
Dunque il teorema-congettura di Miller non è matematicamente certo... ma dato che il logaritmo naturale di N quando N è grande è comunque un numero grande e a maggior ragione il suo quadrato, il fatto che N abbia tantissimi testimoni a favore della sua primalità e nemmeno un testimone contro la sua primalità... rende comunque enormemente probabile che N sia primo.
Notare che su Internet viene a volte citato, nel test di Miller, il limite superiore 70 · ( log N )² invece che quello più recente e favorevole di 2 · ( log N )².
Si noti inoltre che (log N / log 2)² > 2 · ( log N )² ma log N / log 2 = log₂ N approssima per difetto il numero di cifre binarie significative di N e dunque, in pratica il test di Miller va applicato a tutte le basi a non superiori al quadrato del numero di cifre binarie significative di N.
In base a quanto segnalato nel libro di Paulo Ribenboim (vedi bibliografia), sono forti pseudoprimi, ma non primi, i seguenti interi: 2047 = 23*89 smascherato dal testimone 3, 1373653 = 829*1657 smascherato dal testimone 5, 25326001 = 2251*11251 smascherato dal testimone 7, 3215031751 = 151*751*28351 smascherato dal testimone 11, 2152302898747 = 6763*10627*29947 smascherato dal testimone 13, 3474749660383 = 1303*16927*157543 smascherato dal testimone 17, 341550071728321 = 10670053*32010157 smascherato dal testimone 23.
Altri interessanti pseudoprimi forti sono 1194649 = 1093² e 12327121 = 3511² che sono innocenti per il testimone 2 ma sono smascherati dal testimone 3.

Algoritmo di elevamento a potenza

Algoritmo per il controllo di un forte pseudoprimo

Va osservato che l'operazione di prodotto modulare tra due interi a e b modulo p non viene implementata usando l'ovvia espressione Javascript a*b%p poiché si rischia di fare tracimazione (overflow) se entreambi i fattori sono grandi. Si è dunque optato per la realizzazione di una function che effettui il prodotto con lo stesso algoritmo con cui viene fatta l'elevazione a potenza ma ovviamente sostituendo l'operatore di moltiplicazione con quello di addizione.
In concreto ecco l'algoritmo della moltiplicazione modulare:

Algoritmo di moltiplicazione

Se si desidera effettuare calcoli con un maggior numero di cifre significative visitare questa pagina dedicata all' alta precisione da cui, chi è interessato a realizzare pagine didattiche di Teoria dei Numeri, potrebbe estrarre la semplice ma pratica microlibreria scritta nell'omnidisponibile Javascript.