Calcolatore dell’ordine moltiplicativo modulo n

Inserisca una base intera a e un modulo n: il risultato comprende la base ridotta, la funzione phi di Eulero, l’ordine e una verifica modulare diretta. Il calcolo è definito soltanto quando a e n sono coprimi; le coppie non valide producono quindi un errore chiaro, anziché un numero fuorviante. Lo strumento è utile per esercizi di aritmetica modulare, analisi di sottogruppi ciclici, schemi periodici e teoria elementare dei numeri.

Che cosa significa ordine moltiplicativo

Per gli interi a e n, l’ordine moltiplicativo di a modulo n è il minimo intero positivo k tale che a^k dia resto 1 nella divisione per n. La precisazione “minimo positivo” è importante: anche esponenti successivi possono produrre 1, ma l’ordine identifica il primo ritorno all’identità nella moltiplicazione modulare. Per esempio, le potenze di 2 modulo 9 hanno residui 2, 4, 8, 7, 5 e infine 1, quindi l’ordine è 6. Il concetto descrive la dimensione del sottogruppo ciclico generato da a tra le classi di resto invertibili modulo n. Prima del calcolo, lo strumento riduce a al consueto residuo non negativo; in questo modo gestisce coerentemente sia le basi negative sia quelle maggiori di n. Restituisce inoltre un valore di controllo calcolato mediante l’ordine indicato. Un controllo pari a 1 conferma la congruenza caratteristica, mentre il procedimento di riduzione garantisce che nessun divisore proprio ancora presente nell’esponente candidato possa soddisfarla.

Perché è richiesta la coprimalità

L’ordine moltiplicativo modulo n esiste solo quando gcd(a, n) è 1. Non è una semplice convenzione sui dati in ingresso. Un elemento deve possedere un inverso moltiplicativo modulo n affinché le sue potenze appartengano al gruppo finito delle unità e possano tornare a 1. Se a e n condividono un fattore, ogni potenza positiva di a conserva un ostacolo di divisibilità compatibile e non può essere congrua a 1 modulo n. Il calcolatore verifica subito questa condizione e segnala il massimo comune divisore effettivo quando non è rispettata. Anche il modulo deve essere almeno 2, perché il consueto problema dell’ordine è formulato in un sistema di residui non banale. La base può essere zero, negativa o positiva entro il limite pubblicato; tuttavia zero non è valido per alcun modulo ammesso, dato che non è mai coprimo con n. Quando prepara i dati, utilizzi interi esatti e non decimali o approssimazioni scientifiche. Così mantiene intatta l’aritmetica discreta da cui dipendono massimo comune divisore, fattorizzazione e potenze modulari.

Come viene trovato l’esponente minimo

Il calcolatore non prova tutti gli esponenti uno dopo l’altro. Innanzitutto fattorizza n quanto basta per calcolare la funzione phi di Eulero phi(n). Il teorema di Eulero garantisce che a elevato a phi(n) sia congruo a 1 quando gcd(a, n) è 1, dunque l’ordine cercato deve dividere phi(n). L’algoritmo fattorizza poi phi(n) e verifica ripetutamente se, dividendo il candidato corrente per uno dei suoi fattori primi, la potenza modulare rimane uguale a 1. Ogni volta che ciò avviene, il candidato più piccolo sostituisce il precedente. Quando non è più possibile eliminare alcun fattore primo, il candidato rimasto è l’ordine moltiplicativo. L’esponenziazione modulare usa l’elevamento al quadrato ripetuto, mantenendo i valori intermedi ridotti modulo n, e l’aritmetica intera resta sempre esatta. Questo metodo è molto più rapido della scansione di tutti gli esponenti positivi, soprattutto quando l’ordine è grande. Gli ingressi sono limitati a mille miliardi, così la fattorizzazione per tentativi ha un limite deterministico chiaro, adatto sia allo strumento nel browser sia alle chiamate API automatizzate.