Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математика мен компьютерлік ғылымда, біріншілік сертификаты немесе біріншілік дәлелі – бұл санның бірінші екенін қысқаша, формалды түрде дәлелдеу. Біріншілік сертификаттары қымбат немесе сенімсіз біріншілік тестін жүргізудің қажеті болмай, санның біріншілігін жылдам тексеруге мүмкіндік береді. "Қысқаша" әдетте дәлелдің ұзындығы санның өзіндегі цифрлар санынан полиномдық дәрежеде ғана артық болуы керек дегенді білдіреді (мысалы, егер санда b бит болса, дәлел шамамен b2 биттен тұруы мүмкін). Біріншілік сертификаттары біріншілікті тексеру және бүтін сандарды жіктеудің қосымша мәселелері сияқты мәселелердің NP класында екенін, яғни шешімі белгілі болғанда полиномдық уақытта тексерілетін мәселелер класында екенін тікелей дәлелдейді. Бұл мәселелердің барлығы қазірдің өзінде co NP класында жатыр. Бұл осы мәселелердің NP-толық еместігінің алғашқы мықты дәлелі болды, себебі егер олар NP-толық болса, онда NP co NP-нің ішкі жиыны екенін білдіретін болар еді, бұл нәтиже кеңінен жалған деп есептеледі; шындығында, бұл NP ∩ co NP қиылысындағы мәселенің алғашқы көрсетілімі болды, оның P класында екені сол кезде белгісіз болды.
In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test. "Succinct" usually means that the proof should be at most polynomially larger than the number of digits in the number itself (for example, if the number has b bits, the proof might contain roughly b2 bits). Primality certificates lead directly to proofs that problems such as primality testing and the complement of integer factorization lie in NP, the class of problems verifiable in polynomial time given a solution. These problems already trivially lie in co NP. This was the first strong evidence that these problems are not NP complete, since if they were, it would imply that NP is subset of co NP, a result widely believed to be false; in fact, this was the first demonstration of a problem in NP intersect co NP not known, at the time, to be in P.
Қосымша мәселе үшін сертификаттарды жасау, яғни санның құрама екенін анықтау оңай: тривиалды емес бөлгіш көрсету жеткілікті. Baillie–PSW, Ферма және Миллер–Рабин сияқты стандартты ықтималдық тестері де кіріс құрама болған жағдайда құрамалық сертификаттарды шығарады, бірақ бірінші кіріс үшін сертификаттарды шығара алмайды.
Producing certificates for the complement problem, to establish that a number is composite, is straightforward: it suffices to give a nontrivial divisor. Standard probabilistic primality tests such as the Baillie–PSW primality test, the Fermat primality test, and the Miller–Rabin primality test also produce compositeness certificates in the event where the input is composite, but do not produce certificates for prime inputs.
Поклингтондық сертификаттар
Поклингтон теоремасының варианттарына негізделген дәлелді премьер сандарды жасау (Поклингтонның премьерлік тестісін қараңыз) премьер сандарды жасаудың тиімді әдістері болуы мүмкін (құны көбінесе ықтималды жасаудан төмен), сонымен қатар премьерлік сертификаттары да бірге келеді. Бұл премьер сандар ерекше болып көрінсе де, кез келген премьер бүтін санды Поклингтонға негізделген дәлелді жасау алгоритмімен жасауға болады.
Provable prime generation based on variants of Pocklington's theorem (see Pocklington primality test) can be efficient techniques for generating primes (cost is generally less than probabilistic generation) with the added benefit of built in primality certificates. While these may seem to be special primes, notice that every prime integer could be generated with a Pocklington based provable generation algorithm.
"PRIMES P-де" әсері
"PRIMES P-де" – теориялық компьютерлік ғылымдағы маңызды жаңалық. Маниндра Агравал, Нитин Саксена және Нирадж Кайал 2002 жылдың тамызында жариялаған бұл мақала, бір санның жай сан екенін тексерудегі белгілі мәселені полиномиалдық уақытта детерминистік түрде шешуге болатынын дәлелдейді. Авторлар осы еңбегі үшін 2006 жылғы Гедель сыйлығымен және 2006 жылғы Фулкерсон сыйлығымен марапатталды. Қазір AKS жай сан тестісін қолдану арқылы жай сан тестілеуін полиномиалдық уақытта детерминистік түрде жүргізуге болатындықтан, жай санның өзі оның жай екенін растайтын сертификат ретінде қарастырылуы мүмкін. Бұл тест Õ((log n)6) уақытында жұмыс істейді. Іс жүзінде, бұл тексеру әдісі Пратт сертификаттарын тексеруден қымбатқа түседі, бірақ сертификатты анықтау үшін қосымша есептеулердің қажеті жоқ.
"PRIMES is in P" was a breakthrough in theoretical computer science. This article, published by Manindra Agrawal, Nitin Saxena, and Neeraj Kayal in August 2002, proves that the famous problem of checking primality of a number can be solved deterministically in polynomial time. The authors received the 2006 Gödel Prize and 2006 Fulkerson Prize for this work. Because primality testing can now be done deterministically in polynomial time using the AKS primality test, a prime number could itself be considered a certificate of its own primality. This test runs in Õ((log n)6) time. In practice this method of verification is more expensive than the verification of Pratt certificates, but does not require any computation to determine the certificate itself.