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

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

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 से घटाते हुए ताकि संख्याएँ कभी विस्फोट न करें — बिट दर बिट दिखाता है, और प्रत्येक साक्षी के निर्णय की रिपोर्ट करता है, जिसमें यह भी शामिल है कि यदि संख्या अभाज्य नहीं निकलती है तो कौन सा साक्षी संयुक्तता सिद्ध करता है। सब कुछ स्थानीय रूप से आपके ब्राउज़र में चलता है: कोई सर्वर नहीं, कोई बाहरी API नहीं, कोई डेटा कभी भी आपके उपकरण को नहीं छोड़ता।