answered
2015-01-12 21:13:31 +0100
Muj obecny postup pro reseni $a^x~mod~n$
- $a = a' ~(mod~n)$, pokud mi vyslo $1$ nebo $-1$ mam hotovo.
- pokud $gcd(a',n)$ == 1, upravim vyraz za pomoci $a'^{\varphi(n)} = 1~(mod~n)$
- Dostanu $a'^{x'}~(mod~n)$
- Ted mam 2 moznosti: Budto pouziji a) square-and-multiply nebo pokud $n$ neni prvocislo tak b) CRT
Jak pouzit CRT?
Napisu si $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$. Dale si spocitam
$a'^{x'} = b_1 ~ (mod ~ p_1^{\alpha_1})$
$\vdots$
$a'^{x'} = b_k ~ (mod ~ p_k^{\alpha_k})$
A pak zpetne dopocitam pomoci CRT, tak jak ji zname.
Proc pouzivat CRT, kdyz je to spousta prace navic?
- Idealne dostanu $gcd(a', p_i) = 1$, takze budu moci pouzit Eulerovu vetu
- Pro nektera $p_i$ bude platit, ze $p_i | a'$
- U square-and-multiply pracuji s mensim modulem
Dalsi moznost jak si ulehcit praci:
$a^x = (a-n)^x ~(mod~n)$, neboli nez mocnit ohromna cisla je jednodussi si pekne umocnovat $(-2)^x$.