[es] - Multiplicative order

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Multiplicative order

^{04.06.2005. u 01:26 - pre 229 meseci}

Pronaći barem jedan ceo broj čiji je red po modulu 101 jednak 100.
Dakle, treba naći takvo

da važi

,
ali da

nema rešenja ni za jedno

.

Pomoću kompjutera sam pronašao svih 40 mogućih rešenja, ali to sigurno nije
ono što je autor imao na umu...
Ako neko ima elementarno rešenje, neka pošalje...

P.S. Ako je od neke pomoći, iz uslova zadatka (trivijalno) slede:

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

milicas
milica stankovic
beograd

Član broj: 58370
Poruke: 35
*.r62.logikom.net.

Profil

Re: Multiplicative order

^{04.06.2005. u 09:54 - pre 229 meseci}

Jel bi mogao da ponovis tacno text zadatka kako ide?

Jer, sta je red nekog celog broja? Beskonacno, osim ako nije 0 ili se ne radi o nekom elementu

grupe, i to u odnosu na sabiranje. Ili mozda

(svi invertibilni iz

), to je grupa u odnosu na

...

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Multiplicative order

^{04.06.2005. u 10:29 - pre 229 meseci}

Kada kažem, "red" elementa

u grupi

mislim na prvi pozitivan ceo broj

za koji
važi

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..

Profil

Re: Multiplicative order

^{04.06.2005. u 12:45 - pre 229 meseci}

Dokazacemo da je red dvojke po modulu 101 bas 100.

neka je

. Onda

tj.

. Ako je

, onda

ili

. Ali:

(mod 101)
i

(mod 101),
pa mora biti

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Multiplicative order

^{04.06.2005. u 21:20 - pre 229 meseci}

Da, to je sasvim korektan dokaz, i nemojte pogrešno da me shvatite, ali kada
već unapred znam da je red nekog elementa 100, isplati se potruditi se
oko računa i to pokazati. Da je ovaj dokaz počeo ispitivanjem npr. broja 5,
pokazalo bi se (nažalost ne baš brzo) da 5 nije onaj koga tražimo.
Nije teško zamisliti sličnu situaciju, u kojoj bi umesto 101 bio neki drugi značajno
veći prost broj i gde sistem nasumičnih pokušaja (verovatno) ne bi bio isplativ.

Dakle, bilo bi zgodno imati, ako ništa drugo, a ono bar neki uvid u to koje brojeve
ne bi trebalo testirati.

P.S. Srđane, stekao sam utisak da si (i) ti prvo pustio kompjuter da pronađe
najmanjeg "svedoka" a onda konstruisao dokaz, ako grešim izvini...

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dial.InfoSky.Net.

+2789 Profil

Linux - merenje vremena koje je troši neki proces.

^{16.06.2005. u 14:23 - pre 229 meseci}

Mrzi me da pišem, ali imaš to na adresi

http://www.apfloat.org/prim.html

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Multiplicative order

^{16.06.2005. u 22:38 - pre 229 meseci}

Znači, ako sam te dobro shvatio, Srđanov algoritam je najbolji postojeći?

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dial.InfoSky.Net.

+2789 Profil

Re: Multiplicative order

^{17.06.2005. u 14:09 - pre 229 meseci}

S tim da treba ispitivati samo da li je stepen kanditata reda (p-1)/2q različit od 1 i -1, gde q prelazi preko svih prostih delitelja broja n. Takođe, svi brojevi tog oblika imaju svoj NZD, pa se kandidat prvo digne na taj stepen. Time se postižu neke uštede, ali to je to.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu