Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI TEORIJA BROJEVA

Primena teorije brojeva

[inlmath]a^p\equiv a\pmod p,\;a\in\mathbb{Z},\;p\in\mathbb{P}[/inlmath]

Primena teorije brojeva

Postod Corba248 » Nedelja, 02. April 2017, 22:00

Pošto se često postavljaju pitanja u vezi s primenom teorije brojeva, ja ću ovde izneti jednu od njih.
Naime, radi se o kriptografiji (šifrovanju) i njenoj vezi sa prostim brojevima. Ako bi dve osobe (Alisa i Bob su standardna imena) želele da razmene određenu informaciju koju ćemo nazvati [inlmath]g[/inlmath] (neki broj) trebalo bi da urade sledeće:
a) prethodno se dogovore da iskoriste neki ogroman prost broj [inlmath]p[/inlmath] (stotine cifara);
b) Alisa odabere [inlmath]g[/inlmath] i digne ga na [inlmath]a[/inlmath]-ti stepen i dobije [inlmath]g^a[/inlmath];
c) potom pošalje Bobu broj [inlmath]g^a\mod p[/inlmath] (ostatak pri deljenju broja [inlmath]g^a[/inlmath] sa [inlmath]p[/inlmath]);
d) Bob potom digne to na [inlmath]b[/inlmath]-ti stepen i pošalje Alisi [inlmath]g^{ab}\mod p[/inlmath];
e) Alisa potom nađe [inlmath]a[/inlmath]-ti koren da bi dobila [inlmath]g^b\mod p[/inlmath] i to pošalje Bobu;
f) potom Bob nađe [inlmath]b[/inlmath]-ti koren da bi našao i sâmo [inlmath]g[/inlmath].
Primetite da broj [inlmath]p[/inlmath] ne mora biti tajna, on se može i javno objaviti (što se i obično radi), to ne može pomoći potencijalnom kradljivcu informacija.



Postoji još jedan način, sličan, koji podrazumeva poznavanje Ojlerove teoreme.
Postupak je sledeći:
Alisa prvo bira dva vrlo velika prosta broja [inlmath]p[/inlmath] i [inlmath]q[/inlmath] (njih drži u tajnosti) i izračuna njihov proizvod [inlmath]N=pq[/inlmath] i javno ga objavljuje. Sada bira proizvoljan broj [inlmath]m[/inlmath] takav da je [inlmath]\bigl(m,\varphi(N)\bigr)=1[/inlmath] pa objavljuje i njega. Takođe nalazi i broj [inlmath]d[/inlmath] koji zadovoljava linearnu kongruenciju [inlmath]dm\equiv 1\pmod {\varphi(N)}[/inlmath]. Takav broj nalazimo Euklidovim algoritmom, pod uslovom da je poznat modul [inlmath]\varphi(N)[/inlmath], a njega zna samo Alisa. Zašto? Zato što je [inlmath]\varphi(N)=(p-1)(q-1)[/inlmath] te se može naći samo na osnovu broja [inlmath]N[/inlmath].
Bob koji Alisi šalje poruku šifruje neki broj [inlmath]x[/inlmath] tako što računa njegov ostatak [inlmath]y[/inlmath] pri deljenju [inlmath]x^m[/inlmath] sa [inlmath]N[/inlmath] tj. [inlmath]x^m\equiv y\pmod N[/inlmath].
Alisa za dešifrovanje koristi broj [inlmath]d[/inlmath] (samo njoj poznat) i računa ostatak pri deljenju broja [inlmath]y^d[/inlmath] sa [inlmath]N[/inlmath], pa važi:
[dispmath]y^d\equiv(x^m)^d=x^{md}=x^{k\varphi(N)+1}\equiv x\pmod N[/dispmath] Ovo važi jer je, prema Ojlerovoj teoremi [inlmath]x^{\varphi(N)}\equiv1\pmod N[/inlmath] (uslov [inlmath](x,N)=1[/inlmath] se može smatrati ispunjenim).
Kako je faktorisanje ovako velikih brojeva u današnje vreme nerešiv problem, niko osim Alise nije u mogućnosti da sprovede ovakav postupak.
Oznaka [inlmath](a,b)=d[/inlmath] označava da je [inlmath]d[/inlmath] najveći zajednički delilac (NZD) brojeva [inlmath]a[/inlmath] i [inlmath]b[/inlmath], logično je da [inlmath](a,b)=1[/inlmath] označava da su [inlmath]a[/inlmath] i [inlmath]b[/inlmath] uzajamno/relativno prosti.
Gorepomenuti problemi poznati su kao problem distribucije ključa.
Ovo je jedna od primena teorije brojeva, nadam se da će nekome biti interesantno. :)
Zaslužni forumaš
 
Postovi: 314
Zahvalio se: 37 puta
Pohvaljen: 352 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Primena teorije brojeva

Postod Onomatopeja » Ponedeljak, 03. April 2017, 15:57

Ovo je inace RSA algoritam, ako neko zeli malo vise da gugla da zna kako da vrsi pretragu.
 
Postovi: 613
Zahvalio se: 15 puta
Pohvaljen: 588 puta


Povratak na TEORIJA BROJEVA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 31 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 11:09 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs