Prost broj

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web-stranice ili drugi izvori).
Ako se pravilno ne potkrijepe validnim izvorima, sporne rečenice i navodi mogli bi biti obrisani. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci te nakon toga možete ukloniti ovaj šablon.

Prost broj je prirodni brojeveći od 1 koji je dijeljiv jedino sa 1 i samim sobom.

Primjeri prostih brojeva su: 2, 3, 5, 7....

Broj a\, ne možemo rastaviti na proste faktore ako je: a=k \cdot l \Rightarrow a=k \lor a=l.

Broj a \, je prost ako je a \, dijeli p \cdot q \Rightarrow a \, dijeli p \, ili a \, dijeli q \,.

Lahko se može dokazati da ako je broj prost onda је i nerastavljiv i obrnuto. Složen broj je broj koji je djeljiv samim sobom, sa 1, te još nekim brojem.

Svaki složeni broj može se na jedinstven način rastaviti na proste faktore:

  125|5      34|2
   25|5      17|17
    5|5       1 
    1
  
  125=5*5*5   34=2*17

Rastavljanje složenih brojeva na proste faktore[uredi | uredi izvor]

Rastavljanje se može postići dijeljenjem s prostim brojevima, međutim, ako znamo neka jednostavna pravila, to rastavljanje postaje vrlo jednostavno.

  • Ako je broj paran (zadnja cifra mu je 2, 4, 6, 8 ili 0) onda je djeljiv s brojem 2.
  • Ako broj završava ciframa 5 ili 0 onda je djeljiv s brojem 5.
  • Ako mu je zbir cifara dijeljiv s 3, onda je taj broj djeljiv s 3.

Kriptografija[uredi | uredi izvor]

Važna primjena prostih brojeva je u oblasti kriptografije. Algoritmi za šifriranje poruke žive od toga sto ne postoji efikasan algoritam za rastavljanje broja na proste faktore. Tako se lahko mogu pomnožiti dva dovoljno velika prosta broja, međutim, obrnuti proces, tj. naći njegove proste faktore traje dosta duže. Poznata šifra koja na tome bazira je RSA [1]

Brojnost prostih brojeva[uredi | uredi izvor]

Prostih brojeva ima beskonačno mnogo. Ovo je prvi dokazao Euklid u svojim Elementima, knjiga X, Teorema 20. Njegov dokaz je sljedeći:

Pretpostavimo da je broj prostih brojeva konačan. Pomnožimo ih sve i dodajmo 1. Dobićemo broj koji podijeljen sa bilo kojim prostim brojem daje ostatak 1. Dobili smo broj koji nema djelitelja među postojećim brojevima. To jeste prost broj veći od prethodnih.

Matematičari su otkrili još osobina koje su vezane za brojnost prostih brojeva. Ojler je otkrio da red recipročnih prostih brojeva divergira. Čak je nađena asimptotska formula za zbir prostih brojeva manjih od nekog datog

\lim_{x\to\infty} \sum_{p<x} \frac{1}{p}\ \sim\ \ln \ln x

Postoji funkcija \pi (x) \, koja ima vrijednost jednaku broju prostih brojeva u intervalu (1, x] \,. Ona daje odgovor na pitanje kolikoima prostih brojeva manjih od datog broja. Primjer: \pi (100000) = 9592\,. Za veće brojeve funkcija glasi:

\pi (x) \sim \frac{x}{\ln x - 1}.

Najveći poznati prost broj[uredi | uredi izvor]

Trenutno najveći poznati prost broj je 230.402.457 − 1 (ovaj broj ima 9.152.052 cifara). Izračunali su ga 15. decembra 2005. godine dva profesora sa Misuri državnog univerziteta. Označava se sa М30402457 i predstavlja 43. Mersenov prost broj.

Prethodni najveći poznati prost broj je bio M25964951 = 225.964.951 − 1 (42. poznati Mersenov prost broj, 7.816.230 cifara) a pre njega M24036583 = 224.036.583 − 1 (41. poznati Mersenov prost broj, 7.235.733 cifara)

Postoji dobar praktičan razlog zašto su svi veliki prosti brojevi oblika Mersenovih prostih brojeva. To je relativno jednostavan metod za provjeru složenosti broja (Lukas-Lemer test). Za ostale brojeve je metoda vremenski zahtjevna.

Najveći prost broj koji nije ovog oblika je 27.653 × 29.167.433 + 1 (2.759.677 cifara) i šesti je po veličini na listi najvećih poznatih prostih brojeva.

Za nalaženje prostog broja sa 107 decimalnih cifara postoji nagrada od 100.000 dolara.

Također pogledajte[uredi | uredi izvor]


Reference[uredi | uredi izvor]