Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

posted 2015-01-12 21:13:31 +0100

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

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$.