1.Prosti brojevi

Prosti brojevi ili prim-brojevi su svi prirodni brojevi djeljivi bez ostatka samo s brojem 1 i sami sa sobom, a veći od broja 1. Prirodni brojevi koji su veći od broja 1, a nisu prosti brojevi nazivaju se složenim brojevima. Na primjer, 5 je prost broj jer je djeljiv samo s 1 i 5, a 6 je složen broj jer osim što je djeljiv s 1 i 6 dodatno može biti podjeljen s brojevima 2 i 3. Napomena: Broj 1 nije ni prost, ni složen.

Čemu prosti brojevi služe?

Prosti brojevi služe pri faktorizaciji, odnosno rastavljanju složenih brojeva na prim-faktore. Svaki složeni broj može se na jedinstven način rastaviti na prim-faktore.

Teorem(osnovni teorem aritmetike): Svaki se prirodan broj može prikazati kao produkt prostih faktora. Slijedi da se svaki prirodan broj n može zapisati u kanonskom obliku kao produkt potencija prostih brojeva. $$n = p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$$ Faktorizacija na proste faktore je jedinstvena do na poredak faktora.

Eratostenovo sito

Eratostenovo sito (rešeto) je jednostavan algoritam za dobivanje svih prostih brojeva manjih od unaprijed izabranoga prirodnog broja. Osmislio ga je grčki matematičar, geograf i astronom Eratosten.

Postupak dobivanja prostih brojeva pomoću Eratostenovog sita:

1. napišemo proizvoljan broj uzastopnih prirodnih brojeva počevši od 2

2. zaokružimo najmanji neoznačeni broj

3. precrtamo sve njegove višekratnike, koji nisu već označeni

4. ponavljamo postupak od 2. koraka dok svi brojevi nisu označeni (zaokruženi ili precrtani)

Primjer: Provjeravamo je li prirodan broj 30 prost:

Primjer rastava broja na proste faktore: $$30|2$$ $$15|3$$ $$5|5$$ $$1$$

Definicija:Najveći zajednički djelitelj dvaju brojeva je najveći broj kojim su djeljiva ta dva broja. Na isti se način definira i najveći zajednički djelitelj $nzd$ više brojeva.

Npr., najveći zajednički djelitelj brojeva 2 i 8 je:

Pišemo:$$nzd(2, 8) = 2$$ ili ponekad pišemo $$M(2, 8) = 2 (mjera)$$.Primijetimo da je najveći zajednički djelitelj relativno prostih brojeva jednak 1 pa je $nzd(10,21)$ jednako:

U gornjem primjeru vektorizirali smo našu funkciju * je_li_prost * i zatim smo provjerili za neki random niz koji su brojevi prosti, a koji nisu u njemu.

Definicija: Najmanji zajednički višekratnik dvaju ili više brojeva je najmanji broj koji je djeljiv svim tim brojevima.

Tako je najmanji zajednički višekratnik $(nzv)$ brojeva 6 i 4 jednak:

Dakle: $$nzv(6, 4) = 12$$ ili ponekad kraće $$v(6, 4) = 12 (višekratnik).$$

Relativno prosti brojevi

Relativno prosti brojevi su prirodni brojevi koji nemaju zajedničkog djelitelja osim 1.

Primjer: Provjeravamo jesu li prirodni brojevi 48 i 57 relativno prosti:

*Sljedeći kod računa Eulerovu funkciju nekog prirodnog broja: Npr. n=10 *

EUKLIDOV ALGORITAM: Za prirodne brojeve a i b vrijedi: $$nzd(a, b) = nzd(a, a − b).$$

Koristeći Euklidov algoritam izračunajmo $nzd(32,48)$:

Neka još neodgovorena pitanja o prostim brojevima su:

1. Postoji li općenita formula koja izračunava $n$-ti prosti broj?

2. Postoji li formula za izračunavanje $n$-tog prostog broja $p_n$?

3. Postoji li formula za izračunavanje prvog sljedećeg prostog broja, $p_n+1$, nakon što je zadan prethodni prosti broj $p_n$?

4. Koliko je prostih brojeva manjih od nekog zadanog broja $x \in\mathbb{Q}$?

Teorem: Postoji beskonačno mnogo prostih brojeva.

Najveći dosad pronađeni prosti broj je: $$2^{74.207.281}-1.$$

Taj broj ima nevjerovatnih 22.338.618 cifara i nemoguće ga je napisati u njegovom originalnom obliku. Međutim u sljedećem videu možete vidjeti knjigu koja se sastoji od svih cifara tog prostog broja:

Fermatovi brojevi

Definicija: Brojevi $f_n = 2^{2^n} + 1$ zovu se Fermatovi brojevi.

Napomena: Fermat je smatrao da su svi brojevi ovog oblika prosti. Zaista, $f_0 = 3,\,f_1 = 5,\,f_2 = 17,\, f_3 = 257,\,f_4 = 65537$ jesu prosti brojevi. No, $f_5 = 232 + 1$ nije prost jer $641 |\, f_5$. Postoji hipoteza koja kaže da je samo konačno mnogo Fermatovih brojeva koji su prosti.

Fermatov broj $F_n = 2^{2^n} + 1$ za $n ≥ 1$ može se geometrijski prikazati kao kvadrat s duljinom stranice $2^{2^{n−1}}$ uvećan za jedinični kvadrat. Zaista, $F_n = (2^{2^{n−1}})^2 + 1$.

Definicija: S $\pi(x)$ ćemo označavati broj prostih brojeva $p$ takvih da je $p \leqslant x$. Godine 1896. Hadamard i de la Valle Poussin su pokazali da je $\pi(x) \sim \frac{x}{ln x}$.

Kriptiranje podataka

*Još u doba Cezara, prije više od 2000 godina, ljudi su se bavili problemom zaštite poruka i raznih podataka od čitatelja kojima oni nisu bili namijenjeni. Tako je, na primjer, Cezar smislio jednostavan način zaštite poruka: svako slovo u poruci zamijenio je sa nekim slovom koje je bilo ispred njega u abecedi za određeni pomak. Na primjer, slovo a mijenjao bi slovom c, slovo b slovom d itd. Broj mjesta za koje se slova pomiču u abecedi je vrsta kriptografskog ključa. Primatelj tako kriptirane poruke jednostavno bi učinio suprotno od pošiljatelja, tj. umjesto c pisao a itd., te tako pročitao skrivenu poruku. Iako jednostavan i vrlo nesiguran način kriptiranja podataka, posjeduje jedno temeljno svojstvo koje je i danas potrebno u mnogim kriptografskim primjenama: i pošiljatelj i primatelj moraju poznavati ključ pomoću kojega je obavljena enkripcija. Takva metoda enkripcije poznata je pod nazivom metoda tajnog ključa. Nije teško zamisliti slučajeve u kojima metoda tajnog ključa nije efikasna. Na primjer, kupac želi kupiti robu preku interneta, ali ne želi da podaci o njegovoj kreditnoj kartici, koje šalje prodavaču, budu dostupni nekoj trećoj osobi. Kako to učiniti? Podaci dakako trebaju biti kriptirani dok se šalju, ali kako će i pošiljatelj i primatelj u ovom slučaju znati tajni ključ? Jedno od mogućih rješenja ovog problema je korištenje metode kriptiranja pomoću javnog ključa. Poruka se kriptira jednim ključem, a dekriptira drugim. U nastavku, razmatramo jednu čestu i vrlo važnu metodu takvog kriptiranja podataka, RSA. Prosti brojevi se koriste za kriptiranje podataka. *

RSA

*RSA je algoritam za enkripciju pomoću javnog ključa: koristeći javni ključ, koji je svima dostupan, svatko može kriptirati poruku koja je upućena onome tko je ključ objavio. Međutim, pomoću javnog ključa moguće je samo kriptirati, a ne i dektriptirati poruke. Kriptiranu poruku moguće je dekriptirati samo pomoću tzv. tajnog ključa, koji je poznat samo osobi koja je objavila javni ključ. Javni i tajni ključ su matematički povezani i teoretski je moguće izračunati jedan iz drugog (veza će biti detaljno prikazana kasnije), međutim, smatra se da uz današnje poznavanje matematike i današnje brzine računala, to nije moguće učiniti u nekom razumnom vremenu, te se stoga RSA smatra sigurnim algoritmom. Jedna od poznatijih praktičnih primjena RSA je za siguran transfer podataka preko interneta: osobnih podataka, a posebno novčanih transakcija. Naziv RSA nastao je od početnih slova imena troje ljudi koji su ga prvi javno objavili: Ron Rivest, Adi Shamir i Leonard Adleman. Oni su tu objavu učinili 1977. godine. Kasnije se ispostavilo da je Cllifford Cocks, britanski matematičar koji je radio za britansku tajnu službu, otkrio identičan kriptografski sustav već 1973.; međutim, obzirom na visoku cijenu računala koja su tada mogla izvoditi takve algoritme, prijedlog nije zaživio u stvarnosti. K tome, Cocksovo otkriće je nosilo oznaku „top secret“, te je ono postalo poznato javnosti tek 1997. Tako je RSA trojka ostala zapisana u povijesti kao izumitelj tog važnog algoritma. *