pitanje iz matematike

Naučna otkrića, edukacija, školstvo, univerziteti, fakulteti...
Post Reply
fl00d
Posts: 6
Joined: 13/05/2010 19:03

pitanje iz matematike

Post by fl00d » 11/04/2011 21:41

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


User avatar
Duhovni Vođa
Posts: 758
Joined: 16/08/2008 08:35
Location: I shall release you all!

Re: pitanje iz matematike

Post by Duhovni Vođa » 11/04/2011 21:46

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

User avatar
vesna555
Posts: 565
Joined: 01/11/2010 22:30
Location: Sarajevo

Re: pitanje iz matematike

Post by vesna555 » 11/04/2011 21:50

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


:lol: :lol: :thumbup: I meni je on prvi pao na pamet :D

User avatar
Not My Idea
Posts: 14654
Joined: 15/03/2011 23:12

Re: pitanje iz matematike

Post by Not My Idea » 11/04/2011 21:54

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

:thumbup:
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
Posts: 6
Joined: 13/05/2010 19:03

Re: pitanje iz matematike

Post by fl00d » 11/04/2011 22:05

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

zelenashica
Posts: 14490
Joined: 19/08/2007 02:54

Re: pitanje iz matematike

Post by zelenashica » 11/04/2011 22:24

fl00d wrote:hahahha cuj na wc skoljki. :lol: :lol: pa ima li njega cesto na forumu?

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

User avatar
nellington
Posts: 10761
Joined: 11/03/2008 13:32
Location: navedeno lice se udaljilo u nepoznatom pravcu.

Re: pitanje iz matematike

Post by nellington » 11/04/2011 22:31

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
Posts: 6
Joined: 13/05/2010 19:03

Re: pitanje iz matematike

Post by fl00d » 11/04/2011 22:45

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.

User avatar
Bloo
Globalna šefica
Posts: 35777
Joined: 16/01/2008 23:03
Location: Korriban
Has thanked: 25 times
Been thanked: 17 times

Re: pitanje iz matematike

Post by Bloo » 11/04/2011 22:46

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

User avatar
vesna555
Posts: 565
Joined: 01/11/2010 22:30
Location: Sarajevo

Re: pitanje iz matematike

Post by vesna555 » 11/04/2011 22:49

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 :D

User avatar
.Irfan.
Posts: 286
Joined: 29/08/2010 17:10
Location: I reject your reality and substitute my own...

Re: pitanje iz matematike

Post by .Irfan. » 11/04/2011 23:17

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

User avatar
nellington
Posts: 10761
Joined: 11/03/2008 13:32
Location: navedeno lice se udaljilo u nepoznatom pravcu.

Re: pitanje iz matematike

Post by nellington » 12/04/2011 08:27

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

Post Reply