pitanje iz matematike

[fl00d]

zdravo forume kako ide.

imam par pitanja pa ako neko hoce nek odgovori.

imam 42^15 mod 113 trebam izracunat. nije mi jasno kako ovo sad ide. znam da je rezultat 35 ali kako do njega doc....

phi(113) = 112 sto je vece od 15.. tako da ne ide..


drugo: 3^a === 54 mod 113. treba nac a. imal neki algoritam da se to izracuna ili moram probavat pa sta ispane ( a ispane 15 ) . hvala ako se ko nadje da pomogne.

pozdrav

[Duhovni Vođa]

ovo nellington na wc šolji rješava iz razonode.

[vesna555]

ovo nellington na wc šolji rješava iz razonode.

I meni je on prvi pao na pamet

[Not My Idea]

ovo nellington na wc šolji rješava iz razonode.

Mora da je lijep osjecaj kad te 90% raje s ovog foruma smatra pametnim (genijem)
a svi znamo koliko je to pod nasim nebom tesko postic

[fl00d]

hahahha cuj na wc skoljki. pa ima li njega cesto na forumu?

[zelenashica]

hahahha cuj na wc skoljki. pa ima li njega cesto na forumu?

Naleti počesto.Ako ga sretnemo na drugoj temi pošaljemo ga vamo

[nellington]

Moj je prijedlog da kad se susretneš sa ovakvim problemom ne tražiš predugo caku. Ne može Euler, ne može Carmichael, može šta može - square and multiply. Trebaju ti svega tri koraka - drugi stepen, četvrti stepen, osmi stepen - i sve ih izmnožiš. Ako već tražiš caku, primjeti da je 42^16 kongruentno 1 mod 113 (zašto?).

Što se drugog zadatka tiče, nisam se udubljivao ali na prvi pogled ne vidim ništa drugo da možeš pokušati osim klasičnih algoritama za traženje diskretnog logaritma - ima ih svakakvih, ali nema idealnih. Nešto što možeš uraditi je da tragaš za rješenjem od 3^(a-3)=2 mod 113, jer je jednostavnije... Ali opet kažem - caku ne vidim (iako sam oba zadatka gledao 5 min, možda nešto bitno previđam, javim se kad imadnem više vremena).

[fl00d]

Moj je prijedlog da kad se susretneš sa ovakvim problemom ne tražiš predugo caku. Ne može Euler, ne može Carmichael, može šta može - square and multiply. Trebaju ti svega tri koraka - drugi stepen, četvrti stepen, osmi stepen - i sve ih izmnožiš. Ako već tražiš caku, primjeti da je 42^16 kongruentno 1 mod 113 (zašto?).

Što se drugog zadatka tiče, nisam se udubljivao ali na prvi pogled ne vidim ništa drugo da možeš pokušati osim klasičnih algoritama za traženje diskretnog logaritma - ima ih svakakvih, ali nema idealnih. Nešto što možeš uraditi je da tragaš za rješenjem od 3^(a-3)=2 mod 113, jer je jednostavnije... Ali opet kažem - caku ne vidim (iako sam oba zadatka gledao 5 min, možda nešto bitno previđam, javim se kad imadnem više vremena).

42^16 === 1 mod 113

phi(113) = 112
112 = 7*16

42^0 = 1 mod 113

ok


drugi zadatak je takav kakav jest. probavanjem naci rjesenje i gotovo. vidjecu za par dana na tutorijumu pa cu ovdje napisat.

sa prvim cu probat sta si napisao.

hvala ti puno nellington.

[Bloo]

predlazem nellingtona za glavi lik u seriji Numbers mozda postane zanimljivija zelim vise jednacina da vidim

[vesna555]

Moj je prijedlog da kad se susretneš sa ovakvim problemom ne tražiš predugo caku. Ne može Euler, ne može Carmichael, može šta može - square and multiply. Trebaju ti svega tri koraka - drugi stepen, četvrti stepen, osmi stepen - i sve ih izmnožiš. Ako već tražiš caku, primjeti da je 42^16 kongruentno 1 mod 113 (zašto?).

Što se drugog zadatka tiče, nisam se udubljivao ali na prvi pogled ne vidim ništa drugo da možeš pokušati osim klasičnih algoritama za traženje diskretnog logaritma - ima ih svakakvih, ali nema idealnih. Nešto što možeš uraditi je da tragaš za rješenjem od 3^(a-3)=2 mod 113, jer je jednostavnije... Ali opet kažem - caku ne vidim (iako sam oba zadatka gledao 5 min, možda nešto bitno previđam, javim se kad imadnem više vremena).

Priznaj da si sad pod pritiskom jer smo te nahvalili

[.Irfan.]

evo da ne bude da i ja nesto od nellingtona nisam naucio (imo vezane zadatke iz iste materije)

42^15 mod 113 (mod 113 se u svakom redu od sad podrazumijeva)
= 42*42^2*42^4*42^8= 42*1764*3111696*42^8 =
74088*3111696*42^8=
73*15*42^4*42^4=
1095*3111696*3111969=
78*15*15=
1170*15=
40*15=
35

42^15 ===35 mod 113

[nellington]

Prvo da se zahvalim svima koji su me nahvalili (ne znam čime sam zaslužio ovoliko poštovanje, ali u svakom slučaju hvala vam!)

Sad da se malo vratim na zadatke:

@fl00d: zaključak za 42^16 kongruentno 1 mod 113 nije tako jednostavan kako si ti zaključio (da jeste, onda bi Carmichaelova lambda funkcija broja 113 bila 16, a ona to nije). Međutim, to sa 42^16 ti ne bi puno ni pomoglo - to sam rekao onako usput.

Eh sad, što se .irfan.ovog rješenja tiče, jeste, ovo sam imao na umu, samo nisi morao 42^4 računati, mogao si 69^2, lakše je - iako je to to, prilično elegantno