प्रारंभिकता जांच एल्गोरिदम

Question

प्राथमिकता जांच शायद गणित में "उन" कठिन समस्याओं में से एक है। तो, एक बड़ी संख्या की वास्तविकता की जांच के लिए सबसे अच्छा और सबसे तेज़ एल्गोरिदम क्या उपलब्ध है। सबसे कच्चे तेल और शायद सबसे धीमी तरीका है:

public static bool IsPrime(int i) 
{ 
    for (var x = 2; x < i - 1; i++) 
    { 
     if (i % x == 0) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

हाल ही में मैंने पढ़ा है कि 768-बिट RSA एल्गोरिदम जानवर बल का उपयोग कर टूट गया है, एक ग्रिड कंप्यूटिंग सरणी का उपयोग कर। वे एक विशाल प्रधान संख्या पर ब्रूट फोर्स कैसे करते हैं? क्या प्रत्येक प्रसंस्करण इकाई संख्या की एक श्रृंखला लेती है, इसे कारक करती है और उस सीमा में मौजूद सभी संख्याओं की प्राथमिकता की जांच करती है?

Answer 1

वर्तमान एल्गोरिदम

अपने अनुभवहीन कार्यान्वयन के संबंध में

, की ओर इशारा के लिए बाहर primality tests विकिपीडिया पर चेक ध्यान दें कि आप तुरंत झूठे लौट सकते हैं 2 से यदि संख्या विभाज्य है, तो आप सिर्फ अजीब जांच करने के लिए अनुमति देता है संख्या। इसके अतिरिक्त, यदि आपको कोई कारक नहीं मिला है जहां x < = sqrt (i), यह प्राइम है। ऐसा इसलिए है क्योंकि यदि आपको sqrt (i) से बड़ा कारक मिला, तो इसे sqrt (i) की तुलना में छोटे के साथ जोड़ा जाना चाहिए। तो अगर आपको पहले उस छोटे कारक को नहीं मिला है, तो आप कर चुके हैं।

वहाँ भी कुछ और चालें आप मदद :)

Answer 2

public static bool IsPrime(int i) 
{ 
    for (var x = 2; x < (i/2); x++) 
    { 
     if (i % x == 0) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

Answer 3

मुझे लगता है वहाँ काम का बोझ वितरण के कुछ प्रकार है के लिए https://mathoverflow.net/ के लिए रवाना मशगूल जाना है इससे पहले कि आप एक अनुभवहीन एल्गोरिथ्म के लिए आवेदन कर सकते हैं, लेकिन मुझे शक है कि वे इस तरह के प्रयोग किया जाता है प्रारंभिक परीक्षण के लिए एक सरल एल्गोरिदम। शायद उन्होंने number field sieve या Lenstra's elliptic curve factorization का उपयोग किया था।

Answer 4

यह काफ़ी तेजी से किया जाना चाहिए:

public static bool IsPrime(int i) {   
    // only go up to the root of i 
    // +1 to be save from floating point rounding errors, ceil should work too. 
    var max = sqrt(i) + 1; 

    // skip numbers dividable by 2, except 2 itself 
    if (i == 2) return true; 
    if (i % 2 == 0) return false; 
    for (var x = 3; x < max; x+=2) { 
     if (i % x == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

Answer 5

RSA-768 क्रैकिंग सीधे किसी भी primality जांच एल्गोरिथ्म शामिल नहीं थी, न कि जो जरूरत थी एक गुणन एल्गोरिथ्म था: RSA-768 के उत्पाद है दो बहुत बड़े प्राइम, और इसे क्रैक करने में इन प्राइम्स को ढूंढना शामिल है।

इस्तेमाल किए गए कारक एल्गोरिदम लेनस्ट्रा के Number Field Sieve था।

आप यहां पूरा लेख पढ़ सकते हैं: Factorization of a 768-bit RSA modulus।

Answer 6

प्रारंभिक परीक्षण! = कारककरण।

एक विशेष आरएसए सार्वजनिक कुंजी तोड़ना और निजी कुंजी को पुनर्प्राप्त करना, कारककरण की आवश्यकता है।

आरएसए सार्वजनिक/निजी कुंजी जोड़ी बनाने की प्रक्रिया में प्रारंभिक परीक्षण शामिल है। कारक बनाने के लिए उपयोग नहीं किए जाने वाले अधिकांश प्रारंभिक परीक्षण में 100% निश्चित उत्तर नहीं मिलता है, बल्कि यह probabilistic है जो मनमाने ढंग से उच्च संभावना (अधिक परीक्षण पुनरावृत्तियों = उच्च संभावना) के साथ होता है।

और तकनीकी रूप से आपके पास deterministic primality test हो सकता है जो तेज़ है और इसमें वास्तव में प्रश्न के किसी भी कारक की गणना करने में शामिल नहीं है।

Answer 7

मैं Fermat's Little Theorem का उपयोग करने का सुझाव देता हूं। 'एक्स' का मूल्य प्रधानमंत्री अगर ((एक^(एक्स 1))% x) == 1 है।कहाँ 'एक' किसी भी संख्या और है 'एक्स' 1, 0 या 2 के बराबर नहीं।