पोलार्ड-रो फैक्टोरिज़ेशन समांतरता

Question

मैंने हाल ही में के समांतरता पर a paper पर ठोकर खाई, और इस तथ्य के अलावा कि मैंने गणित के आवश्यक स्तर को प्राप्त नहीं किया है, मुझे आश्चर्य है कि यह विशेष समानांतरता है या नहीं विधि मेरे विशिष्ट मामले में मदद करता है।

मैं एक बहुत बड़ी संख्या के दो कारकों-सेमिप्रिम्स खोजने की कोशिश कर रहा हूं। मेरी धारणा, कागज के बारे में मुझे समझने के आधार पर, यह है कि यह समानांतर दो बहुत बड़े कारकों के बजाए बहुत से छोटे कारकों के साथ एक संख्या पर अच्छी तरह से काम करता है।

क्या यह सच है? क्या मुझे इस समांतरता का उपयोग करना चाहिए या कुछ और उपयोग करना चाहिए? क्या मुझे पोलार्ड के Rho का भी उपयोग करना चाहिए, या क्या एक अलग कारककरण एल्गोरिदम का बेहतर समांतरता है?

Answer 1

बड़े पूर्णांक फैक्टरिंग में मूल विचार विभिन्न तरीकों का उपयोग करना है, प्रत्येक के अपने प्लस और माइनस के साथ। सामान्य योजना 1000 से 10000 तक प्राइम द्वारा ट्रायल डिवीजन से शुरू करना है, इसके बाद कुछ मिलियन पोलार्ड रोड कदम हैं; जो आपको बारह अंकों तक कारक प्राप्त करना चाहिए। उस बिंदु पर कुछ परीक्षण क्रम में हैं: क्या संख्या एक प्रमुख शक्ति या एक परिपूर्ण शक्ति है (उन गुणों के लिए सरल परीक्षण हैं)। यदि आपने अभी भी संख्या को नहीं देखा है, तो आप जानते हैं कि यह कठिन होगा, इसलिए आपको भारी शुल्क वाले टूल की आवश्यकता होगी। एक उपयोगी अगला कदम पोलार्ड की पी -1 विधि है, इसके बाद उसके करीबी चचेरे भाई अंडाकार वक्र विधि के बाद। थोड़ी देर बाद, यदि यह काम नहीं करता है, तो केवल एक ही विधि छोड़कर चतुर्भुज चलनी या संख्या क्षेत्र चलनी है, जो मूल रूप से समानांतर हैं।

आपके द्वारा पूछे जाने वाले समांतर rho विधि का व्यापक रूप से उपयोग नहीं किया जाता है। जैसा कि आपने सुझाव दिया था, पोलार्ड rho बड़े लोगों की बजाय छोटे कारकों को खोजने के लिए बेहतर अनुकूल है। अर्ध-प्रधान के लिए, पोलार्ड रोडो की तुलना में एक चोरों पर समानांतर चक्र खर्च करना बेहतर होता है।

मैं अधिक जानकारी के लिए mersenneforum.org पर फ़ैक्टरिंग फ़ोरम की अनुशंसा करता हूं।

Answer 2

विकिपीडिया लेख में कहा गया दो ठोस उदाहरण:

सभी की

Number    Original code  Brent's modification 
18446744073709551617 26 ms    5 ms 
10023859281455311421 109 ms    31 ms 

पहले, अपने कार्यक्रम के साथ इन दोनों चलाने के लिए और अपने समय पर एक नज़र डालें। यदि वे इस तरह के हैं ("हार्ड" संख्या 4-6 गुना अधिक गणना करते हैं), तो खुद से पूछें कि क्या आप इसके साथ रह सकते हैं। या इससे भी बेहतर, सरल क्लासिक "ब्रूट फोर्स" कारककरण जैसे अन्य एल्गोरिदम का उपयोग करें और वे जो समय देते हैं उन्हें देखें। मुझे लगता है कि उनके पास 1 के करीब एक कठिन कारक हो सकता है, लेकिन पूर्णकालिक समय, इसलिए यह एक साधारण व्यापार-बंद है।

साइड नोट: बेशक, समांतरता यहां जाने का तरीका है, मुझे लगता है कि आप जानते हैं लेकिन मुझे लगता है कि जोर देना महत्वपूर्ण है। इसके अलावा, यह इस मामले में मदद करेगा कि पोलार्ड-रोड समय (जैसे पोलार्ड-रो 5-31 एमएस, अलग दृष्टिकोण 15-17 एमएस) के बीच एक और दृष्टिकोण है, इस मामले में, पृथक धागे में 2 एल्गोरिदम चलाने पर विचार करें एक "कारक बनाने की दौड़" करने के लिए।

यदि आपके पास अभी तक एल्गोरिदम का वास्तविक कार्यान्वयन नहीं है, तो यहां Python implementations हैं।