Trova x^(Numero Enorme) in Z_n

[Frisbon]

Da quel che ho capito, l'algoritmo risolutivo é:

1. Prendi n é usa la funzione di Eulero per ricavarti fi(n)
   (scomponi n in un prodotto di numeri primi)
2. Dividi il "Numero Enorme" per n e tieniti sia il risultato che il resto
3. Componi:
   
4. Per il teorema di Eulero, puoi cancellare tutto tranne x^resto
5. Calcola x^resto

Corregete se sbaglio, di solito faccio una roba braindead senza andare nei dettagli

[CuriousCI]

Quasi corretto... (c'è un errore al punto 3, colgo l'occasione per aggiungere dettagli se qualcuno fosse interessato)

Algoritmo

Se devo calcolare $a^b$ in $\mathbb{Z}_n$ con $b$ molto grande:

Note

Per $x \equiv_n y$ intendo $x \equiv y \mod n$

1. Si calcola $\phi(n)$, con $\phi$ la funzione di Eulero (o toziente)
   • Sia $p_1^{h_1}\cdots p_s^{h_s} = n$, la scomposizione in fattori primi di $n$ a meno di ordinamenti
   • $\phi(n) = (p_1^{h_1} - p_1^{h_1 - 1}) \cdots (p_s^{h_s} - p_s^{h_s - 1})$
2. $b$ si può scrivere come $\phi(n) \cdot q + r$ (basta fare la normale divisione con resto)
3. $a^b = a^{\phi(n) \cdot q + r} = a^{\phi(n)\cdot q} \cdot a^r$
4. $a^{\phi(n)\cdot q} \equiv_n 1$ per il teorema di Eulero(-Fermat), quindi $a^{\phi(n) \cdot q + r} = a^{\phi(n)\cdot q} \cdot a^r \equiv_n 1 \cdot a^r \equiv_n a^r$
   • Più precisamente, $a^{\phi(n)} \equiv_n 1$ per il teorema di Eulero(-Fermat)
   • Ma $a^{\phi(n)\cdot q} = (a^{\phi(n)})^q \equiv_n 1^q \equiv_n 1$
5. Basta calcolare $a^r \mod n$

Esempio

$12387^{8525} \mod 10$

1. $\phi(10) = \phi(5 * 2) = (5^1 - 5^0)(2^1 - 2^0) = (5 - 1)(2 - 1) = 4$
2. $8525 = 4 \cdot 2131 + 1$
3. $12387^{8525} = 12387^{4 \cdot 2131 + 1} = 12387^{4 \cdot 2131} \cdot 12387^1$
4. $12387^{4 \cdot 2131} \cdot 12387^1 \equiv_{10} 1 \cdot 12387^1$
5. $12387 = 1238 \cdot 10 + 7 \implies 12387 \equiv_{10} 7$