modulo

neixet · Post autor: **neixet** » 15 sty 2008, o 18:52

\(\displaystyle{ 18^{-1} mod93}\) czyli obliczyc dla jakie k \(\displaystyle{ 18 kmod93=1}\)
zna ktos sposob jak szybciej obliczac niz wstawiajac po kolei k? siedzialem nad tym dzis dlugo. bylbym bardzo wdzieczny za pomoc. Jezeli nie ma rozwiazania(ktorego nie znalazlem) to tak czy inaczej istnieje jakis sposob na ulatwienie sobie zycia i przyspieszenie rozwiazania?

UNIX_admin · Post autor: **UNIX_admin** » 15 sty 2008, o 19:23

odwrotnosc modulo najlatwiej liczy sie tzw. rozszerzonym algorytmem Euklidesa

jesli chcesz moge podeslac Ci kod.

proponuje wpisac w google: odwrotność modulo

neixet · Post autor: **neixet** » 15 sty 2008, o 20:18

no to w sumie z tego algorytmu korzystalem, tylko jesli na kolokwium jest do obliczenia 18kmod93 w 5min to troche masakra :/

[ Dodano: 15 Stycznia 2008, 20:42 ]
dobra juz sobie poradzilem... ze tez wczesniej na to nie wpadlem
kiedy liczymy np 13*1mod93 otrzymujemy reszte 13
bezsensownym byloby liczenie
13*2...
13*3... poniewaz wiemy ze ta liczba jest mniejsza od 93 a wiec napewno nie da reszty 1
liczymy wiec
13*7... reszta 91 wiec o 3 za malo, wiadomo natomiast ze gdy pomnozymy razy 8 to bedzie o wiele za duzo przeskakujemy wiec o kolejne 7 liczb
13*14... lipa
13*21... lipa
...
...
13*42... ooo prawie - reszta 12
13*43... reszta 1- bingo

UNIX_admin · Post autor: **UNIX_admin** » 15 sty 2008, o 20:53

w zastosowaniach praktycznych radze korzystac z Euklidesa, ale w tym konkretnym przypadku (dla bardzo malych n i w dodatku nie bedacych liczba pierwsza (n=93)) mozna skorzystac z Fermata:

\(\displaystyle{ a^{-1}=a^{\phi(n)-1}(mod \ n)}\)

nalezy oczywiscie pamietac, ze odrotnosc istnieje tylko jesli a i n sa wzglednie pierwsze.

tak wiec dla powyzszego przykladu odwrotnosc nie istnieje