Mocnění v modulární aritmetice

answered Jan 12 '15

Jasmes
111 ●5 ●5

updated Jan 12 '15

Muj obecny postup pro reseni $a^x~mod~n$

1. $a = a' ~(mod~n)$, pokud mi vyslo $1$ nebo $-1$ mam hotovo.
2. pokud $gcd(a',n)$ == 1, upravim vyraz za pomoci $a'^{\varphi(n)} = 1~(mod~n)$
3. Dostanu $a'^{x'}~(mod~n)$
4. 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$.