Posted By: gekon (Love, peace and Coyot!) on 'CZscience'
Title: Re: Eukliduv algoritmus
Date: Thu Apr 17 12:05:55 1997
<*** Graficky upravil room aide. Lumo ***>
------------------------------------------
Tak me to chvili vrtalo hlavou a pak mi doslo, ze jde o naprosto trivialni
problem.
Budu psat obecne pro rovnici t*x = 1 mod n, kde promenna je t a x, n jsou
zname konstanty.
Jedna se o obycejne hledani inverzniho prvku k tride [x] v grupe
zbytkovych trid modulo n. Z teorie grup vyplyva, ze reseni existuje pro kazde x
pouze v pripade, ze n je prvocislo. Jinak se obecne dost dobre neda urcit, pro
ktera x reseni existuje a pro ktera ne (pak se totiz nejedna o grupu, ale
jen o monoid a tudiz vsechny prvky nemaji inverzi), takze podminka, aby n bylo
<*** Pro ktera x existuje inverzni prvek v monoidu Z_n, se da urcit celkem
snadno. Jsou to vsechna cisla x nesoudelna s n. Drobny doplnek Lumo ***>
prvocislo je prakticky nezbytna. Spocitame si Eukleidovym algoritmem NSD(n, x)
a oznacme ho treba q. Bezoutova rovnost rika, ze existuji takova cela cisla a,
b, ze plati: q = a*n + b*x. A nami hledane t je prave b.
A ted jak se ty cisla a, b spocitaji:
Jedna se vlastne o eukleiduv algoritmus zdola nahoru.
Eukleiduv algoritmus pro NSD(n, x), n>x:
n = k_1 * x + r_1 r_1 < x
x = k_2 * r_1 + r_2 r_2 < r_1
r_1 = k_2 * r_2 + r_3 r_3 < r_2
.
.
r_n-2 = k_n-1 * r_n-1 + r_n r_n < r_n-1
r_n-1 = k_n * r_n deleni vyjde beze zbytku
A ted Bezoutova rovnost:
Zbytky r_n az r_1 postupne vyjadrime pomoci zbytku s nizsim indexem
q = r_n = r_n-2 - k_n-1*r_n-1 = (ted vyjadrime r_n-1 pomoci r_n-2 a r_n-3)
r_n-2 - k_n-1*(r_n-3 - k_n-2*r_n-2) = (upravime) r_n-2*(1 - k_n-1*k_n-2) -
k_n-2*r_n-3 = ... = neco_1*n + neco_2*x.
A to neco_2 je hledane b (=t).
No, vypada to priserne, ale je to docela jednoduchy. Zkusim ukazat na
priklade:
Zkusim spocitat to t, z rovnice t*29 = 1 mod 1189.
:))) Zacal jsem to tukat do kalkulacky a ono 1189=29*41. Takze reseni
neexistuje.
Tak zkusim treba t*29 = 1 mod 571. NETVRDIM, ze 571 je prvocislo, ale pokud
ne, tak mam stesti a vyjde to.
571 = 19 * 29 + 20
29 = 1 * 20 + 9
20 = 2 * 9 + 2
9 = 4 * 2 + 1
2 = 2 * 1 + 0
Tedy NSD(571, 29) = 1. A ted Bezout:
1 = 9 - 4*2 = 9 - 4*(20 - 2*9) = (pozor, nesmime vycislit zavorku, ale musime
ji roznasobit) = 9*(1 -4*-2) - 4*20 = 9*9 - 4*20 = 9*(29 - 1*20) - 4*20 = 9*29
- 13*20 = 9*29 - 13*(571 - 19*29) = -13*571 + 256*29.
Cili t=256.
UUUUF! Hodina je v haji. Snad ti to bude k uzitku. Nenech se odradit, je do
docela jednoduchy a pro pocitac uplna malina.
> Diky
> vecne nespokojeny rk
> -----------------------------------------------------------------------------
> Where do foxes give Good night?
Gekon /-----
/ 0 0
------------------------------------------- ' -------------------
Never send to know for whom the bell talls. ===== / Microsoft?
It talls for thee... _____/ Just simply say NO!
<*** To byla pekna prednaska, rekl bych, diky! Room aide Lumo. ***>