Muj obecny postup pro reseni $a^x~mod~n$
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?
2 | No.2 Revision |
Muj obecny postup pro reseni $a^x~mod~n$
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?
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$.