Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Бастапқы сандарды табу алгоритмдері
Algorithms to generate prime numbers
Есептеулік сандар теориясында бастапқы сандарды тиімді түрде табуға мүмкіндік беретін әртүрлі алгоритмдер бар. Олар хэшинг, ашық кілттің криптографиясы және үлкен сандардың жай көбейткіштерін табу сияқты түрлі қолданыстарда қолданылады. Шамалы сандар үшін, кезекті тақ санға сынақ бөлуді қолдануға болады. Бірақ жай сандарды іздеу (просеивание) әлде де жылдам. Жай сандарды іздеу – жай сандарды детерминистік түрде табудың ең жылдам белгілі әдісі. Келесі жай санды есептей алатын белгілі формулалар бар, бірақ келесі жай санды бұрынғы жай сандар арқылы өрнектеудің белгілі жолы жоқ. Сондай-ақ, келесі жай санды детерминистік түрде есептейтін математикалық өрнектің (кейінгі жай сандарды қоса алғанда) тиімді жалпы манипуляциясы немесе кеңейтілуі белгілі емес.
In computational number theory, a variety of algorithms make it possible to generate prime numbers efficiently. These are used in various applications, for example hashing, public key cryptography, and search of prime factors in large numbers. For relatively small numbers, it is possible to just apply trial division to each successive odd number. Prime sieves are almost always faster. Prime sieving is the fastest known way to deterministically enumerate the primes. There are some known formulas that can calculate the next prime but there is no known way to express the next prime in terms of the previous primes. Also, there is no effective known general manipulation and/or extension of some mathematical expression (even such including later primes) that deterministically calculates the next prime.
Басты сырғалар
Бастапқы сүзгі немесе алғашқы сандар сүзгісі – алғашқы сандарды табуға арналған жылдам алгоритм түрі. Көптеген бастапқы сүзгілер бар. Эратоспеннің қарапайым сүзгісі (б.з.д. 250 жылдары), Сундарамның сүзгісі (1934), одан да жылдам, бірақ күрделі Аткиннің сүзгісі (2003) және түрлі дөңгелек сүзгілер ең көп қолданылады. Бастапқы сүзгі, қажетті лимитке дейінгі барлық бүтін сандар тізімін жасау және тек алғашқы сандар қалғанша құрама сандарды (оларды тікелей анықтап шығару арқылы) біртіндеп жою арқылы жұмыс істейді. Бұл алғашқы сандардың кең ауқымын алудың ең тиімді жолы; алайда, жеке алғашқы сандарды табу үшін тікелей алғашқылықты тексерулер тиімдірек. Сонымен қатар, сүзгінің формальды негізінде кейбір бүтін сандар тізбектері құрастырылады, оларды белгілі бір интервалдарда алғашқы сандарды табу үшін де пайдалануға болады.
A prime sieve or prime number sieve is a fast type of algorithm for finding primes. There are many prime sieves. The simple sieve of Eratosthenes (250s BCE), the sieve of Sundaram (1934), the still faster but more complicated sieve of Atkin (2003), and various wheel sieves are most common. A prime sieve works by creating a list of all integers up to a desired limit and progressively removing composite numbers (which it directly generates) until only primes are left. This is the most efficient way to obtain a large range of primes; however, to find individual primes, direct primality tests are more efficient. Furthermore, based on the sieve formalisms, some integer sequences are constructed which also could be used for generating primes in certain intervals.
Үлкен жай сандар
Криптографияда қолданылатын үлкен жай сандар үшін, Поклингтонның жайлық сынағының түрлеріне негізделген дәлелді жай сандар жасалуы мүмкін, ал ықтимал жай сандар Бейли-PSW жайлық сынағы немесе Миллер-Рабин жайлық сынағы сияқты ықтималды жайлық сынақтарымен жасалуы мүмкін. Дәлелді және ықтимал жайлық сынақтарының екеуі де модульдік дәрежелеуге сүйенеді. Есептеу шығындарын одан да азайту үшін, бүтін сандар алдымен Эратоспенің елегіне ұқсас немесе қарапайым бөлу арқылы кез келген кіші жай бөлгіштерге тексеріледі. Мерсенн жай саны немесе Ферма жай саны сияқты ерекше формадағы бүтін сандар, егер p-1 немесе p+1 жай факторлануы белгілі болса, жайлыққа тиімді тестілеуге болады.
For the large primes used in cryptography, provable primes can be generated based on variants of Pocklington primality test, while probable primes can be generated with probabilistic primality tests such as the Baillie–PSW primality test or the Miller–Rabin primality test. Both the provable and probable primality tests rely on modular exponentiation. To further reduce the computational cost, the integers are first checked for any small prime divisors using either sieves similar to the sieve of Eratosthenes or trial division. Integers of special forms, such as Mersenne primes or Fermat primes, can be efficiently tested for primality if the prime factorization of p − 1 or p + 1 is known.
Күрделілігі
Эратостеннің сырғасы, әдетте, іске асыру үшін ең оңай сырға деп саналады, бірақ ол үлкен сырғалау диапазондары үшін берілген ауқымдағы операциялардың саны жағынан ең жылдам емес. Оның әдеттегі стандартты іске асырылуы (кішігірім жай сандар үшін негізгі дөңгелек факторлауды қамтуы мүмкін), ол барлық N-ге дейінгі жай сандарды уақыт ішінде таба алады, ал Аткиннің сырғасы мен дөңгелек сырғаларының негізгі іске асырылуы сызықтық уақытта жұмыс істейді. Аткиннің сырғасының арнайы нұсқасы және Эратостеннің сырғасынан алынған әдістерді пайдалана отырып сырғалауды қамтитын дөңгелек сырғаларының кейбір арнайы нұсқалары сызықтық уақыт күрделілігінде жұмыс істей алады. Алгоритмнің асимптотикалық уақыт күрделілігі төмендеуі оның практикалық іске асырылуы асимптотикалық уақыт күрделілігі жоғары алгоритмнен жылдам жұмыс істейтінін білдірмейді: Егер сол аз асимптотикалық күрделілікке қол жеткізу үшін жекелеген операциялардың уақыт күрделілігінің өсуінің тұрақты факторы бар болса, ол қарапайым алгоритмге қарағанда бірнеше есе үлкен болуы мүмкін, бұл операцияға қосымша уақытты өтеу үшін жеткілікті үлкен диапазондар үшін операциялардың қысқартылған санының артықшылығы үшін практикалық сырғалау диапазондарында ешқашан мүмкін болмауы мүмкін. Кейбір сырғалау алгоритмдері, мысалы үлкен мөлшерде дөңгелек факторлаумен Эратостеннің сырғасы, олардың асимптотикалық уақыт күрделілігі көрсететініне қарағанда кішігірім диапазондар үшін әлдеқайда аз уақыт алады, өйткені олардың күрделілігі үлкен теріс тұрақты ауытқуларға ие және осылайша практикалық диапазоннан тыс болғанша, бұл асимптотикалық күрделілікке жетпейді. Мысалы, Эратостеннің сырғасы дөңгелек факторлау мен 19 дейін кішігірім жай сандарды пайдалануды алдын ала таңдау комбинациясымен 1019-дың жалпы ауқымы үшін болжалданғаннан екі есе аз уақыт пайдаланады, бұл жалпы ауқымы ең жақсы сырғалау алгоритмі үшін жүздеген негізгі жылды қажет етеді. Осы сырға түрлерінің кез келгенінің қарапайым "бір үлкен сырғалау массиві" сырғалары шамамен жад кеңістігін алады, бұл дегеніміз 1) олар қол жетімді RAM (жад) мөлшеріне қарай өткізе алатын сырғалау диапазондарында өте шектеулі және 2) олар әдетте өте баяу, өйткені жадқа қол жеткізу жылдамдығы, әдетте, жылдамдықтың бөтелкелі шегіне айналады. Эратосфен мен Аткиннің әдетте іске асырылатын беттік сегментті сырғалары кеңістікті және әдетте CPU кэшінде орналасу үшін өлшенген шағын сырға сегмент буферлерін алады; Эратосфен сырғасының арнайы түрлерін қоса алғанда, беттік сегментті дөңгелек сырғалары, әдетте, қажетті дөңгелек бейнелерін сақтау үшін, осыдан әлдеқайда көп орын алады; Эратосфен / дөңгелек сырғасының сызықтық уақыт күрделілігі сырғасының Притчардтың өзгеруі кеңістікті алады. Аткиннің сырғанағының уақыт күрделілігі жақсы ерекше нұсқасы кеңістікті алады. Соренсон дөңгелек сырғанаққа қарағанда жақсаруды көрсетеді, ол кез-келген уақытқа қарағанда аз орын алады. Алайда, жалпы байқау мынау: жад мөлшері неғұрлым аз болса, операцияға арналған уақыт шығынындағы тұрақты фактордың өсуі соғұрлым жоғары болады, тіпті асимптотикалық уақыт күрделілігі бірдей қалуы мүмкін, яғни жадты азайтылған нұсқалар жадты азайтпаған нұсқаларға қарағанда бірнеше есе баяу жүруге болады.
The sieve of Eratosthenes is generally considered the easiest sieve to implement, but it is not the fastest in the sense of the number of operations for a given range for large sieving ranges. In its usual standard implementation (which may include basic wheel factorization for small primes), it can find all the primes up to N in time while basic implementations of the sieve of Atkin and wheel sieves run in linear time Special versions of the Sieve of Eratosthenes using wheel sieve principles can have this same linear time complexity. A special version of the Sieve of Atkin and some special versions of wheel sieves which may include sieving using the methods from the Sieve of Eratosthenes can run in sublinear time complexity of Note that just because an algorithm has decreased asymptotic time complexity does not mean that a practical implementation runs faster than an algorithm with a greater asymptotic time complexity: If in order to achieve that lesser asymptotic complexity the individual operations have a constant factor of increased time complexity that may be many times greater than for the simpler algorithm, it may never be possible within practical sieving ranges for the advantage of the reduced number of operations for reasonably large ranges to make up for this extra cost in time per operation. Some sieving algorithms, such as the Sieve of Eratosthenes with large amounts of wheel factorization, take much less time for smaller ranges than their asymptotic time complexity would indicate because they have large negative constant offsets in their complexity and thus don't reach that asymptotic complexity until far beyond practical ranges. For instance, the Sieve of Eratosthenes with a combination of wheel factorization and pre culling using small primes up to 19 uses time of about a factor of two less than that predicted for the total range for a range of 1019, which total range takes hundreds of core years to sieve for the best of sieve algorithms. The simple naive "one large sieving array" sieves of any of these sieve types take memory space of about , which means that 1) they are very limited in the sieving ranges they can handle to the amount of RAM (memory) available and 2) that they are typically quite slow since memory access speed typically becomes the speed bottleneck more than computational speed once the array size grows beyond the size of the CPU caches. The normally implemented page segmented sieves of both Eratosthenes and Atkin take space plus small sieve segment buffers which are normally sized to fit within the CPU cache; page segmented wheel sieves including special variations of the Sieve of Eratosthenes typically take much more space than this by a significant factor in order to store the required wheel representations; Pritchard's variation of the linear time complexity sieve of Eratosthenes/wheel sieve takes space. The better time complexity special version of the Sieve of Atkin takes space Sorenson shows an improvement to the wheel sieve that takes even less space at for any However, the following is a general observation: the more the amount of memory is reduced, the greater the constant factor increase in the cost in time per operation even though the asymptotic time complexity may remain the same, meaning that the memory reduced versions may run many times slower than the non memory reduced versions by quite a large factor.