प्राइम नंबर खोज एल्गोरिदम

“सबसे बड़ी अभाज्य संख्या 2 ^32582657 -1 है । और मैं दावा है कि वह सभी नंबरों को याद ... बाइनरी रूप में करने के लिए गर्व कर रहा हूँ। "
कार्ल पोमरेन्स

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

एरेटोस्थेनेज की चलनी

एराटोस्थनीज की छलनी - प्राचीन ग्रीक गणितज्ञ एराटोस्थनीज द्वारा प्रस्तावित एक एल्गोरिथ्म। यह विधि आपको दिए गए नंबर n से कम सभी primes खोजने की अनुमति देती है। विधि का सार इस प्रकार है। 2 से n करने के लिए संख्या का एक सेट पर विचार करें। हम सेट (otseit) से हटाने के सभी नंबरों 2. छोड़कर, 2 से विभाज्य अगले "कोई घास" संख्या के लिए आगे बढ़ें -, 3 फिर से पता लगा कि सभी से 3. अगली शेष संख्या पर जाएं विभाज्य है - 5, और इतने पर हम जब तक हम एन । उपरोक्त चरणों को करने के बाद, मूल सूची में केवल प्रमुख संख्याएँ ही रहेंगी।

एल्गोरिथ्म को थोड़ा अनुकूलित किया जा सकता है। समग्र की संख्या n के divisors में से एक के बाद से की आवश्यकता होती है $$$\ leqllant \ sqrt {n}$ , एल्गोरिथ्म, बंद कर सकते हैं बाहर हड़ताली के बाद संख्या से विभाज्य $$$\ sqrt {n}$ ।

विकिपीडिया से एल्गोरिथ्म के संचालन का चित्रण:


एल्गोरिथ्म की जटिलता है $$$O (n \ log \ log n)$ उसी समय, यह जानकारी संग्रहीत करने के लिए कि कौन से नंबर को पार किया गया था, इसकी आवश्यकता है $$$O (n)$ स्मृति।

इन संकेतकों को कम करने के लिए कई अनुकूलन हैं। प्राप्त करना कहा जाता पहिया गुणन स्रोत सूची ही नंबर शामिल करने के लिए है पारस्परिक रूप से प्रधानमंत्री पहले प्रधानमंत्री संख्या की अधिकता (जैसे कम से कम 30) के साथ। सिद्धांत रूप में, इसके बारे में पहले सरल लोगों को लेने का प्रस्ताव है $$$\ sqrt {\ log n}$ । यह एल्गोरिथ्म की जटिलता को कम करता है $$$\ log \ log n$ समय। इसके अलावा, तथाकथित विभाजन का उपयोग मेमोरी की खपत को कम करने के लिए किया जाता है। नंबरों की प्रारंभिक सेट आकार के क्षेत्रों में बांटा गया है $$$\ leqllant \ sqrt {n}$ और प्रत्येक खंड के लिए, इरेटोस्थनीज की छलनी अलग से लागू की जाती है। मेमोरी की खपत कम हो जाती है $$$O (\ sqrt {n})$ ।

एटकिन चलनी

समग्र संख्या को बाहर निकालने के लिए एक बेहतर एल्गोरिथ्म Atkin और Bershtein द्वारा प्रस्तावित किया गया था और इसे Atkin चलनी कहा जाता था। यह विधि निम्नलिखित तीन गुणों के गुणों पर आधारित है।

संपत्ति १

यदि n एक धनात्मक संख्या है, जो अभाज्य संख्या के वर्ग का बहु नहीं है और ऐसा है $$$n \ equiv 1 (\ mod 4)$ । तब n अभाज्य है यदि और केवल यदि समीकरण की जड़ों की संख्या $$$4x ^ 2 + y ^ 2 = n$ अजीब।

संपत्ति २

यदि n एक धनात्मक संख्या है, जो अभाज्य संख्या के वर्ग का बहु नहीं है और ऐसा है $$$n \ equiv 1 (\ mod 6)$ । तब n अभाज्य है यदि और केवल यदि समीकरण की जड़ों की संख्या $$$3x ^ 2 + y ^ 2 = n$ अजीब।

संपत्ति ३

यदि n एक धनात्मक संख्या है, जो अभाज्य संख्या के वर्ग का बहु नहीं है और ऐसा है $$$n \ equiv 11 (\ mod 12)$ । तब n अभाज्य है यदि और केवल यदि समीकरण की जड़ों की संख्या $$$3x ^ 2-y ^ 2 = n$ अजीब।

इन गुणों के साक्ष्य इस लेख में दिए गए हैं ।

एल्गोरिथ्म के प्रारंभिक चरण में, एटकिन चलनी एक सरणी है जो शून्य से भरा आकार एन है । अभाज्य संख्या निर्धारित करने के लिए, सभी $$$x, y <\ sqrt n$ । प्रत्येक के लिए ऐसी जोड़ी की गणना की जाती है $$$4x ^ 2 + y ^ 2$ । $$$3x ^ 2 + y ^ 2$ । $$$3x ^ 2-y ^ 2$ और सरणी के तत्वों का मूल्य $$$A [4x ^ 2 + y ^ 2]$ । $$$A [3x ^ 2 + y ^ 2]$ । $$$एक [3x ^ 2-y ^ 2]$ एक से बढ़ जाता है। एल्गोरिथ्म के अंत में, सरणी के सभी तत्वों के ऑड्स जिनके विषम मान हैं, वे या तो अभाज्य संख्याएँ हैं या अभाज्य संख्याओं के वर्ग हैं। एल्गोरिथ्म के अंतिम चरण में, सेट में शेष संख्याओं के वर्गों को पार किया जाता है।

यह एल्गोरिथ्म के वर्णन से निम्नानुसार है कि एटकिन चलनी और मेमोरी खपत की कम्प्यूटेशनल जटिलता है $$$हे (एन)$ । पहिया कारक और विभाजन का उपयोग करते समय, एल्गोरिथ्म की जटिलता का अनुमान कम हो जाता है $$$O (n / \ log \ log n)$ , और मेमोरी खपत तक $$$O (\ sqrt {n})$ ।

Mersenne संख्या और ल्यूक- Lemer परीक्षण

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

ऐसा ही एक परीक्षण तरीका है ल्यूक-लेमर परीक्षण । यह परीक्षण के नियतात्मक और पूर्ण सादगी है। इसका मतलब है कि परीक्षण के पारित होने के लिए आसान संख्या सुनिश्चित करता है। दुर्भाग्य से, परीक्षण केवल एक विशेष प्रकार की संख्या के लिए करना है $$$2 ^ पी 1$ जहाँ p एक प्राकृतिक संख्या है। इस तरह की संख्याओं को मेरसेन नंबर कहा जाता है।

ल्यूक-लेमर परीक्षण का दावा है कि मेरसेन संख्या $$$M_p = 2 ^ p-1$ अगर प्राइम और केवल अगर पी प्राइम और $$$M_p$ समान रूप से विभाजित $$$(पी -1)$ अनुक्रम का सदस्य $$$S_k$ रिकर्सिवली परिभाषित: $$$S_1 = 4, S_k = S_ {k-1} ^ 2-2$ के लिए $$$k> 1$ ।

संख्या के लिए $$$M_p$ p की लंबाई एल्गोरिथ्म की कम्प्यूटेशनल जटिलता है $$${\ displaystyle O (p ^ {3})}$ ।

परीक्षण की सादगी और नियतत्ववाद के कारण, सबसे बड़े ज्ञात अपराध मेर्सेन संख्या हैं। आज की सबसे बड़ी ज्ञात अभाज्य संख्या है $$$2 ^ {82,589,933} -1$ इसके दशमलव संकेतन 24,862,048 अंक होते हैं। आप यहाँ इस सुंदरता की प्रशंसा कर सकते हैं।

फर्मेट का प्रमेय और मिलर-राबिन परीक्षण

बहुत से मेर्सेन प्राइम्स ज्ञात नहीं हैं, इसलिए सार्वजनिक कुंजी क्रिप्टोग्राफी को प्रिम्स की खोज के लिए एक अलग तरीके की आवश्यकता होती है। ऐसी ही एक विधि है फ़र्मेट सादगी परीक्षण । यह फर्मेट के थोड़ा प्रमेय, जिसमें कहा गया है पर आधारित है कि यदि एक n - अभाज्य संख्या है, तो किसी भी एक के लिए है, जो एन से विभाज्य नहीं है, समानता $$$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ । प्रमेय का प्रमाण विकिपीडिया पर पाया जा सकता है।

Fermat की सादगी परीक्षण एक संभाव्य परीक्षण है, जिसमें यदि उनमें से कम से कम एक असमानता को संतुष्ट करता है, तो कई मूल्यों की गणना करना शामिल है $$$a ^ {n-1} \ not \ equiv 1 \ pmod n$ , पूर्णांक n - समग्र। अन्यथा, n शायद प्रमुख है। परीक्षण में उपयोग किए गए अधिक मूल्य, उच्च संभावना है कि n प्रमुख है।

दुर्भाग्यवश, तुलना करने के लिए मिश्रित संख्या n हैं $$$a ^ {n-1} \ equiv 1 {\ pmod {n}}$ n के साथ सभी परस्पर प्रधानता रखता है। ऐसे नंबरों को कारमाइकल नंबर कहा जाता है। यौगिक संख्या जो सफलतापूर्वक फ़र्मेट टेस्ट पास करती हैं उन्हें छद्म-सरल फ़र्मेट कहा जाता है। छद्म-सरल फ़र्मेट की संख्या अनंत है, इसलिए प्राइम संख्या निर्धारित करने के लिए फ़र्मेट टेस्ट सबसे विश्वसनीय तरीका नहीं है।

मिलर-राबिन टेस्ट

फ़र्मेट की छोटी प्रमेय और इस तथ्य को मिलाकर अधिक विश्वसनीय परिणाम प्राप्त किए जा सकते हैं कि प्राइम पी के लिए समीकरण की कोई अन्य जड़ें नहीं हैं। $$$x ^ 2 \ equiv 1 \ pmod p$ 1 और -1 को छोड़कर। मिलर-राबिन परीक्षण एक के कई मूल्यों को जांचता है और जांचता है कि निम्नलिखित स्थितियां सत्य हैं।

पी को प्रधान होने दें और $$$p-1 = 2 ^ sd$ , फिर किसी भी स्थिति के लिए कम से कम एक सच है:

1. $$$a ^ {d} \ equiv pm pm {{pmod {p}}$
2. एक पूर्णांक r <s ऐसा है $$$a ^ {2 ^ {r} d} \ equiv -1 {\ pmod {p}}$

Fermat की प्रमेय द्वारा $$$a ^ {p-1} \ equiv1 \ pmod p$ और कब से $$$p-1 = 2 ^ sd$ समीकरण की जड़ों की संपत्ति से $$$x ^ 2 \ equiv 1 \ pmod p$ यह इस प्रकार है कि यदि हम ऐसा पाते हैं कि कोई एक स्थिति संतुष्ट नहीं है, तो p एक संयुक्त संख्या है। यदि शर्तों में से एक को पूरा किया जाता है, तो संख्या को मिलर के अनुसार संख्या n की सादगी का गवाह कहा जाता है, और संख्या n स्वयं संभवतः प्रमुख है।

सादगी के जितने अधिक साक्षी पाए जाते हैं, उतनी ही अधिक संभावना है कि n अभाज्य है। प्रमेय राबिन संभावना के अनुसार कि यादृच्छिक रूप से चयनित संख्या इच्छा गवाह सादगी समग्र संख्या लगभग है $$$1/4$ ।

इसलिए, यदि हम k यादृच्छिक संख्याओं की जांच करते हैं , तो संयुक्त संख्या को प्रधान के रूप में लेने की संभावना $$$\ लगभग (1/4) ^ k$ ।

एल्गोरिथ्म की जटिलता $$$हे (k \ लॉग ^ 3p)$ जहां k चेक की संख्या है।

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

वह ऐसे कंपोजिट नंबर जेनरेट करने में सक्षम था, जो लाइब्रेरी ओपनएसएसएल, क्रिप्टलिब, जावास्क्रिप्ट बिग नंबर और कई अन्य में सादगी परीक्षण को सफलतापूर्वक पार कर गया।

ल्यूक टेस्ट और बैली - पीएसडब्ल्यू टेस्ट

परिस्थितियों से संबंधित कमजोरियों से बचने के लिए जब एक हमलावर द्वारा उत्पन्न एक समग्र संख्या को एक प्रमुख के रूप में प्रस्तुत किया जाता है, मार्टिन अल्ब्रेक्ट बैली - पीएसडब्ल्यू परीक्षण का उपयोग करने का सुझाव देता है। इस तथ्य के बावजूद कि बैली - पीएसडब्ल्यू परीक्षण संभावित है, आज तक, कोई यौगिक संख्या नहीं मिली है जो इस परीक्षण को सफलतापूर्वक पास करती है। 1980 में ऐसी संख्या खोजने के लिए, एल्गोरिथ्म के लेखकों ने $ 30 के इनाम का वादा किया था। अभी तक पुरस्कार का दावा नहीं किया गया है।

कई शोधकर्ताओं ने सभी नंबरों की जाँच की $$$2 ^ {64}$ और हम किसी भी संयुक्त संख्या, अंतिम परीक्षण बैली-PSW नहीं मिला। इसलिए, संख्याओं के लिए कम $$$2 ^ {64}$ परीक्षण को नियतात्मक माना जाता है।

परीक्षण का सार लगातार दो अलग-अलग तरीकों से डाउनटाइम पर संख्या की जांच करना है। इनमें से एक विधि मिलर-राबिन परीक्षण है जो पहले से ही ऊपर वर्णित है। दूसरा मजबूत छद्म सादगी के लिए ल्यूक का परीक्षण है ।

ल्यूक स्ट्रॉन्ग स्यूडो-सिंपलिसिटी टेस्ट

ल्यूक अनुक्रम पुनरावृत्ति अनुक्रमों के जोड़े हैं $$$\ {U_ {n} (पी, क्यू) \}, \ {V_ {n} (पी, क्यू) \}$ भावों द्वारा वर्णित:

$$

$${\ displaystyle U_ {0} (P, Q) = 0, \ quad U_ {1} (P, Q) = 1, \ quad U_ {n + 2} (P, Q) = P \ cdot U_ / n +1} (P, Q) -Q \ cdot U_ {n} (P, Q), \, n \ geq 0}$$

$$

$${\ displaystyle V_ {0} (P, Q) = 2, \ quad V_ {1} (P, Q) = P, \ quad V_ {n + 2} (P, Q) = P \ cdot V_ / n +1} (P, Q) -Q \ cdot V_ {n} (P, Q), \, n \ geq 0}$$

चलो $$$U_n (P, Q)$ और $$$V_n (पी, क्यू)$ क्या लुकास अनुक्रम हैं, जहां पूर्णांक पी और क्यू स्थिति को संतुष्ट करते हैं $$${\ displaystyle D = P ^ {2} -4Q \ neq 0}$

हम जैकोबी प्रतीक की गणना करते हैं : $$$\ _ ({\ _ frac {D} {p}} \ right) = \ varepsilon$ ।

ऐसे r खोजें , जिसके लिए समानता हो $$$n-n = 2 ^ rs$

प्राइम एन के लिए , निम्नलिखित में से एक स्थिति रखती है:

1. n बांटता है $$$U_s$
2. n बांटता है $$$V_ {2 ^ js}$ कुछ j <r के लिए

अन्यथा, n यौगिक है।

संभावना है कि एक मिश्रित संख्या n सफलतापूर्वक पैरामीटर पी की एक जोड़ी के लिए ल्यूक परीक्षण पास करेगा, क्यू 4/15 से अधिक नहीं है। इसलिए, परीक्षण के समय को लागू करने के बाद, यह संभावना है $$$(4/15) ^ k$ ।

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

निष्कर्ष

कार्य के आधार पर, अभाज्य संख्याओं को खोजने के विभिन्न तरीकों का उपयोग किया जा सकता है। उदाहरण के लिए, जब बड़े मेर्सेन प्राइम की खोज करते हैं, तो सबसे पहले, एराटोस्थनीज़ या एटकिन की छलनी का उपयोग करते हुए, प्रिम्स की एक सूची एक निश्चित सीमा तक निर्धारित होती है, मान लीजिए $$$10 ^ 8$ । फिर, सूची से प्रत्येक नंबर पी के लिए, ल्यूक-लेमर परीक्षण का उपयोग करके, इसे सरलता के लिए जांचा जाता है $$$M_p = 2 ^ p-1$ ।

क्रिप्टोग्राफ़िक उद्देश्यों के लिए एक बड़ी प्राइम संख्या उत्पन्न करने के लिए, एक यादृच्छिक संख्या एक चयनित और मिलर-राबिन परीक्षण या अधिक विश्वसनीय बैली - पीएसडब्ल्यू द्वारा सत्यापित है। प्राइम संख्या वितरण प्रमेय के अनुसार , 1 से n तक यादृच्छिक रूप से चयनित संख्या के लिए , प्राइम होने की संभावना लगभग बराबर है $$${\ frac {1} {\ ln n}}$ । इसलिए, 1024 बिट्स की एक प्रमुख संख्या का पता लगाने के लिए, यह लगभग एक हजार विकल्पों को हल करने के लिए पर्याप्त है।

पुनश्च स्रोत

गो पर सभी वर्णित एल्गोरिदम का कार्यान्वयन गिटहब पर देखा जा सकता है ।