प्राइमलिटी चेकर

प्राइमलिटी चेकर आपको बताता है कि पूर्णांक अभाज्य है या नहीं, और - अधिकांश ऑनलाइन कैलकुलेटर के विपरीत - आपको वास्तविक एल्गोरिदम दिखाता है जो इसे साबित करता है, कैश्ड लुकअप टेबल नहीं। कोई भी पूर्णांक टाइप करें, सकारात्मक या नकारात्मक, छोटा या बड़ा, और टूल यह तय करता है कि उसके आकार के आधार पर कौन सा वास्तविक एल्गोरिदम चलाना है।

10¹² (एक ट्रिलियन) से कम की संख्याओं के लिए, यह वास्तविक परीक्षण प्रभाग चलाता है: 2 से शुरू करके, यह प्रत्येक पूर्णांक उम्मीदवार को √n के तल तक एक संभावित भाजक के रूप में आज़माता है, एक समान रूप से विभाजित होने वाले क्षण को रोक देता है (मिश्रित) या पुष्टि करता है कि √n तक के प्रत्येक उम्मीदवार की जाँच (प्राइम) हो जाने के बाद भी कोई नहीं करता है। बड़ी संख्या में उम्मीदवारों के लिए दिखाए गए ट्रेस को पहले ~18 प्रयास और अंतिम एक तक सीमित कर दिया गया है, जिसमें एक ईमानदार नोट है कि प्रदर्शन में कितने छोड़ दिए गए थे - लेकिन हर एक उम्मीदवार को अभी भी कोड द्वारा जांचा जाता है, गणना में किसी को भी नहीं छोड़ा जाता है।

उस सीमा पर या उससे ऊपर की संख्याओं के लिए - क्रिप्टोग्राफी में उपयोग की जाने वाली आकार सीमा - परीक्षण विभाजन में बहुत लंबा समय लगेगा, इसलिए उपकरण 13 प्रमुख गवाहों (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41) के एक निश्चित, नियतात्मक सेट के साथ मिलर-राबिन प्रारंभिक परीक्षण पर स्विच करता है। यह सटीक गवाह सेट एक प्रसिद्ध परिणाम है: इसमें 3,317,044,064,679,887,385,961,981 (लगभग 3.3×10²⁴) से नीचे किसी भी n के लिए कोई गलत सकारात्मकता नहीं है, जो कम्प्यूटेशनल सत्यापन द्वारा स्थापित एक सीमा है (सोरेंसन और वेबस्टर, 2015 और व्यापक रूप से पुनरुत्पादित निर्धारक-साक्षी तालिका देखें)। उस सीमा से ऊपर वही परीक्षण अभी भी चलता है, लेकिन उपकरण आपको ईमानदारी से बताता है कि गारंटी गणितीय निश्चितता के बजाय एक अत्यंत मजबूत संभाव्य बन जाती है।

मिलर-राबिन ट्रेस n - 1 = 2ˢ × d को d विषम के साथ लिखता है, फिर वास्तविक BigInt मॉड्यूलर घातांक के माध्यम से चलता है - वर्ग-और-गुणा करता है, हर एक चरण में मॉड्यूलो n को कम करता है ताकि संख्या कभी विस्फोट न हो - पहले गवाह के लिए थोड़ा-थोड़ा करके, और प्रत्येक गवाह के फैसले की रिपोर्ट करता है, जिसमें यह भी शामिल है कि कौन सा गवाह समग्रता साबित करता है यदि संख्या अभाज्य नहीं है। आपके ब्राउज़र में सब कुछ स्थानीय रूप से चलता है: कोई सर्वर, कोई बाहरी एपीआई, कोई डेटा कभी भी आपके डिवाइस को नहीं छोड़ता है।