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).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. 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]

Također pogledajte[uredi | uredi izvor]

Commons logo
U Wikimedijinom spremniku se nalazi još materijala vezanih uz:

Reference[uredi | uredi izvor]

  1. ^ RSA . Kurs na njemačkoj gimnaziji u Berlinu učitano 18.01.2014 njem.