| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
nick
Forumaš(ica)
Pridružen/a: 15. 02. 2005. (11:58:25)
Postovi: (6)16
|
 Postano: 11:07 čet, 26. 5. 2005 Naslov: jednostavna linearna kongruencija |
    |
|
|
Pretpostavljam da je moje pitanje vama supertrivijalno, no ja nisam matematicar, ovdje slusam samo Kriptografiju i s kongruencijama stojim zalosno lose :-) Zato me zanima postoji li nacin da se jednostavno rijesi sljedeca kongruencija:
ax=1 (mod b), gdje je "=" oznaka za kongruenciju, jel
ako je Nzd(a, b)=1? Naime, mogao bih iterativno proci sve xove od 1 do n pa racunati ostatak, no zanima me postoji li jednostavniji algoritam za rijesavanje takvih kongruencija...
Zahvaljujen unaprijed...
Pretpostavljam da je moje pitanje vama supertrivijalno, no ja nisam matematicar, ovdje slusam samo Kriptografiju i s kongruencijama stojim zalosno lose :-) Zato me zanima postoji li nacin da se jednostavno rijesi sljedeca kongruencija:
ax=1 (mod b), gdje je "=" oznaka za kongruenciju, jel
ako je Nzd(a, b)=1? Naime, mogao bih iterativno proci sve xove od 1 do n pa racunati ostatak, no zanima me postoji li jednostavniji algoritam za rijesavanje takvih kongruencija...
Zahvaljujen unaprijed...
|
|
| [Vrh] |
|
GauSs_
Moderator
Pridružen/a: 28. 01. 2004. (21:01:17)
Postovi: (53C)16
Spol: 
Lokacija: 231
|
| Postano: 13:24 čet, 26. 5. 2005 Naslov: |
|
|
|
prvo odradis Euklidov algoriatam:
[code:1]
b = aq(1) + r(1), 0 < r(1) < a,
a = r(1)q(2) + r(2), 0 < r(2) < r(1),
r(1) = r(2)q(3) + r(3), 0 < r(3) < r(2),
. . .
r(j−2) = r(j−1)q(j) + r(j) , 0 < r(j) < r(j−1),
r(j−1) = r(j)q(j+1).[/code:1]
te dobijes odgovarajuce q-ove.
tada pomocu rekurzije:
[code:1]
y(−1) = 0, y(0) = 1; y(i) = y(i−2) − q(i)y(i−1),
[/code:1]
izracunas odgovarajuce y.
rjesenje kongruencije je y(j).
pogledaj primjer 2.1 iz knjige profesora Dujelle:
[url]http://web.math.hr/~duje/utb/utblink.pdf[/url]
Za provjeru mozes koristiti funkciju [b]PowerMod[/b] iz programskog
paketa [i]Mathematica[/i].
prvo odradis Euklidov algoriatam:
| Kod: |
b = aq(1) + r(1), 0 < r(1) < a,
a = r(1)q(2) + r(2), 0 < r(2) < r(1),
r(1) = r(2)q(3) + r(3), 0 < r(3) < r(2),
. . .
r(j−2) = r(j−1)q(j) + r(j) , 0 < r(j) < r(j−1),
r(j−1) = r(j)q(j+1). |
te dobijes odgovarajuce q-ove.
tada pomocu rekurzije:
| Kod: |
y(−1) = 0, y(0) = 1; y(i) = y(i−2) − q(i)y(i−1),
|
izracunas odgovarajuce y.
rjesenje kongruencije je y(j).
pogledaj primjer 2.1 iz knjige profesora Dujelle:
http://web.math.hr/~duje/utb/utblink.pdf
Za provjeru mozes koristiti funkciju PowerMod iz programskog
paketa Mathematica.
_________________ The purpose of life is to end
Prosle su godine kolokviji bili laksi, zar ne? |
|
| [Vrh] |
|
nick
Forumaš(ica)
Pridružen/a: 15. 02. 2005. (11:58:25)
Postovi: (6)16
|
|
| [Vrh] |
|
|
