Ask Your Question
1

Mocnění v modulární aritmetice

asked 2015-01-11 20:16:34 +0100

updated 2015-01-13 15:40:23 +0100

Miro Hrončok gravatar image

Jak prosím spočítat následující příklad z rozstřelu? $135^{135} \pmod{17}$

Při použití malé Fermatovy věty to jsem schopen zredukovat to na: $135^{7} \pmod{17}$, ale dál?

Obecně tedy otázka zní: Jak postupovat, pokud to po použití malé Fermatovy věty to nevyjde nějak "hezky"?

edit retag flag offensive close delete

3 Answers

Sort by » oldest newest most voted
3

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

Jasmes gravatar image

updated 2015-01-12 21:17:23 +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

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

edit flag offensive delete publish link more
0

answered 2015-01-11 20:22:27 +0100

Josef Kokeš gravatar image

updated 2015-01-11 20:25:04 +0100

Začněte výpočtem, kolik je 135 mod 17, a jak by se ten výsledek ještě dal vyjádřit.

Kdyby vůbec nešlo použít nějaké zjednodušení (ale to není váš případ), tak x^y (mod z) se dá dost jednoduše spočítat pomocí algoritmu square-and-multiply. Zvlášť když je exponent dost malý nebo má hezký tvar.

edit flag offensive delete publish link more
0

answered 2015-01-13 17:16:06 +0100

Matúš Vološin gravatar image

updated 2015-01-13 17:16:47 +0100

V tomto prípade je to úplne jednoduché pretože 135 mod 17 = -1 mod 17 takže máme -1^135 mod 17 = -1 mod 17 = 16

edit flag offensive delete publish link more

Comments

Závorku!! -1^135 se sice čirou náhodou rovná (-1)^135, ale je lepší zvyknout si spíš na ten druhý zápis.

Josef Kokeš ( 2015-01-13 18:09:59 +0100 )edit

jo jasne zavorka :) keby to bolo na papiery určite ju napíšem.

Matúš Vološin ( 2015-01-13 19:13:26 +0100 )edit

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

Asked: 2015-01-11 20:16:34 +0100

Seen: 267 times

Last updated: Jan 13 '15