Случајан прост број
У рачунарској теорији бројева, мноштво алгоритама омогућава ефикасно генерисање простих бројевима. Они се користе у различитим апликацијама, на пример хеширању, криптографији са јавним кључем, и у потрази за прост делиоцем у великом броју.
За релативно мале бројеве, могуће је применити само пребрајање делилаца на сваки наредни непаран број. Проста сита су готово увек бржа.
Основна сита[уреди | уреди извор]
Просто сито или сито простог броја је брз тип алгоритма за проналажење простих бројева. Постоји много простих сита. Једноставно је Ератостеново сито (250. п. н. е.), Сундарамово сито (1934), и још брже, али компликованије Аткиново сито (2004),[1] а разна кружна растављања се најчешће јављају.[2]
Проста сита креирају листе свих целих бројева до жељене границе и постепено уклањањају сложене бројеве (који се директно генеришу) док само прости остају. Ово је најефикаснији начин да се добије велики асортиман простих бројева. Међутим, да би се пронашли појединачни прости бројеви, директни прости тестови су ефикаснији. Надаље, на основу формализама сита, неке целобројне секвенце (секвенца А240673 у ОЕИС) су конструисане за коришћење у генерисању простих бројеве у одређеним интервалима.
Велики прости бројеви[уреди | уреди извор]
За велике просте бројеве који се користе у криптографији, уобичајено је користити модификовани облик просејавања: насумично изабран опсег непарних бројева жељене величине је просејан за релативно мале просте бројеве (типично све просте бројеве мање од 65.000). Преостали прости бројеви се тестирају по случајном избору са стандардним пробабилистичким тестом, као што је Бејли-ПСВ прост тест или Милер—Рабинов тест који ради за могуће просте бројеве.
Алтернативно, постоје бројне технике за ефикасно доказивање простих бројева. Ово укључује стварање простих бројева п за које је растављање на бројеве п - 1 или П + 1 ако је познато, на пример Марсенови прости бројеви, ФЕРМАТ простих бројева и њихове генерализације.
Сложеност[уреди | уреди извор]
Ератостеново сито се генерално сматра најлакшим ситом за имплементацију, али није најбржи у смислу бројеба операција за велики опсег. У свом уобичајеном стандардном спровођењу (што може укључивати основе тачка разлагања за мале просте бројеве), може наћи све просте бројеве у Н у времену О (Нlog log Н), док основне имплементације у Аткиново сито и кружно растављање раде у линеарном времену O(Н). Посебне верзије Ератостеновог сита помоћу точка сито могу имати исти линеарни О (н) комплексност времена. Посебна верзија сита Аткин и неке специјалне верзије точкова сита који могу укључивати просејавање користе методе из Ератостеновог сито које могу покренути у сублинеар временске комплексности О (Нlog log Н). Имајте на уму да само зато што је алгоритам смањена асимптотска комплексност времена не значи да практична примена ради брже него алгоритам са већом асимптотском сложеношћу времена: Ако како би се постигла та мања асимптотска сложеност поједине операције имају константан фактор повећане сложености времена, па може бити много већа за једноставније алгоритме, то никада неће бити могуће у оквиру практичног просејавања опсега за предност смањеног броја операција за разумно велика окружења да се искупе за додатне трошкове у времену по операцији.
Једноставна наивна "велика просејавања реда " сита било које од ових сита врсте се меморијским простор од око О (н), што значи да: 1) они су веома ограничени у просејавању и могу се носити у износу од РАМ меморије на располагању и 2) да су обично прилично спори, јер брзина приступа РАМ меморије обично постаје уско грло брзине веће од израчунавања брзине када величина низа расте изван величине ЦПУ кеша. Нормално спровођење страница поделом сита оба Ератосена и Аткинова је простор О (н /log Н), плус мало сито сегмената пуфера који су обично величине да стане унутар величина ЦПУ кеша; страница сегментираног лаког сита укључује специјалне варијације сита или Ератосена обично је потребно много више простора него фактора да би спасили потребне изјаве точка; Причардова варијација линеарног времена сложености ератостеново сито / точкова сито је O(Н1/2log log Н/log Н). Боља временска комплексност посебне верзије сита Аткин заузима простор Н1/2+o(1). Соренсон[3] показује побољшање за сито која узимају још мање простора у O(Н/((log Н)Llog log Н)) од Л > 1. Међутим, следеће је опште запажање: количина меморије се смањује, што је већи стални пораст фактора у трошковима у времену по операцији, иако је асимптотска комплексност времена може остати иста, што значи да меморијски смањена верзија може покренути много пута спорији од не меморијски смањене верзије код прилично великих фактора.
Види још[уреди | уреди извор]
Референце[уреди | уреди извор]
- ^ 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. стр. 179—195. ISBN 978-3-540-64657-0. doi:10.1007/BFb0054861..