Esiste un algoritmo per il calcolo dell'ordine moltiplicativo di x modulo y (per y < 1000) che non richiede un tipo BigInteger?
-
22-07-2019 - |
Domanda
L'algoritmo che sto usando al momento si imbatte in numeri estremamente alti molto rapidamente. Un passo nell'algoritmo che sto per sollevare x al risultato della funzione totient applicata a y . Il risultato è che puoi imbatterti in numeri molto grandi.
Eg. Nel calcolare ordine moltiplicativo di 10 modulo 53:
10^totient(53) == 10^52 == 1 * 10^52
Il seguente algoritmo funziona un po 'meglio in termini di evitamento di grandi numeri, ma fallisce ancora quando 10 ^ mOrder è maggiore della capacità del tipo di dati:
mOrder = 1
while 10^mOrder % 53 != 1
if mOrder >= i
mOrder = 0;
break
else
mOrder = mOrder + 1
Soluzione
Usando l'esponente modulare, è possibile calcolare (10 ^ mOrder% 53) o in generale, qualsiasi (a ^ b mod c) senza ottenere valori molto più grandi di c. Vedi Wikipedia per i dettagli, c'è anche questo codice di esempio:
Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {
Bignum result = 1;
while (exponent > 0) {
if ((exponent & 1) == 1) {
// multiply in this bit's contribution while using modulus to keep result small
result = (result * base) % modulus;
}
// move to the next bit of the exponent, square (and mod) the base accordingly
exponent >>= 1;
base = (base * base) % modulus;
}
return result;
}
Altri suggerimenti
Perché esponenziare? Non puoi semplicemente moltiplicare il modulo n in un ciclo?
(defun multiplicative-order (a n) (if (> (gcd a n) 1) 0 (do ((order 1 (+ order 1)) (mod-exp (mod a n) (mod (* mod-exp a) n))) ((= mod-exp 1) order))))
O, nel codice ptheudo (sic):
def multiplicative_order (a, n) :
if gcd (a, n) > 1 :
return 0
else:
order = 1
mod_exp = a mod n
while mod_exp != 1 :
order += 1
mod_exp = (mod_exp * a) mod n
return order