Slučajan prost broj
U računarskoj teoriji brojeva, mnoštvo algoritama omogućava efikasno generisanje prostih brojevima. Oni se koriste u različitim aplikacijama, na primer heširanju, kriptografiji sa javnim ključem, i u potrazi za prost deliocem u velikom broju.
Za relativno male brojeve, moguće je primeniti samo prebrajanje delilaca na svaki naredni neparan broj. Prosta sita su gotovo uvek brža.
Osnovna sita[uredi | uredi izvor]
Prosto sito ili sito prostog broja je brz tip algoritma za pronalaženje prostih brojeva. Postoji mnogo prostih sita. Jednostavno je Eratostenovo sito (250. p. n. e.), Sundaramovo sito (1934), i još brže, ali komplikovanije Atkinovo sito (2004),[1] a razna kružna rastavljanja se najčešće javljaju.[2]
Prosta sita kreiraju liste svih celih brojeva do željene granice i postepeno uklanjanjaju složene brojeve (koji se direktno generišu) dok samo prosti ostaju. Ovo je najefikasniji način da se dobije veliki asortiman prostih brojeva. Međutim, da bi se pronašli pojedinačni prosti brojevi, direktni prosti testovi su efikasniji. Nadalje, na osnovu formalizama sita, neke celobrojne sekvence (sekvenca A240673 u OEIS) su konstruisane za korišćenje u generisanju prostih brojeve u određenim intervalima.
Veliki prosti brojevi[uredi | uredi izvor]
Za velike proste brojeve koji se koriste u kriptografiji, uobičajeno je koristiti modifikovani oblik prosejavanja: nasumično izabran opseg neparnih brojeva željene veličine je prosejan za relativno male proste brojeve (tipično sve proste brojeve manje od 65.000). Preostali prosti brojevi se testiraju po slučajnom izboru sa standardnim probabilističkim testom, kao što je Bejli-PSV prost test ili Miler—Rabinov test koji radi za moguće proste brojeve.
Alternativno, postoje brojne tehnike za efikasno dokazivanje prostih brojeva. Ovo uključuje stvaranje prostih brojeva p za koje je rastavljanje na brojeve p - 1 ili P + 1 ako je poznato, na primer Marsenovi prosti brojevi, FERMAT prostih brojeva i njihove generalizacije.
Složenost[uredi | uredi izvor]
Eratostenovo sito se generalno smatra najlakšim sitom za implementaciju, ali nije najbrži u smislu brojeba operacija za veliki opseg. U svom uobičajenom standardnom sprovođenju (što može uključivati osnove tačka razlaganja za male proste brojeve), može naći sve proste brojeve u N u vremenu O (Nlog log N), dok osnovne implementacije u Atkinovo sito i kružno rastavljanje rade u linearnom vremenu O(N). Posebne verzije Eratostenovog sita pomoću točka sito mogu imati isti linearni O (n) kompleksnost vremena. Posebna verzija sita Atkin i neke specijalne verzije točkova sita koji mogu uključivati prosejavanje koriste metode iz Eratostenovog sito koje mogu pokrenuti u sublinear vremenske kompleksnosti O (Nlog log N). Imajte na umu da samo zato što je algoritam smanjena asimptotska kompleksnost vremena ne znači da praktična primena radi brže nego algoritam sa većom asimptotskom složenošću vremena: Ako kako bi se postigla ta manja asimptotska složenost pojedine operacije imaju konstantan faktor povećane složenosti vremena, pa može biti mnogo veća za jednostavnije algoritme, to nikada neće biti moguće u okviru praktičnog prosejavanja opsega za prednost smanjenog broja operacija za razumno velika okruženja da se iskupe za dodatne troškove u vremenu po operaciji.
Jednostavna naivna "velika prosejavanja reda " sita bilo koje od ovih sita vrste se memorijskim prostor od oko O (n), što znači da: 1) oni su veoma ograničeni u prosejavanju i mogu se nositi u iznosu od RAM memorije na raspolaganju i 2) da su obično prilično spori, jer brzina pristupa RAM memorije obično postaje usko grlo brzine veće od izračunavanja brzine kada veličina niza raste izvan veličine CPU keša. Normalno sprovođenje stranica podelom sita oba Eratosena i Atkinova je prostor O (n /log N), plus malo sito segmenata pufera koji su obično veličine da stane unutar veličina CPU keša; stranica segmentiranog lakog sita uključuje specijalne varijacije sita ili Eratosena obično je potrebno mnogo više prostora nego faktora da bi spasili potrebne izjave točka; Pričardova varijacija linearnog vremena složenosti eratostenovo sito / točkova sito je O(N1/2log log N/log N). Bolja vremenska kompleksnost posebne verzije sita Atkin zauzima prostor N1/2+o(1). Sorenson[3] pokazuje poboljšanje za sito koja uzimaju još manje prostora u O(N/((log N)Llog log N)) od L > 1. Međutim, sledeće je opšte zapažanje: količina memorije se smanjuje, što je veći stalni porast faktora u troškovima u vremenu po operaciji, iako je asimptotska kompleksnost vremena može ostati ista, što znači da memorijski smanjena verzija može pokrenuti mnogo puta sporiji od ne memorijski smanjene verzije kod prilično velikih faktora.
Vidi još[uredi | uredi izvor]
Reference[uredi | uredi izvor]
- ^ Atkin, A. O. L.; Bernstein, D. J. (2003). „Prime sieves using binary quadratic forms”. Mathematics of Computation. 73 (246): 1023—1030. doi:10.1090/S0025-5718-03-01501-1..
- ^ Pritchard, Paul (1994). Improved Incremental Prime Number Sieves. Algorithmic Number Theory Symposium. pp. 280–288. CiteSeerX: 10.
- ^ Sorenson, Jonathan P. (1998). „Trading time for space in prime number sieves”. Algorithmic Number Theory. Lecture Notes in Computer Science. 1423. str. 179—195. ISBN 978-3-540-64657-0. doi:10.1007/BFb0054861..