កម្មវិធីពិនិត្យចំនួនបឋម

ប្រវត្តិនៃចំនួនបឋម

ចំនួនបឋមគឺជាសំណង់គ្រឹះនៃចំនួនគត់—អាចចែកបានតែនឹង 1 និងខ្លួនវាផ្ទាល់។ អ៊ុយក្លីត បានបង្ហាញភស្តុតាងជាង 2000 ឆ្នាំមុនថា ចំនួនបឋមមានចំនួនច្រើនឥតកំណត់។ គ្រីបតូក្រាហ្វីទំនើប (RSA, Diffie-Hellman, ECC ប្រភេទផ្សេងៗ) ពឹងផ្អែកលើលក្ខណៈរបស់ចំនួនបឋមសម្រាប់សុវត្ថិភាព។

ចំណេះដឹងគួរឲ្យចាប់អារម្មណ៍៖ ទ្រឹស្តីបទចំនួនបឋមបង្ហាញថា ចំនួនបឋមកាន់តែស្តើងឡើងប្រហែលតាម n / ln(n)។ ចំនួនបឋម Mersenne (2^p − 1 ដែល p ជាចំនួនបឋម) គឺកម្រណាស់ ហើយជំរុញគម្រោងដូចជា GIMPS ឲ្យស្វែងរកពួកវា។ ការធ្វើតេស្តភាពបឋមឥឡូវនេះលឿន (ឧ. Miller–Rabin, AKS) ធ្វើឲ្យ “តើនេះជាចំនួនបឋមឬ?” ទទួលចម្លើយស្ទើរតែភ្លាមៗ សូម្បីតែសម្រាប់លេខធំៗ។