निर्धारित रूप से जांचना कि बड़ी संख्या प्रमुख या समग्र है या नहीं?

Question

मैं प्राथमिकता परीक्षण के लिए एक एल्गोरिदम खोज रहा हूं (जैसे 10) संख्याएं। क्या कोई अच्छा एल्गोरिदम है?

आदर्श रूप में, मैं एक एल्गोरिदम पसंद करूंगा जो संभाव्य नहीं है।

नोट: संख्याएं 50 से अधिक और 200 अंकों से कम हैं।

Answer 1

यदि आप एक गैर-संभाव्य परीक्षण की तलाश में हैं, तो आप AKS primality testing algorithm को देखना चाहेंगे, जो लगभग ओ (लॉग n) समय में चलता है। आपके पास अंकों की संख्या के लिए, यह संभवतः संभव है।

ने कहा, संभाव्यता प्रारंभिक परीक्षण बेहद अच्छे हैं और कई में तेजी से छोटी त्रुटि दर है। मैं उन लोगों में से एक का उपयोग करने का सुझाव दूंगा जब तक कि कोई अच्छा कारण न हो।

EDIT: मुझे अभी this page containing several C++ implementations of AKS मिला है। मुझे नहीं पता कि वे सही तरीके से काम करते हैं या नहीं, लेकिन वे एक अच्छा प्रारंभिक बिंदु हो सकते हैं।

आशा है कि इससे मदद मिलती है!

Answer 2

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

मान लीजिए कि आप पर्याप्त नहीं हैं। फिर आप वास्तव में ECPP का उपयोग करना चाहते हैं और प्रमाणपत्र प्राप्त करना चाहते हैं। उचित कार्यान्वयन Primo या ecpp-dj हैं। ये एक दूसरे के तहत अच्छी तरह से 200 अंकों की संख्या की वास्तविकता साबित कर सकते हैं, और एक प्रमाण पत्र वापस कर सकते हैं जिसे स्वतंत्र रूप से सत्यापित किया जा सकता है।

APR-CL एक और उचित विधि है। नकारात्मकता यह है कि यह प्रमाण पत्र वापस नहीं करता है, इसलिए आप कार्यान्वयन पर भरोसा कर रहे हैं - आपको "हां" या "नहीं" आउटपुट मिलता है जो कार्यान्वयन सही होने पर निश्चित रूप से सही होता है। पार/जीपी अपने isprime कमांड के साथ एपीआर-सीएल का उपयोग करता है, और डेविड क्लीवर का उत्कृष्ट ओपन सोर्स कार्यान्वयन है: mpz_aprcl। उन कार्यान्वयनों में विभिन्न सॉफ़्टवेयर में कुछ कोड समीक्षा और दैनिक उपयोग किया गया है, इसलिए यह अच्छा होना चाहिए।

AKS अभ्यास में उपयोग करने के लिए एक भयानक विधि है। यह प्रमाण पत्र नहीं लौटाता है, और टूटा कार्यान्वयन खोजने में बहुत मुश्किल नहीं है, जो पूरी तरह से पहली जगह में एक सबूत विधि बनाम अच्छे संभावित प्राइम परीक्षण का उपयोग करने के बिंदु को हरा देता है। यह भी बहुत धीमी गति से धीमा है। 200 अंकों की संख्या किसी भी कार्यान्वयन के लिए व्यावहारिक बिंदु से पहले अच्छी तरह से हैं जो मुझे पता है। पहले उल्लिखित ecpp-dj सॉफ़्टवेयर में एक "तेज़" शामिल है, ताकि आप इसे आजमा सकें, और कुछ अन्य कार्यान्वयन पाए जा सकते हैं।

गति के कुछ विचारों के लिए, यहां कुछ कार्यान्वयन के समय हैं। मुझे एकेएस, एपीआर-सीएल, या बीपीएसडब्ल्यू के किसी भी कार्यान्वयन के बारे में पता नहीं है जो दिखाए गए लोगों की तुलना में तेज़ हैं (यदि आप एक के बारे में जानते हैं तो कृपया टिप्पणी करें)। Primo ecpp-dj दिखाए गए थोड़ा धीमे से शुरू होता है, लेकिन 500 या तो अंकों पर यह तेज़ है, और उसके पीछे एक बेहतर ढलान है। यह बड़े इनपुट (2,000-30,000 अंक) के लिए पसंद का कार्यक्रम है।