5. zadaca

[Gost]

1. zadatak, trazimo d iz e*d==1(mod fi(n)), napravim euklidov algoritam za e i fi(n), i gdje dobim d?

[marcel]

potrazite kako se rjesavaju kongruencije
ax=b (mod m)

Pozdrav,
Marcel

[mia_]

Moramo li i to na ruke ili za taj dio zadatka smijemo koristiti Mathematicu?

[marcel]

Moze na ruke, ne trebate koristiti Mathematicu.



Pozdrav,
Marcel

[Gost]

sto znaci da 2. i 3. zadatak ne smijemo rjesavati faktorizacijom?

[marcel]

Za ovako male brojeve faktorizacija (pomocu npr. Mathematice) bi bila brzo gotova.

Zasto se to ne smije i sto to konkretno znaci?
Ako znate faktorizaciju javno poznatog n=pq, mozete lako izracunati fi(n)=(p-1)(q-1), a iz toga takodjer lako izracunati tajni kljuc d (pomocu prosirenog euklidovog algoritma).

Sigurnost RSA sustava lezi u problemu faktorizacije od n.

Pozdrav,
Marcel

[Gost]

kako u trecem zadatku dobivamo onaj d kako provjerimo da vrijedi 2 na d pa na e je kongruentno recimo 2...kad bi to ubacili u kalkulator izbacio bi nam math eror,jel postoji neki algoritam za to?i konvergente razvijama kao kako smor adili na utbu?

[petrich]

[marcel]

Ne znam ko je taj Guest, ali je sve vise i vise lijen.

[Perosito]

Dal smijemo u 3. zadatku faktorizirati e?
Onda bi mogli to raspisat u smislu:
e=p1^a1*p2^a2*...*pn^an
Zatim napišemo 2^e={[(2^p1^a1)^p2^a2]^...}^pn^an
I onda u svakom koraku (naravno ako broj premaši n) uzmemo modulo n i dobijemo neki broj a takav da je:
2^e==a(mod n)
Onda provjerimo za q-ove koje smo dobili za koji vrijedi
(2^e)^q==a^q==2(mod n) → uzmemo dakle x=2

Mislim, modularno potenciranje 14-eroznamenkastog broja metodom "kvadriraj i množi" ko na vježbama i u 1. zadatku nije baš najzgodnije rješenje za računat na papiru.

_________________
Nije sve tako sivo... Kad imaš s nekim otić na pivo

[greeneyes]

pa samo u prvom treba mnoziti pjeske, kaj nije tak receno na vjezbama?
za ovo ostalo, Mathematica ima PowerMod npr.

_________________
Am I so different from you
Now does it scare you that I'm able to discern
What to love and what to burn..
Don't judge what you don't understand..

// Disturbed: Fear

[Perosito]

Ma pitam, zato kaj sam ja na početku riješil zadatak na ovaj gore način i sve super, i onda ono pročitam da ne smijemo faktorizirat, onda sam 14-eroznamenkasti broj pretvaral u binarno i one potencije pisal.
Jao, koji bolni postupak!
PS Ovaj PowerMod nisam znal, no čovjek uči dok je živ, pa eto...

_________________
Nije sve tako sivo... Kad imaš s nekim otić na pivo

[petrich]

[Perosito]

Piše, al asistent je spominjao samo faktorizaciju n-a, pa zato pitam. Mislim, nije ni bitno, ja sam riješio sva tri, pa nema veze. Čisto pitam, tak da drugi znaju.

_________________
Nije sve tako sivo... Kad imaš s nekim otić na pivo

[petrich]

[Grga]

Samo za provjeru, je li dozvoljeno onda koristiti mathematicu za racunanje razvoa broja e/n, i opwermod za pronalazenje d?

_________________
Bri

[marcel]

Ajmo ovako - bilo bi najbolje da ja ne znam da koristite Mathematicu.

Mozete koristiti Mathematicu, ali bi bilo najbolje da se to sakrije. Npr. - da u zadaci ne pisete PowerMod i sl.

Pozdrav,
Marcel

[LSSD]

Trebamo li pisati korake euklidovog algoritma u zadnjem zadatku ili je dovoljno napisati da smo tim postupkom dosli do brojeva(pa ih nabrojimo) i onda racunamo konvergente?

_________________
' Zasto jednostavno kad moze i komplicirano?'

[Gost]

moze li mi netko napisati(pojasniti) algoritam za modularni eksponent?
neki primjer?

[Gost]

dakle u 3 zataku mozemo koristiti powermod za racunanje d-a i sifrata?samo to nesmijemo napisati ako sam dobro shvatio,nece nam biti skinuti bodovi,,jel bi cijeli postupak bio jako bolan...