Verifica degli pseudoprimi di Fermat per qualsiasi base

Un composto che supera il controllo è pseudoprimo di Fermat per la base scelta: in questo test specifico si comporta come un primo, pur non essendolo. Viene mostrato anche il massimo comune divisore, così Lei può analizzare e spiegare più facilmente il risultato.

Che cosa significa davvero un esito positivo

Il piccolo teorema di Fermat afferma che, se n è primo e a non è divisibile per n, allora a elevato a n meno uno dà resto uno modulo n. Il contrario non è garantito. Alcuni interi composti producono anch’essi resto uno per determinate basi e vengono chiamati pseudoprimi di Fermat rispetto a tali basi. Questo strumento richiede espressamente che n sia composto, verifica prima tale condizione e poi valuta la congruenza in modo esatto. Quando passes_fermat_test e is_fermat_pseudoprime sono veri, il composto inserito ha ingannato il test di Fermat per quella specifica base. Ciò non significa che n sia primo, probabilmente primo o pseudoprimo per ogni base. La base è parte integrante dell’affermazione e deve sempre accompagnare il risultato. Il resto restituito costituisce la prova aritmetica diretta: uno indica il superamento, mentre qualsiasi altro valore indica il fallimento. Il massimo comune divisore aiuta inoltre a distinguere le prove con basi coprime dai casi in cui l’input rivela già una relazione tra fattori.

Come viene garantita l’esattezza del calcolo

Entrambi gli input sono stringhe decimali, così gli interi oltre l’intervallo numerico sicuro di JavaScript non vengono arrotondati prima del calcolo. L’intervallo accettato termina al massimo intero senza segno a 64 bit e offre quindi un limite chiaro e verificabile per il controllo di primalità. Prima del test di Fermat, lo strumento applica Miller–Rabin in forma deterministica con un insieme di testimoni sufficiente per l’intero intervallo. Se viene rilevato un primo, restituisce un errore di input: i primi soddisfano il teorema, ma per definizione non possono essere pseudoprimi. Per un composto valido, l’esponenziazione modulare usa il metodo dei quadrati ripetuti invece di costruire l’enorme valore a^(n-1). Ogni moltiplicazione viene ridotta modulo n, mantenendo i valori intermedi limitati ed esatti con BigInt. L’algoritmo di Euclide calcola separatamente gcd(a,n). La base deve rispettare 2 <= a <= n - 2. Nessun testimone casuale, data, chiamata di rete o operazione in virgola mobile influenza la risposta, perciò input uguali producono sempre output uguali.

Impiego nello studio e nei flussi di verifica

Un esempio classico usa n = 341 con base a = 2. Benché 341 sia composto, 2^340 è congruo a uno modulo 341; pertanto supera il test ed è pseudoprimo di Fermat in base due. Cambiando la base, lo stesso composto può fallire: un singolo test di Fermat non è quindi un certificato generale di primalità. In una lezione, l’output strutturato consente di collegare direttamente la definizione al resto calcolato. In una suite di test, può conservare vettori noti di pseudoprimi e non pseudoprimi senza dipendere da una libreria matematica o da conversioni numeriche legate alla macchina. Per esplorare il fenomeno, confronti più basi ammesse mantenendo fisso n e osservi quanto conta la scelta del testimone. Consideri un risultato vero come dimostrazione dei limiti del test di Fermat, non come autorizzazione ad accettare il numero quale primo in codice crittografico o sensibile alla sicurezza. L’API costa $0.002 per ogni coppia verificata, mentre la versione nel browser esegue localmente lo stesso calcolo deterministico.