| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
hermione
Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol: 
Sarma: -
|
|
| [Vrh] |
|
duje
Forumaš(ica)
Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol: 
|
|
| [Vrh] |
|
hermione
Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol:
Sarma: -
|
|
| [Vrh] |
|
duje
Forumaš(ica)
Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol:
|
|
| [Vrh] |
|
Gost
|
 Postano: 11:49 čet, 19. 1. 2006 Naslov: |
    |
|
|
kak se ti korijeni određuju?? Stavim neki prost broj na 1/2eulerove funkc. ==1 (mod n)
jel? pa se onda gleda kad nije?
npr. modulo 23:
23 je prost , gleda se euler od 22 ->ima 11
i sad uzmem npr. 2^11=32*64 {tj. 2^5*2^6 da li to sama tako biram?}==9*(-5)==1(mod 23)
otkud mi ovo 9*(-5)? jasno mi je da se pokušava zadovoljiti taj uvijet 1(mod n), pa taj br nije primitivan korijen ali nije mi jasno kako dobijem ove brojeve izmeđju 32*64 i 9*(-5); ovo 9 je kao 32-23, a -5 je 64-23-23-23, ali zašto se baš tu staje?
i sad se kao dobije da 2 nije, pa se uzme 3 pa tako redom?
kak se ti korijeni određuju?? Stavim neki prost broj na 1/2eulerove funkc. ==1 (mod n)
jel? pa se onda gleda kad nije?
npr. modulo 23:
23 je prost , gleda se euler od 22 ->ima 11
i sad uzmem npr. 2^11=32*64 {tj. 2^5*2^6 da li to sama tako biram?}==9*(-5)==1(mod 23)
otkud mi ovo 9*(-5)? jasno mi je da se pokušava zadovoljiti taj uvijet 1(mod n), pa taj br nije primitivan korijen ali nije mi jasno kako dobijem ove brojeve izmeđju 32*64 i 9*(-5); ovo 9 je kao 32-23, a -5 je 64-23-23-23, ali zašto se baš tu staje?
i sad se kao dobije da 2 nije, pa se uzme 3 pa tako redom?
|
|
| [Vrh] |
|
duje
Forumaš(ica)
Pridružen/a: 07. 11. 2002. (12:21:31)
Postovi: (55C)16
Spol:
|
| Postano: 13:13 čet, 19. 1. 2006 Naslov: |
|
|
|
[quote]kak se ti korijeni određuju?? Stavim neki prost broj na 1/2eulerove funkc. ==1 (mod n)
jel? pa se onda gleda kad nije?[/quote]
Da bi se provjerilo je li broj a primitivni korijen, provjerava se vrijedi li za neki prirodan broj k manji od phi(n) da je a^k== 1 (mod n).
U slucaju kada je n prost broj, onda je phi(n)=n-1. Tada je dovoljno provjeriti gornju kongruenciju za brojeve k oblika (n-1)/q, gdje su q-ovi prosti faktori od n-1. To znaci da ispitivanje kongruencije a^{phi(n)/2} == 1 (mod n) jedan od koraka. Ako ispadne da je ova kongruencija zadovoljena, onda odmah imamo zakljucak da a nije primitivni korijen. U protivnom nastavljamo s ostalim prostim faktorima od phi(n).
[quote]
npr. modulo 23:
23 je prost , gleda se euler od 22 ->ima 11
i sad uzmem npr. 2^11=32*64 {tj. 2^5*2^6 da li to sama tako biram?}==9*(-5)==1(mod 23)
otkud mi ovo 9*(-5)? jasno mi je da se pokušava zadovoljiti taj uvijet 1(mod n), pa taj br nije primitivan korijen ali nije mi jasno kako dobijem ove brojeve izmeđju 32*64 i 9*(-5); ovo 9 je kao 32-23, a -5 je 64-23-23-23, ali zašto se baš tu staje?
i sad se kao dobije da 2 nije, pa se uzme 3 pa tako redom?[/quote]
Jednostavno treba (na bilo koji nacin) izracunati ostatak broja 2^11=2048 pri dijeljenju s 23. Mozda je najjednostavnije podijeliti ta dva broja (dobije se kvocijent 89 i ostatak 1). Ja sam (na ploci, pa kasnije i u skripti) pokusao minimizirati racun, tako da sve ostatke mogu izracunati napamet. Nadam se da je jasno da je 32==9 (mod 23) i 64==-5 (mod 23), a takodjer i 9*(-5)=-45 == -45+2*23 == 1 (mod 23). No, lako je moguce da je ovaj moj nacin racunanja ovog ostatka nepotrebno kompliciranje. U svakom slucaju, na ovom mjestu treba naci ostatak pri dijeljenju broja 2048 s 23.
| Citat: | kak se ti korijeni određuju?? Stavim neki prost broj na 1/2eulerove funkc. ==1 (mod n)
jel? pa se onda gleda kad nije? |
Da bi se provjerilo je li broj a primitivni korijen, provjerava se vrijedi li za neki prirodan broj k manji od phi(n) da je a^k== 1 (mod n).
U slucaju kada je n prost broj, onda je phi(n)=n-1. Tada je dovoljno provjeriti gornju kongruenciju za brojeve k oblika (n-1)/q, gdje su q-ovi prosti faktori od n-1. To znaci da ispitivanje kongruencije a^{phi(n)/2} == 1 (mod n) jedan od koraka. Ako ispadne da je ova kongruencija zadovoljena, onda odmah imamo zakljucak da a nije primitivni korijen. U protivnom nastavljamo s ostalim prostim faktorima od phi(n).
| Citat: |
npr. modulo 23:
23 je prost , gleda se euler od 22 →ima 11
i sad uzmem npr. 2^11=32*64 {tj. 2^5*2^6 da li to sama tako biram?}==9*(-5)==1(mod 23)
otkud mi ovo 9*(-5)? jasno mi je da se pokušava zadovoljiti taj uvijet 1(mod n), pa taj br nije primitivan korijen ali nije mi jasno kako dobijem ove brojeve izmeđju 32*64 i 9*(-5); ovo 9 je kao 32-23, a -5 je 64-23-23-23, ali zašto se baš tu staje?
i sad se kao dobije da 2 nije, pa se uzme 3 pa tako redom? |
Jednostavno treba (na bilo koji nacin) izracunati ostatak broja 2^11=2048 pri dijeljenju s 23. Mozda je najjednostavnije podijeliti ta dva broja (dobije se kvocijent 89 i ostatak 1). Ja sam (na ploci, pa kasnije i u skripti) pokusao minimizirati racun, tako da sve ostatke mogu izracunati napamet. Nadam se da je jasno da je 32==9 (mod 23) i 64==-5 (mod 23), a takodjer i 9*(-5)=-45 == -45+2*23 == 1 (mod 23). No, lako je moguce da je ovaj moj nacin racunanja ovog ostatka nepotrebno kompliciranje. U svakom slucaju, na ovom mjestu treba naci ostatak pri dijeljenju broja 2048 s 23.
|
|
| [Vrh] |
|
|
