Forum Klix.ba

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

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

Duhovni Vođa wrote:ovo nellington na wc šolji rješava iz razonode.

I meni je on prvi pao na pamet

Duhovni Vođa wrote: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

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

fl00d wrote: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

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).

nellington wrote: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.

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

nellington wrote: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

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

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