Verificatore Euler-Jacobi

Uno pseudoprimo di Euler–Jacobi rispetto a una base data è un intero composto dispari che obbedisce al criterio di Euler come se fosse primo. Per una base a coprima, ciò significa che a elevato a (n meno uno) su due è congruo al simbolo di Jacobi di a su n, modulo n. Ogni primo dispari che non divide a soddisfa la stessa congruenza, così i composti che passano ancora sono i fallimenti interessanti di un test in stile Solovay–Strassen. Questo verificatore risponde esattamente a quella domanda: dati n composto dispari e la base a, decidere se n è uno pseudoprimo di Euler–Jacobi in quella base. La risposta riporta il gcd, il simbolo di Jacobi, la potenza modulare, se la congruenza vale e un booleano vero solo quando la definizione completa è soddisfatta.

Che cos'è uno pseudoprimo di Euler–Jacobi e come differisce dai test di Fermat e di Euler

Il criterio di Euler afferma che se p è un primo dispari e a non è divisibile per p, allora a elevato a (p meno uno) su due è congruo al simbolo di Legendre di a su p, modulo p. Il simbolo di Jacobi (a/n) estende quel carattere quadratico dai primi dispari a qualsiasi intero positivo dispari n, perciò è tentante scrivere la stessa congruenza con n al posto di p. Quando n è un primo dispari i due simboli coincidono e la congruenza è un teorema.

Quando n è dispari e composto, la congruenza può ancora valere per alcune basi sebbene n non sia primo. Quegli n si chiamano pseudoprimi di Euler–Jacobi in base a, purché gcd(a, n) sia uno. La condizione è strettamente più forte del test di Fermat (a elevato a n meno uno congruo a uno modulo n) e anche più forte del test di Euler debole, che chiede solo che la potenza modulare sia più uno o meno uno.

L'esempio classico è trecentoquarantuno in base due: è uno pseudoprimo di Fermat, due elevato a centosettanta vale uno modulo trecentoquarantuno, ma il simbolo di Jacobi (2/341) è meno uno, quindi la congruenza di Euler–Jacobi fallisce. Cinquecentosessantuno, il più piccolo numero di Carmichael, soddisfa la congruenza in base due ed è quindi uno pseudoprimo di Euler–Jacobi in quella base. Novantuno in base dieci è un altro esempio d'aula che questo verificatore conferma.

Contratto di ingresso, campi della risposta e comportamento in errore

Se n è minore di nove, pari o primo, il gestore rifiuta la richiesta: gli pseudoprimi di Euler–Jacobi sono composti dispari per definizione, e trattare un primo come uno pseudoprimo fallito insegnerebbe la lezione sbagliata. Tali fallimenti di convalida non vengono addebitati. La stringa criterion ribadisce a^((n-1)/2) ≡ (a/n) (mod n) perché una pagina o un taccuino mostri la definizione accanto al verdetto.

Quando gcd è maggiore di uno, Jacobi vale zero e la coppia non è di Euler–Jacobi anche se qualche potenza accidentale si annulla. Esempio: n uguale a cinquecentosessantuno e a uguale a due produce jacobi uno, remainder uno e un flag vero; n uguale a trecentoquarantuno e a uguale a due produce jacobi meno uno, remainder uno e un flag falso. Tutta l'aritmetica è BigInt esatto; non c'è virgola mobile né testimone casuale.

Dove un verificatore di pseudoprimi di Euler–Jacobi merita il suo posto

I corsi di teoria dei numeri e le piattaforme di concorsi usano un verificatore di pseudoprimi di Euler–Jacobi perché gli allievi distinguano i bugiardi di Fermat dai bugiardi di Solovay–Strassen senza implementare a mano la reciprocità di Jacobi né l'esponenziazione modulare. I taccuini di ricerca e le scansioni ricreative chiamano lo stesso contratto quando vogliono un oracolo indipendente per un elenco pubblicato: cinquecentosessantuno, milletencentocinque, millesettecentoventinove e gli altri esempi classici in base due devono restituire vero, mentre trecentoquarantuno in base due deve restituire falso.

I laboratori di crittografia che presentano il test di primalità di Solovay–Strassen hanno bisogno di uno strumento che rifiuti n primo, perché il punto didattico è il composto che imita il criterio di Euler, non ripetere che i primi passano. I team di ingegneria che scrivono test di proprietà per le proprie librerie di Jacobi o di potenza modulare possono fissare questa risposta come riscontro.

Preferisca questo strumento quando la domanda è strettamente se un dato composto dispari soddisfa la congruenza di Euler–Jacobi per una data base — non quando Le serve una ricerca su tutte le basi, un test solo di Fermat, un rapporto di testimoni Miller–Rabin o certificati per interi di migliaia di bit.