Devo calcolare in modo efficiente a ^^ b mod m per grandi valori di a, b, m < 2^32
dove ^^ è l'operatore di tetrazione: 2 ^^ 4 = 2^(2^(2^2))
Come calcolare a ^^ b mod m?
m non è un numero primo e non un potere di dieci.
Potete essere d'aiuto?
Per essere chiari, a ^^ b non è la stessa cosa di a^b, è la torre esponenziale a^(a^(a^...^a)) dove ci sono b copie di a, noto anche come tetration. Sia T (a, b) = a ^^ b così T (a, 1) = a e T (a, b) = a^T (a, b-1).
Per calcolare T (a, b) mod m = a^T (a, b-1) mod m, vogliamo calcolare una potenza di una mod m con un esponente estremamente grande. Quello che puoi usare è che l'esponenziazione modulare è preperiodica con lunghezza preperiodo al massimo della massima potenza di un primo nella fattorizzazione primaria di m, che è al massimo log_2 m, e la lunghezza del periodo divide phi (m), dove phi (m) è Euler's totient function. In effetti, la lunghezza del periodo divide Carmichael's function di m, lambda (m). Così,
a^k mod m = a^(k+phi(m)) mod m as long as k>log_2 m.
attenzione che una non è necessariamente relativamente primi a m (o successiva, a phi (m), phi (phi (m)), etc.). Se lo fosse, potresti dire che a^k mod m = a^(k mod phi (m)) mod m. Tuttavia, questo non è sempre vero quando a e m non sono relativamente primi. Ad esempio, phi (100) = 40 e 2^1 mod 100 = 2, ma 2^41 mod 100 = 52. Puoi ridurre i grandi esponenti ai numeri congruenti mod phi (m) che sono almeno log_2 m, quindi tu posso dire che 2^10001 mod 100 = 2^41 mod 100 ma non puoi ridurlo a 2^1 mod 100. Potresti definire un mod m [minimo x] o usare min + mod (a-min, m) finché a> min.
Se T (a, b-1)> [log_2 m], quindi
a^T(a,b-1) mod m = a^(T(a,b-1) mod phi(m) [minimum [log_2 m]])
altrimenti solo calcolare un^T (a, b-1) mod m.
Calcolare in modo ricorsivo questo valore. Puoi sostituire phi (m) con lambda (m).
Non ci vuole molto tempo per calcolare la fattorizzazione primaria di un numero inferiore a 2^32 poiché è possibile determinare i fattori primi al massimo 2^16 = 65.536 divisioni di prova. Le funzioni della teoria dei numeri come phi e lambda sono facilmente espresse in termini di fattorizzazione primaria.
Ad ogni passaggio, sarà necessario essere in grado di calcolare le potenze modulari con piccoli esponenti.
Si finisce per calcolare i poteri mod phi (m), quindi si alimenta mod phi (phi (m)), quindi si alimenta mod phi (phi (phi (m))), ecc. Non ci vogliono molte iterazioni prima che la funzione phi iterata sia 1, il che significa che riduci tutto a 0 e non ottieni più alcun cambiamento aumentando l'altezza della torre.
Ecco un esempio, di un tipo che è incluso nelle gare di matematica delle scuole superiori in cui i concorrenti dovrebbero riscoprire questo ed eseguirlo a mano. Quali sono le ultime due cifre del 14 ^^ 2016?
14^^2016 mod 100
= 14^T(14,2015) mod 100
= 14^(T(14,2015) mod lambda(100) [minimum 6]) mod 100
= 14^(T(14,2015 mod 20 [minimum 6]) mod 100
T(14,2015) mod 20
= 14^T(14,2014) mod 20
= 14^(T(14,2014) mod 4 [minimum 4]) mod 20
T(14,2014) mod 4
= 14^T(14,2013) mod 4
= 14^(T(14,2013 mod 2 [minimum 2]) mod 4
T(14,2013) mod 2
= 14^T(14,2012) mod 2
= 14^(T(14,2012 mod 1 [minimum 1]) mod 2
= 14^(1) mod 2
= 14 mod 2
= 0
T(14,2014) mod 4
= 14^(0 mod 2 [minimum 2]) mod 4
= 14^2 mod 4
= 0
T(14,2015) mod 20
= 14^(0 mod 4 [minimum 4]) mod 20
= 14^4 mod 20
= 16
T(14,2016) mod 100
= 14^(16 mod 20 [minimum 6]) mod 100
= 14^16 mod 100
= 36
Quindi, 14^14^14^...^14 termina nelle cifre ... 36.
Puoi dare la parte dell'algoritmo ricorsivo in pseudo-codice con tutte le condizioni di arresto della ricorsione e tenendo conto del caso in cui a e m non sono relativamente prime. – bilbo
@bilbo: Il motivo per cui ho usato x mod y [min k] invece di x mod y era che la mia risposta gestisce il caso che a non è relativamente primo a m, o a phi (m). Non ho mai dato per scontato che a era relativamente primo a m. Le linee "Se T (a, b-1)> [log_2 m], quindi a^T (a, b-1) mod m = a^(T (a, b-1) mod phi (m) [minimo [log_2 m]]) altrimenti calcola solo un^T (a, b-1) mod m. " descrivere l'algoritmo. –
Non vedo come calcolare T (a, b-1) senza overflow per testare T (a, b-1)> [log_2 m]. La funzione ricorsiva I calcola è T1 (a, b, totient (m), log_2 (m)) ma non vedo come includere il test T (a, b-1)> [log_2 m] – bilbo
Quale lingua? Cosa hai provato? –
http: //en.wikipedia.org/wiki/Exponentiation_by_squaring –
Puoi provare a implementarlo in python, ma non dimenticare di usare la proprietà modulare '(una mod n) (b mod n) == ab mod n' poiché questo ridurrà parte del tuo lavoro, prendendo il caso peggiore 'a = b = m = 2^32 - 1', il risultato finale richiederà molto tempo e memoria per essere eseguito. –