Praštevila: definicija, lastnosti, primeri in odprte težave
Praštevilo je naravno število večje od 1, ki nima drugih pozitivnih deliteljev razen 1 in samega sebe. To pomeni, da za praštevilo p ne obstajata naravni števili m in n, večji od 1, z m × n = p. Število 1 ni praštevilo (in tudi ni sestavljeno število). Sestavljeno število je vsako naravno število > 1, ki ima vsaj enega dodatnega delitelja; na primer najmanjše sestavljeno število je 4, ker 2 × 2 = 4. Najmanjše praštevilo je 2 (edino sodo praštevilo). Nekaj prvih praštevil: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Praštevil ni največjega – množica praštevil je neskončna.
Lastnosti
- Edinstvena praštevilna faktorizacija: po osnovnem izreku aritmetike (Fundamental Theorem of Arithmetic) ima vsako število > 1 enolično razčlenitev na praštevila (do vrstnega reda faktorjev).
- Infinitnost: drži, da praštevil obstaja neskončno (klasičen Evklidov dokaz).
- Parnost: 2 je edino sodo praštevilo; vsa ostala praštevila so liha.
- Razporeditev: praštevil se z večanjem števil hitro redči; gostota praštevil približno sledi približku x / log x (Prime Number Theorem). O tem podrobneje govori teorem o praštevilskih številih.
- Posebne vrste: dvojčka praštevil (npr. 11 in 13), Mersennova praštevila (oblike 2^p − 1, kjer je p praštevilo), Sophie Germain praštevila idr.
Primeri in posebni pojmi
- Dvojčka praštevil: pari praštevil, ki se razlikujeta za 2 (npr. 3 in 5, 11 in 13).
- Mersennova praštevila: števila oblike 2^p − 1; za določene eksponente p so ta števila praštevila in pogosto dajejo največja znana praštevila.
- Kompozitna razcepnost: primer: 84 = 2^2 × 3 × 7.
Kako preveriti praštevilskost
Pri majhnih številih zadostuje deljenje z vsemi praštevilskimi delitelji do kvadratnega korena števila (trial division). Za večja števila pa obstajajo hitrejše metode:
- Eliminacijske metode: sito Eratostenovo učinkovito najde vse praštevila do dane meje.
- Verjetnostni testi: npr. Miller–Rabin, Fermatov test; hitro dajo odgovor z zelo majhno verjetnostjo napake in se pogosto uporabljajo pri iskanju velikih praštevil.
- Deterministični testi: npr. AKS (Agrawal–Kayal–Saxena) zagotavlja determinističen polinomni čas, obstajajo tudi praktične metode, kot je ECPP (Elliptic Curve Primality Proving), ki za dano število izpelje formalni dokaz, da je praštevilo.
- Praktično: za kriptografijo se pogosto uporabljajo kombinacije hitro verjetnostnih testov in nato formalno dokazovanje, kadar je to potrebno.
Največja praštevila in iskanje
Čeprav največjega praštevil ni, se matematično in računalniško intenzivno iščejo "največja znana" praštevila. Pogosto so to Mersennova praštevila, ker za njih obstajajo učinkoviti testi (Lucas–Lehmerov test). Iskanja velikih praštevil potekajo s projektom GIMPS in drugimi sodelovanji; najdena največja znana praštevila so izredno dolga (imajo milijone števk). Te vrednosti se s časom spreminjajo, zato je za aktualne rekorde smiselno preveriti najnovejše vire.
Odprte težave
- Goldbachova domneva: vsako sodo število > 2 naj bi bilo vsota dveh praštevil — to je še vedno nerešeno in je ena klasičnih odprtih problemov v teoriji števil (glej Goldbachova domneva).
- Domneva o dvojčkih praštevil: ali obstaja neskončno mnogo dvojčk praštevil, še ni dokazano (t. i. Twin Prime Conjecture).
- Riemannova hipoteza: globoko povezana z razporeditvijo praštevil; če bi bila dokazana, bi dalo to natančnejše ocene o odstopanjih števila praštevil od pričakovane gostote.
Uporabe
Praštevila imajo številne praktične uporabe, največja pa je v kriptografiji (npr. RSA), kjer so za varnost potrebna velika praštevila in težave fakorizacije sestavljenih števil. Uporabljajo se tudi v računalniških algoritmih, verjetnostnih metodah, kodiranju in pri generiranju naključnih struktur.
Za nadaljnje učenje so koristni viri o teoriji števil, algoritmih za testiranje praštevil in specialnih vrstah praštevil (npr. Mersennova, Fermatova, Sophie Germain). Če želite, lahko dodam primer algoritma za preverjanje praštevil ali kratka koda za sito Eratostenovo.
O praštevilskih številih lahko razmišljamo še na drug način. Število 12 ni praštevilo, ker lahko iz njega naredimo pravokotnik s stranicama dolžine 4 in 3. Ta pravokotnik ima površino 12, ker je uporabljenih vseh 12 blokov. Tega ni mogoče narediti z 11. Ne glede na to, kako je pravokotnik urejen, bodo vedno ostali bloki, razen za pravokotnik s stranicama dolžin 11 in 1. 11 mora biti torej praštevilo.
Kako najti majhna praštevilska števila
Obstaja preprosta metoda za iskanje seznama praštevil. Ustvaril jo je Eratosten. Imenuje se Eratostenovo sito. V njem se ujamejo števila, ki niso praštevilska (kot v situ), praštevilska števila pa gredo skozi.
Metoda deluje s seznamom števil in posebnim številom, imenovanim b, ki se med izvajanjem metode spreminja. Med izvajanjem metode nekatera števila na seznamu obkrožite, druga pa prečrtate. Vsako obkroženo število je praštevilo in vsako prečrtano število je sestavljeno. Na začetku so vsa števila navadna: niso obkrožena in niso prečrtana.
Metoda je vedno enaka:
- Na list papirja napišite vsa cela števila od 2 do preverjanega števila. Ne zapišite števila 1. Preidite na naslednji korak.
- Začnite z b, ki je enako 2. Pojdite na naslednji korak.
- Na seznamu obkrožite b. Pojdite na naslednji korak.
- Začni z b, preštej še b na seznamu in to številko prečrtaj. Ponavljajte štetje še za b številk in prečrtavanje številk do konca seznama. Preidite na naslednji korak.
- (Na primer: Če je b 2, obkrožite 2 in prečrtajte 4, 6, 8 itd. Če je b 3, boste obkrožili 3 in prečrtali 6, 9, 12 itd. Število 6 in 12 je že prečrtano. Ponovno ju prečrtajte.)
- Povečajte b za 1. Pojdite na naslednji korak.
- Če je bil b prečrtan, se vrnite na prejšnji korak. Če je b številka s seznama, ki ni bila prečrtana, pojdite na 3. korak. Če b ni na seznamu, pojdite na zadnji korak.
- (To je zadnji korak.) Končali ste. Vsa praštevilska števila so obkrožena, vsa sestavljena števila pa prečrtana.
Na primer, to metodo lahko uporabite za seznam števil od 2 do 10. Na koncu bodo obkrožena števila 2, 3, 5 in 7. To so praštevila. Številke 4, 6, 8, 9 in 10 bodo prečrtane. To so sestavljena števila.
Ta metoda ali algoritem traja predolgo za iskanje zelo velikih praštevil. Vendar je manj zapleten kot metode, ki se uporabljajo za zelo velika praštevilska števila, na primer Fermatov test primarnosti (test, s katerim ugotovimo, ali je število praštevilo ali ne) ali Miller-Rabinov test primarnosti.
Za kaj se uporabljajo praštevila
Prva števila so zelo pomembna v matematiki in računalništvu. V nadaljevanju je navedenih nekaj primerov uporabe v resničnem svetu. Zelo dolga števila je težko rešiti. Težko je najti njihove prafaktorje, zato se za šifriranje in tajne kode največkrat uporabljajo števila, ki so verjetno praštevila.
- Večina ljudi ima bančno kartico, s katero lahko na bankomatu dvignejo denar s svojega računa. Ta kartica je zaščitena s tajno kodo za dostop. Ker mora biti koda tajna, je na kartici ni mogoče shraniti v odprtem besedilu. Za tajno shranjevanje kode se uporablja šifriranje. Pri šifriranju se uporabljajo množenje, deljenje in iskanje ostankov velikih praštevil. V praksi se pogosto uporablja algoritem, imenovan RSA. Uporablja kitajski teorem o preostanku.
- Če ima nekdo digitalni podpis za svoje e-poštno sporočilo, se uporablja šifriranje. S tem je zagotovljeno, da nihče ne more ponarediti njegovega e-poštnega sporočila. Pred podpisovanjem se ustvari hash vrednost sporočila. Ta se nato združi z digitalnim podpisom, da nastane podpisano sporočilo. Uporabljene metode so bolj ali manj enake kot v prvem primeru zgoraj.
- Iskanje največjega doslej znanega prime je postalo svojevrsten šport. Če je število veliko, je preverjanje, ali je praštevilo praštevilo, lahko težavno. Največja kadar koli znana praštevilska števila so običajno Mersennova števila, saj je najhitrejši znani test za preverjanje prvobitnosti Lucas-Lehmerjev test, ki temelji na posebni obliki Mersennovih števil. Skupina, ki išče Mersennova praštevilska števila, je tukaj[1].
Vprašanja in odgovori
V: Kaj je praštevilo?
O: Praštevilo je naravno število, ki ga ni mogoče deliti z nobenim drugim naravnim številom, razen z 1 in samim seboj.
V: Kaj je najmanjše sestavljeno število?
O: Najmanjše sestavljeno število je 4, ker je 2 x 2 = 4.
V: Katera so naslednja praštevilska števila za 2?
O: Naslednja praštevilska števila za 2 so 3, 5, 7, 11 in 13.
V: Ali obstaja največje praštevilo?
O: Ne, največje praštevilo ne obstaja. Množica praštevil je neskončna.
V: Kaj pravi temeljni stavek aritmetike?
O: Temeljni stavek aritmetike pravi, da lahko vsako pozitivno celo število zapišemo kot zmnožek praštevil na edinstven način.
V: Kaj je Goldbachova domneva?
O: Goldbachova domneva je nerešen problem v matematiki, ki pravi, da lahko vsako celo število, večje od dva, izrazimo kot vsoto dveh praštevil.
V: Kdo je zapisal dokaz, da ni največjega praštevilskega števila?
O: Evklid je zapisal dokaz, da ni največjega praštevilskega števila.
