Test di primalità di Proth con testimone

Prima controlla che k sia positivo e dispari, che n sia positivo e che k sia minore di 2^n. Poi calcola esattamente la potenza modulare richiesta. Una congruenza valida dimostra che il numero di Proth è primo; un testimone negativo resta inconcludente, salvo che riveli un fattore.

Inserisca un vero numero di Proth e un testimone

Un numero di Proth ha esattamente la forma N = k × 2^n + 1, dove k è un intero positivo dispari, n è un intero positivo e k è strettamente minore di 2^n. Tutte queste condizioni sono essenziali. Il calcolatore accetta k e il testimone come testo decimale, così i valori grandi rimangono esatti e non subiscono arrotondamenti in virgola mobile. Inserisca n come intero da 1 a 10,000. Lo strumento costruisce N anziché richiederlo separatamente, impedendo discrepanze tra il numero dichiarato e i parametri che lo definiscono. Verifica inoltre che il testimone sia strettamente compreso tra 1 e N. Un k pari, un valore non positivo oppure k maggiore o uguale a 2^n fanno rifiutare l’input come non appartenente alla forma di Proth, senza applicare un teorema quando le sue ipotesi non valgono. Il numero, l’esponente, il testimone e il residuo vengono restituiti come stringhe decimali quando necessario, affinché Lei possa controllare il calcolo e copiarlo in un altro strumento di aritmetica esatta.

Comprenda che cosa dimostra la congruenza

Per un numero di Proth valido N, il teorema afferma che N è primo se esiste un intero a per cui a^((N−1)/2) è congruo a −1 modulo N. Il testimone fornito rappresenta a e il calcolatore valuta la potenza modulare mediante quadratura ripetuta, senza costruire prima l’enorme potenza ordinaria. Nell’output, `residue` è il minimo residuo non negativo e `passes_test` è true esattamente quando coincide con N−1, cioè la rappresentazione modulare di −1. In tal caso `prime_proven` è true e il verdetto è `prime`: con le condizioni di Proth già verificate, questo costituisce un certificato deterministico, non una stima di probabile primalità. La risposta comprende l’esponente esatto (N−1)/2, così Lei può riprodurre autonomamente la congruenza. L’algoritmo usa soltanto operazioni intere, non sceglie testimoni casuali e non consulta tabelle o servizi remoti. Pertanto lo stesso input restituisce sempre il medesimo risultato e rende visibili tutti i valori importanti impiegati dal teorema.

Interpreti correttamente un testimone negativo

Un testimone che non produce −1 non dimostra da solo che il numero sia composto. Significa soltanto che quello specifico testimone non soddisfa la condizione sufficiente del teorema di Proth. Per questo il calcolatore restituisce `inconclusive`, non `composite`, quando il residuo è diverso e il testimone è coprimo con N. Lei può quindi provare un altro testimone scelto matematicamente oppure usare un diverso metodo deterministico di primalità. Esiste un’eccezione utile: prima di interpretare la congruenza, il calcolatore determina il massimo comune divisore tra il testimone e N. Se tale valore è un fattore proprio, il risultato è definitivamente `composite` e viene restituito il fattore. Questa distinzione impedisce l’errore comune di trasformare un teorema unidirezionale in un test bidirezionale non valido. È utile anche nei flussi automatizzati: accetti `prime` come prova, respinga `composite` quando emerge un fattore e invii `inconclusive` a un altro test senza considerarlo silenziosamente un fallimento definitivo.