Test di primalità di Lucas

Fornisca un intero dispari n, un testimone di Lucas proposto e la fattorizzazione prima completa di n meno uno. Il calcolatore convalida la fattorizzazione, valuta le potenze modulari e i massimi comuni divisori richiesti e certifica n soltanto quando tutte le condizioni del teorema di Lucas sono soddisfatte. Le stringhe decimali conservano interi esatti anche oltre il consueto intervallo numerico sicuro di JavaScript.

Prepari un certificato completo

Parta dall’intero dispari che desidera certificare e fattorizzi completamente n meno uno. Inserisca n e ogni fattore primo come stringa decimale canonica, perché le stringhe mantengono valori esatti fino al limite di 64 bit. Ogni fattore deve comparire una sola volta con il proprio esponente positivo. Per esempio, con n = 29 si ha n meno uno = 28 = 2 al quadrato per 7; l’elenco contiene quindi 2 con esponente 2 e 7 con esponente 1. Deve inoltre fornire una base a tale che 1 < a < n. Questa base è il testimone di Lucas proposto. Il verificatore richiede intenzionalmente il testimone invece di cercarlo: la verifica di un certificato è rapida, limitata e ripetibile, mentre una ricerca può avere una durata dipendente dall’input. Se non dispone ancora di un testimone, provi piccole basi con uno strumento separato per le radici primitive, quindi invii il certificato ottenuto. Spazi, segni, zeri iniziali, notazione in virgola mobile, primi duplicati, fattori composti e fattori mancanti vengono respinti anziché normalizzati in silenzio; il certificato è così adatto ai registri di controllo e alle pipeline automatizzate.

Comprenda le due condizioni di Lucas

Il primo calcolo verifica che a elevato a n meno uno sia congruente a 1 modulo n. È la nota condizione di Fermat, ma da sola non può dimostrare la primalità, perché gli pseudoprimi possono soddisfarla. La seconda fase, decisiva, usa ogni primo distinto q che divide n meno uno. Per ciascun q, il verificatore calcola a elevato a (n meno uno) diviso q modulo n, sottrae uno e controlla che il risultato abbia massimo comune divisore 1 con n. Il superamento di tutti questi controlli dimostra che l’ordine moltiplicativo di a modulo n è esattamente n meno uno. Un elemento modulo n non può avere tale ordine a meno che n sia primo: questo è il nucleo del teorema di Lucas. I controlli restituiti mostrano il residuo modulare e il massimo comune divisore per ogni q distinto, mentre l’esponente resta visibile nella fattorizzazione convalidata. L’esponenziazione modulare usa quadrati successivi e aritmetica BigInt esatta, quindi il calcolo non dipende mai da arrotondamenti in virgola mobile, basi casuali, servizi di rete o affidabilità probabilistica.

Interpreti errori e risultati positivi

Una risposta positiva è il risultato di un certificato di primalità, non una semplice etichetta di primo probabile. Ripete n, identifica il testimone accettato, riporta il residuo di Fermat ed elenca un controllo riuscito del massimo comune divisore per ogni fattore distinto di n meno uno. Conservi l’input originale insieme alla risposta quando un altro sistema deve riprodurre la dimostrazione. Gli errori sono volutamente specifici. Se le potenze dei fattori non producono esattamente n meno uno, la fattorizzazione è incompleta o errata. Se un fattore indicato è composto o lo stesso primo compare due volte, la fattorizzazione è malformata anche se il prodotto grezzo coincide. Il fallimento di una condizione modulare indica che la base fornita non è un testimone di Lucas; da solo non distingue un n composto da un primo associato a una base inadatta. Provi un altro testimone matematicamente giustificato se si attende ancora la primalità. Gli input sono limitati agli interi dispari da 3 a 2^64 meno 1, permettendo la convalida deterministica dei fattori primi indicati prima di valutare il certificato. Il prezzo dell’API è $0.002 per richiesta.