| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Mr. Nice Guy
Gost
|
 Postano: 11:07 pet, 9. 10. 2009 Naslov: Primjer 1.22 |
    |
|
|
Imam problema pri shvaćanju primjera 1.22
3^x kongruentno 2 (mod 23)
OK, odredimo primitivni korijen, to mi je jasno (btw, 5). Zatim zašto radimo ono u sljedećem redu tj. provjeravamo koliki je ostatak za 5^2, 5^5 i 5^11, zašto baš na te potencije?
Imam problema pri shvaćanju primjera 1.22
3^x kongruentno 2 (mod 23)
OK, odredimo primitivni korijen, to mi je jasno (btw, 5). Zatim zašto radimo ono u sljedećem redu tj. provjeravamo koliki je ostatak za 5^2, 5^5 i 5^11, zašto baš na te potencije?
|
|
| [Vrh] |
|
duje
Forumaš(ica)
Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol: 
|
| Postano: 11:23 pet, 9. 10. 2009 Naslov: |
|
|
|
Treba naci ind_5 3 i ind_5 2, znaci brojeve a i b takve da je 5^a == 3 (mod 23), 5^b == 2 (mod 23).
Moze se napraviti tablica svih ostataka brojeva 5^i za i=0,1,...,22, pa u njoj pronaci ostatke 2 i 3.
Cesto se moze i barem malo krace. Ovdje je dosta ocito da je ind_5 2 =2 jer je 5^2 = 25 == 2 (mod 23).
Ono sa 5^11 ne treba posebno racunati, jer uvijek za primitivni korijen g vrijedi da je g^((p-1)/2) == -1 (mod p). To se moze iskoristiti tako da je dovoljno ispuniti polovicu tablice; npr. kad se dobije 5^5 == -3 (mod 23), onda se mnozenjem kongruencija dobije da je 5^16 == 3 (mod 23).
Treba naci ind_5 3 i ind_5 2, znaci brojeve a i b takve da je 5^a == 3 (mod 23), 5^b == 2 (mod 23).
Moze se napraviti tablica svih ostataka brojeva 5^i za i=0,1,...,22, pa u njoj pronaci ostatke 2 i 3.
Cesto se moze i barem malo krace. Ovdje je dosta ocito da je ind_5 2 =2 jer je 5^2 = 25 == 2 (mod 23).
Ono sa 5^11 ne treba posebno racunati, jer uvijek za primitivni korijen g vrijedi da je g^((p-1)/2) == -1 (mod p). To se moze iskoristiti tako da je dovoljno ispuniti polovicu tablice; npr. kad se dobije 5^5 == -3 (mod 23), onda se mnozenjem kongruencija dobije da je 5^16 == 3 (mod 23).
|
|
| [Vrh] |
|
Gost
|
| Postano: 11:38 pet, 9. 10. 2009 Naslov: |
|
|
|
[quote="duje"]Treba naci ind_5 3 i ind_5 2, znaci brojeve a i b takve da je 5^a == 3 (mod 23), 5^b == 2 (mod 23).
Moze se napraviti tablica svih ostataka brojeva 5^i za i=0,1,...,22, pa u njoj pronaci ostatke 2 i 3.
Cesto se moze i barem malo krace. Ovdje je dosta ocito da je ind_5 2 =2 jer je 5^2 = 25 == 2 (mod 23).
Ono sa 5^11 ne treba posebno racunati, jer uvijek za primitivni korijen g vrijedi da je g^((p-1)/2) == -1 (mod p). To se moze iskoristiti tako da je dovoljno ispuniti polovicu tablice; npr. kad se dobije 5^5 == -3 (mod 23), onda se mnozenjem kongruencija dobije da je 5^16 == 3 (mod 23).[/quote]
Znači, za ovaj 5^5 moramo ići za svaki i=0,1,2.... ?
| duje (napisa): | Treba naci ind_5 3 i ind_5 2, znaci brojeve a i b takve da je 5^a == 3 (mod 23), 5^b == 2 (mod 23).
Moze se napraviti tablica svih ostataka brojeva 5^i za i=0,1,...,22, pa u njoj pronaci ostatke 2 i 3.
Cesto se moze i barem malo krace. Ovdje je dosta ocito da je ind_5 2 =2 jer je 5^2 = 25 == 2 (mod 23).
Ono sa 5^11 ne treba posebno racunati, jer uvijek za primitivni korijen g vrijedi da je g^((p-1)/2) == -1 (mod p). To se moze iskoristiti tako da je dovoljno ispuniti polovicu tablice; npr. kad se dobije 5^5 == -3 (mod 23), onda se mnozenjem kongruencija dobije da je 5^16 == 3 (mod 23). |
Znači, za ovaj 5^5 moramo ići za svaki i=0,1,2.... ?
|
|
| [Vrh] |
|
duje
Forumaš(ica)
Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol:
|
| Postano: 12:37 pet, 9. 10. 2009 Naslov: |
|
|
|
[quote]
Znači, za ovaj 5^5 moramo ići za svaki i=0,1,2.... ?[/quote]
Opcenito se a^n (mod m) racuna metodom "kvadriraj i mnozi" (vidite npr. http://web.math.hr/~duje/kript/rsa.html ili
http://web.math.hr/~duje/tbkript/tbkriptlink.pdf (Poglavlje 2.3)),
ali za ovako male brojeve nema velike potrebe za optimizacijom racunanja, pa izracunajte kako god hocete.
Efikasno racunanje a^n (mod m) s vrlo velikim brojevima je vazno npr. kod RSA kriptosustava, Miller-Rabinovom testa prostosti, ...
| Citat: |
Znači, za ovaj 5^5 moramo ići za svaki i=0,1,2.... ? |
Opcenito se a^n (mod m) racuna metodom "kvadriraj i mnozi" (vidite npr. http://web.math.hr/~duje/kript/rsa.html ili
http://web.math.hr/~duje/tbkript/tbkriptlink.pdf (Poglavlje 2.3)),
ali za ovako male brojeve nema velike potrebe za optimizacijom racunanja, pa izracunajte kako god hocete.
Efikasno racunanje a^n (mod m) s vrlo velikim brojevima je vazno npr. kod RSA kriptosustava, Miller-Rabinovom testa prostosti, ...
|
|
| [Vrh] |
|
|
