द्विघात छलनी

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

मूल उद्देश्य

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

वर्गों की सर्वांगसमता ज्ञात करने का सरल तरीका यह है कि एक यादृच्छिक संख्या चुनें, उसका वर्ग करें, n से भाग दें और आशा करें कि सबसे कम गैर-नकारात्मक शेष एक वर्ग संख्या हो। उदाहरण के लिए, $80^{2}\equiv 441=21^{2}{\pmod {5959}}$. यह दृष्टिकोण बड़े n के लिए शायद ही कभी वर्गों की सर्वांगसमता पाता है, लेकिन जब यह एक पाता है, तो अधिकतर, सर्वांगसमता गैर-तुच्छ होती है और गुणनखंडन पूरा हो जाता है। यह मोटे तौर पर फ़र्मेट की गुणनखंडन विधि का आधार है।

द्विघात छलनी डिक्सन की गुणनखंडन विधि का एक संशोधन है।

द्विघात छलनी (एक पूर्णांक n का गुणनखंड करने के लिए) के लिए आवश्यक सामान्य चलने का समय है

$e^{(1+o(1)){\sqrt {\ln n\ln \ln n}}}=L_{n}\left[1/2,1\right]$

एल-नोटेशन में. स्थिरांक e प्राकृतिक लघुगणक का आधार है।

दृष्टिकोण

पूर्णांक n को गुणनखंडित करने के लिए, फ़र्मेट की गुणनखंडन विधि|फ़र्मेट की विधि में एकल संख्या a की खोज शामिल है, n^1/2 < a < n−1, जैसे कि a का शेषफल²n से विभाजित करने पर एक वर्ग प्राप्त होता है। लेकिन इन्हें ढूंढना कठिन है। द्विघात छलनी में a के शेषफल की गणना की जाती है²/n अनेक a के लिए, फिर इनका एक उपसमुच्चय ज्ञात करना जिसका गुणनफल एक वर्ग हो। इससे वर्गों की सर्वांगसमता प्राप्त होगी।

उदाहरण के लिए, संख्या 1649 का गुणनखंड करने का प्रयास करने पर विचार करें। हमारे पास है: $41^{2}\equiv 32,42^{2}\equiv 115,43^{2}\equiv 200{\pmod {1649}}$. कोई भी पूर्णांक नहीं $32,115,200$ एक वर्ग है, लेकिन गुणनफल $32\cdot 200=80^{2}$ एक वर्ग है. हमारे पास भी था

$32\cdot 200\equiv 41^{2}\cdot 43^{2}=(41\cdot 43)^{2}\equiv 114^{2}{\pmod {1649}}$

तब से $41\cdot 43\equiv 114{\pmod {1649}}$. अवलोकन कि $32\cdot 200=80^{2}$ इस प्रकार वर्गों की सर्वांगसमता प्राप्त होती है

$114^{2}\equiv 80^{2}{\pmod {1649}}.$ इस तरह $114^{2}-80^{2}=(114+80)\cdot (114-80)=194\cdot 34=k\cdot 1649$ कुछ पूर्णांक के लिए $k$. हम तब कारक बन सकते हैं

$1649=\gcd(194,1649)\cdot \gcd(34,1649)=97\cdot 17$

सबसे बड़े सामान्य भाजक की गणना करने के लिए यूक्लिडियन एल्गोरिथ्म का उपयोग करना।

तो समस्या अब कम हो गई है: पूर्णांकों का एक सेट दिया गया है, एक उपसमुच्चय खोजें जिसका उत्पाद एक वर्ग है। अंकगणित के मौलिक प्रमेय के अनुसार, किसी भी सकारात्मक पूर्णांक को अभाज्य शक्तियों के उत्पाद के रूप में विशिष्ट रूप से लिखा जा सकता है। हम इसे वेक्टर प्रारूप में करते हैं; उदाहरण के लिए, 504 का अभाज्य-शक्ति गुणनखंडन 2 है³3²5⁰7¹, इसलिए इसे घातांक वेक्टर (3,2,0,1) द्वारा दर्शाया जाता है। फिर दो पूर्णांकों को गुणा करना उनके घातांक सदिशों को जोड़ने के समान होता है। एक संख्या एक वर्ग होती है जब उसका घातांक वेक्टर प्रत्येक निर्देशांक में सम होता है। उदाहरण के लिए, सदिश (3,2,0,1) + (1,0,0,1) = (4,2,0,2), इसलिए (504)(14) एक वर्ग है। एक वर्ग की खोज के लिए केवल सदिशों में संख्याओं की समता (गणित) का ज्ञान आवश्यक है, इसलिए इन सदिशों की गणना mod 2: (1,0,0,1) + (1,0,0,1) करना पर्याप्त है = (0,0,0,0). इसलिए (0,1)-वेक्टर का एक सेट दिया गया है, हमें एक सबसेट ढूंढने की ज़रूरत है जो शून्य वेक्टर मॉड 2 में जुड़ता है।

रिंग (गणित) के बाद से यह एक रैखिक बीजगणित समस्या है $\mathbb {Z} /2\mathbb {Z}$ इसे ऑर्डर 2 के गैलोइस क्षेत्र के रूप में माना जा सकता है, अर्थात मॉड्यूलो 2 की गणना करते समय हम सभी गैर-शून्य संख्याओं (केवल एक है, अर्थात् 1) से विभाजित कर सकते हैं। यह एक रैंक-शून्यता प्रमेय है कि प्रत्येक वेक्टर की प्रविष्टियों की तुलना में अधिक वेक्टर के साथ, एक रैखिक निर्भरता हमेशा मौजूद रहती है। इसे गाऊसी उन्मूलन द्वारा पाया जा सकता है। हालाँकि, बस कई यादृच्छिक संख्याओं का वर्ग करने से बहुत बड़ी संख्या में विभिन्न अभाज्य संख्या कारक उत्पन्न होते हैं, और इसलिए बहुत लंबे वैक्टर और एक बहुत बड़ा मैट्रिक्स होता है। तरकीब यह है कि संख्याओं को विशेष रूप से इस प्रकार खोजा जाए कि a²mod n में केवल छोटे अभाज्य गुणनखंड हैं (वे सुचारु संख्याएँ हैं)। उन्हें ढूंढना कठिन है, लेकिन केवल सुचारु संख्याओं का उपयोग करने से सदिश और आव्यूह छोटे और अधिक सुव्यवस्थित रहते हैं। द्विघात छलनी छलनी सिद्धांत नामक तकनीक का उपयोग करके चिकनी संख्याओं की खोज करती है, जिस पर बाद में चर्चा की गई है, जिससे एल्गोरिदम अपना नाम लेता है।

एल्गोरिदम

संक्षेप में कहें तो, बुनियादी द्विघात छलनी एल्गोरिथ्म में ये मुख्य चरण हैं:

1. एक सहज संख्या#परिभाषा बी चुनें। संख्या π(बी), बी से कम अभाज्य गणना फ़ंक्शन, वेक्टर की लंबाई और आवश्यक वैक्टर की संख्या दोनों को नियंत्रित करेगा।
2. π(बी)+1 संख्या ए का पता लगाने के लिए छानने का उपयोग करें_iऐसे कि बी_i= (ए_i²mod n) B-स्मूथ है।
3. फैक्टर बी_iऔर प्रत्येक के लिए घातांक सदिश मॉड 2 उत्पन्न करें।
4. इन सदिशों का एक उपसमुच्चय खोजने के लिए रैखिक बीजगणित का उपयोग करें जो शून्य सदिश में जुड़ता है। संगत a को गुणा करें_i एक साथ और परिणाम mod n को नाम a दें; इसी तरह, बी को गुणा करें_iएक साथ जो एक बी-चिकना वर्ग बी उत्पन्न करता है².
5. अब हम समानता के साथ बचे हैं² = बी²mod n जिससे हमें (a) के दो वर्गमूल मिलते हैं²mod n), b के पूर्णांकों में वर्गमूल लेकर एक²अर्थात् बी, और दूसरे ए की गणना चरण 4 में की गई है।
6. अब हमारे पास वांछित पहचान है: $(a+b)(a-b)\equiv 0{\pmod {n}}$. ए और बी के अंतर (या योग) के साथ एन की जीसीडी की गणना करें। यह एक कारक उत्पन्न करता है, हालाँकि यह एक तुच्छ कारक (n या 1) हो सकता है। यदि कारक तुच्छ है, तो भिन्न रैखिक निर्भरता या भिन्न a के साथ पुनः प्रयास करें।

इस आलेख का शेष भाग इस मूल एल्गोरिथम के विवरण और विस्तार की व्याख्या करता है।

एल्गोरिदम का छद्म कोड

एल्गोरिथ्म द्विघात चलनी है
    चिकनाई बंधी चुनें $B$

होने देना $t=\pi (B)$ के लिए $i\in {1,...,t+1}$ करना

        चुनना $x\in \{0,\pm 1,\pm 2,...\}$
        $a_{i}=x+\lfloor {\sqrt {n}}\rfloor$
        $b_{i}=a_{i}^{2}-n$ (कहाँ $b_{i}=\prod _{j=1}^{t}p_{j}^{e_{i,j}}$)
        जबकि (check-p_t-smooth(b_i) = false) करते हैं
            होने देना $v_{i}=(v_{i,1},v_{i,2},...,v_{i,t})=(e_{i,1}{\bmod {2}},e_{i,2}{\bmod {2}},...,e_{i,t}{\bmod {2}})$

पाना $T\subseteq \{1,2,...,t+1\}:\sum _{i\in T}v_{i}=0\in \mathbb {Z} _{2}$ होने देना $x=\prod _{i\in T}a_{i}{\bmod {n}}$ होने देना $y=\prod _{j=1}^{t}p_{j}^{(\sum _{i\in T}e_{i,j})/2}{\bmod {n}}$ अगर $x\not \equiv -y{\bmod {n}}$ और $x\not \equiv y$ तब

               वापसी gcd(x - y, n) , gcd(x + y, n)
            अन्य :
                मुख्य लूप पर लौटें।

क्यूएस सर्वांगसमता खोजने को कैसे अनुकूलित करता है

द्विघात छलनी पूर्णांक x और y(x) के जोड़े खोजने का प्रयास करती है (जहाँ y(x) x का एक फलन है) x की तुलना में बहुत कमजोर स्थिति को संतुष्ट करता है² ≡ और²(मॉड एन)। यह अभाज्य संख्या के एक सेट का चयन करता है जिसे कारक आधार कहा जाता है, और x को इस प्रकार खोजने का प्रयास करता है कि y(x) का न्यूनतम पूर्ण शेष = x²mod n पूरी तरह से कारक आधार पर गुणनखंडन करता है। ऐसे y मानों को कारक आधार के संबंध में सुचारू कहा जाता है।

y(x) के मान का गुणनखंडन, जो x के मान के साथ कारक आधार पर विभाजित होता है, एक संबंध के रूप में जाना जाता है। द्विघात छलनी x को n के वर्गमूल के करीब ले जाकर संबंध खोजने की प्रक्रिया को तेज करती है। यह सुनिश्चित करता है कि y(x) छोटा होगा, और इस प्रकार इसके सुचारू होने की अधिक संभावना है।

$y(x)=\left(\left\lceil {\sqrt {n}}\right\rceil +x\right)^{2}-n{\hbox{ (where }}x{\hbox{ is a small integer)}}$

$y(x)\approx 2x\left\lceil {\sqrt {n}}\right\rceil$

इसका तात्पर्य यह है कि y 2x के क्रम पर है[√n]. हालाँकि, इसका तात्पर्य यह भी है कि y, n के वर्गमूल के x गुना के साथ रैखिक रूप से बढ़ता है।

सहजता की संभावना बढ़ाने का दूसरा तरीका केवल कारक आधार के आकार को बढ़ाना है। हालाँकि, रैखिक निर्भरता के अस्तित्व को सुनिश्चित करने के लिए, कारक आधार में अभाज्य संख्या से अधिक कम से कम एक सहज संबंध खोजना आवश्यक है।

आंशिक संबंध और चक्र

भले ही कुछ संबंधों के लिए y(x) सहज न हो, फिर भी इनमें से दो आंशिक संबंधों को मिलाकर एक पूर्ण संबंध बनाना संभव हो सकता है, यदि दोनों y'कारक आधार के बाहर समान अभाज्य के उत्पाद हैं। [ध्यान दें कि यह कारक आधार को विस्तारित करने के बराबर है।] उदाहरण के लिए, यदि कारक आधार {2, 3, 5, 7} और n = 91 है, तो आंशिक संबंध हैं:

${21^{2}\equiv 7^{1}\cdot 11{\pmod {91}}}$

${29^{2}\equiv 2^{1}\cdot 11{\pmod {91}}}$

इन्हें एक साथ गुणा करें:

${(21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}\cdot 11^{2}{\pmod {91}}}$

और दोनों पक्षों को (11) से गुणा करें⁻¹)²मॉड्यूलो 91.11⁻¹ मॉड्यूलो 91 58 है, इसलिए:

$(58\cdot 21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}$

$14^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}$

एक पूर्ण संबंध बनाना। ऐसे पूर्ण संबंध (आंशिक संबंधों को मिलाकर प्राप्त) को चक्र कहा जाता है। कभी-कभी, दो आंशिक संबंधों से एक चक्र बनाने से सीधे वर्गों की सर्वांगसमता हो जाती है, लेकिन शायद ही कभी।

छानकर चिकनाई जांचना

वाईएस की चिकनाई की जांच करने के कई तरीके हैं। सबसे स्पष्ट परीक्षण प्रभाग है, हालांकि इससे डेटा संग्रह चरण के लिए चलने का समय बढ़ जाता है। एक अन्य विधि जिसकी कुछ स्वीकार्यता है वह है लेनस्ट्रा अण्डाकार वक्र गुणनखंडन (ईसीएम)। व्यवहार में, आमतौर पर छानने की प्रक्रिया का उपयोग किया जाता है। यदि f(x) बहुपद है $f(x)=x^{2}-n$ अपने पास

${\begin{aligned}f(x)&=x^{2}-n\\f(x+kp)&=(x+kp)^{2}-n\\&=x^{2}+2xkp+(kp)^{2}-n\\&=f(x)+2xkp+(kp)^{2}\equiv f(x){\pmod {p}}\end{aligned}}$

इस प्रकार x के लिए f(x) ≡ 0 (mod p) को हल करने से संख्याओं y का एक संपूर्ण अनुक्रम उत्पन्न होता है जिसके लिए y=f(x), जो सभी p से विभाज्य होते हैं। यह एक वर्गमूल मॉड्यूलो को एक प्राइम ढूंढ रहा है, जिसके लिए शैंक्स-टोनेली एल्गोरिदम जैसे कुशल एल्गोरिदम मौजूद हैं। (यह वह जगह है जहां द्विघात छलनी को इसका नाम मिलता है: y, x में एक द्विघात बहुपद है, और छानने की प्रक्रिया एराटोस्थनीज की छलनी की तरह काम करती है।)

छलनी बाइट्स की एक बड़ी सरणी A[] में प्रत्येक प्रविष्टि को शून्य पर सेट करके शुरू होती है। प्रत्येक पी के लिए, दो मूल α और β प्राप्त करने के लिए द्विघात समीकरण मॉड पी को हल करें, और फिर प्रत्येक प्रविष्टि में लॉग (पी) में एक सन्निकटन जोड़ें जिसके लिए y (x) = 0 मॉड पी ... यानी, ए [केपी + α] और ए[kp+β]। कारक-आधार प्राइम की छोटी शक्तियों द्वारा विभाज्य संख्याओं को पहचानने के लिए पी की द्विघात समीकरण मॉड्यूलो छोटी शक्तियों को हल करना भी आवश्यक है।

कारक आधार के अंत में, कोई भी A[] जिसमें मोटे तौर पर लॉग (x) की सीमा से ऊपर का मान होता है²−n) y(x) के मान के अनुरूप होगा जो कारक आधार पर विभाजित होता है। इस बारे में जानकारी कि वास्तव में कौन से अभाज्य संख्याएँ y(x) को विभाजित करती हैं, खो गई हैं, लेकिन इसमें केवल छोटे कारक हैं, और किसी संख्या के गुणनखंडन के लिए कई अच्छे एल्गोरिदम हैं जो केवल छोटे कारकों के लिए जाने जाते हैं, जैसे कि छोटे अभाज्यों द्वारा परीक्षण विभाजन, SQUFOF, पोलार्ड रो, और ईसीएम, जो आमतौर पर कुछ संयोजन में उपयोग किए जाते हैं।

ऐसे कई y(x) मान हैं जो काम करते हैं, इसलिए अंत में गुणनखंडन प्रक्रिया का पूरी तरह से विश्वसनीय होना जरूरी नहीं है; अक्सर प्रक्रियाएं मान लीजिए कि 5% इनपुट पर गलत व्यवहार करती हैं, जिसके लिए थोड़ी मात्रा में अतिरिक्त छानने की आवश्यकता होती है।

बुनियादी छलनी का उदाहरण

यह उदाहरण लघुगणक अनुकूलन या अभाज्य शक्तियों के बिना मानक द्विघात छलनी प्रदर्शित करेगा। मान लीजिए कि गुणनखंडित होने वाली संख्या N = 15347 है, इसलिए N के वर्गमूल की अधिकतम सीमा 124 है। चूँकि N छोटा है, मूल बहुपद पर्याप्त है: y(x) = (x + 124)²- 15347.

डेटा संग्रह

चूँकि N छोटा है, केवल 4 अभाज्य संख्याएँ आवश्यक हैं। पहले 4 अभाज्य संख्याएँ p जिनके लिए 15347 का वर्गमूल modulo p है वे 2, 17, 23, और 29 हैं (दूसरे शब्दों में, 15347 इनमें से प्रत्येक अभाज्य संख्या एक द्विघात अवशेष मापांक है)। ये अभाज्य पदार्थ छानने का आधार होंगे।

अब हम अपनी छलनी बनाते हैं $V_{X}$ का $Y(X)=(X+\lceil {\sqrt {N}}\rceil )^{2}-N=(X+124)^{2}-15347$ और आधार में प्रत्येक अभाज्य के लिए छानने की प्रक्रिया शुरू करें, Y(X) के पहले 0 ≤ X <100 को छानने का चयन करें:

${\begin{aligned}V&={\begin{bmatrix}Y(0)&Y(1)&Y(2)&Y(3)&Y(4)&Y(5)&\cdots &Y(99)\end{bmatrix}}\\&={\begin{bmatrix}29&278&529&782&1037&1294&\cdots &34382\end{bmatrix}}\end{aligned}}$

अगला कदम छलनी करना है। हमारे कारक आधार में प्रत्येक पी के लिए $\lbrace 2,17,23,29\rbrace$ प्रश्न हल करें

$Y(X)\equiv (X+\lceil {\sqrt {N}}\rceil )^{2}-N\equiv 0{\pmod {p}}$

सरणी V में उन प्रविष्टियों को ढूँढ़ने के लिए जो p से विभाज्य हैं।

के लिए $p=2$ हल करना $(X+124)^{2}-15347\equiv 0{\pmod {2}}$ समाधान पाने के लिए $X\equiv {\sqrt {15347}}-124\equiv 1{\pmod {2}}$.

इस प्रकार, X=1 से प्रारंभ करके 2 से बढ़ाने पर, प्रत्येक प्रविष्टि 2 से विभाज्य होगी। उन प्रविष्टियों में से प्रत्येक को 2 से विभाजित करने पर परिणाम प्राप्त होते हैं

$V={\begin{bmatrix}29&139&529&391&1037&647&\cdots &17191\end{bmatrix}}$

इसी प्रकार शेष अभाज्य संख्याओं के लिए p in $\lbrace 17,23,29\rbrace$ समीकरण$X\equiv {\sqrt {15347}}-124{\pmod {p}}$ हल किया गया। ध्यान दें कि प्रत्येक p > 2 के लिए, 2 मॉड्यूलर वर्गमूल होने के कारण 2 परिणामी रैखिक समीकरण होंगे।

${\begin{aligned}X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 3{\pmod {17}}\\&&\equiv 9-124&\equiv 4{\pmod {17}}\\X&\equiv {\sqrt {15347}}-124&\equiv 11-124&\equiv 2{\pmod {23}}\\&&\equiv 12-124&\equiv 3{\pmod {23}}\\X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 0{\pmod {29}}\\&&\equiv 21-124&\equiv 13{\pmod {29}}\\\end{aligned}}$

प्रत्येक समीकरण $X\equiv a{\pmod {p}}$ का परिणाम $V_{x}$ x=a पर p से विभाज्य होना और उससे आगे प्रत्येक pth मान। आधार में प्रत्येक अभाज्य के लिए V को a, a+p, a+2p, a+3p आदि पर p से विभाजित करने पर सुस्पष्ट संख्याएँ प्राप्त होती हैं जो अद्वितीय अभाज्य संख्याओं (प्रथम घात) के गुणनफल हैं।

$V={\begin{bmatrix}1&139&23&1&61&647&\cdots &17191\end{bmatrix}}$

V की कोई भी प्रविष्टि जो 1 के बराबर है, एक सहज संख्या से मेल खाती है। तब से $V_{0}$, $V_{3}$, और $V_{71}$ एक के बराबर, यह इससे मेल खाता है:

X + 124	Y	factors
124	29	20 • 170 • 230 • 291
127	782	21 • 171 • 231 • 290
195	22678	21 • 171 • 231 • 291

मैट्रिक्स प्रोसेसिंग

चूँकि संपत्ति के साथ सुस्पष्ट संख्याएँ Y पाई गई हैं $Y\equiv Z^{2}{\pmod {N}}$, एल्गोरिथ्म का शेष भाग डिक्सन की गुणनखंडन विधि के किसी भी अन्य रूपांतर के समान रूप से अनुसरण करता है।

समीकरणों के उपसमुच्चय के गुणनफल के घातांक लिखना

${\begin{aligned}29&=2^{0}\cdot 17^{0}\cdot 23^{0}\cdot 29^{1}\\782&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{0}\\22678&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{1}\\\end{aligned}}$

एक मैट्रिक्स के रूप में ${\pmod {2}}$ पैदावार:

$S\cdot {\begin{bmatrix}0&0&0&1\\1&1&1&0\\1&1&1&1\end{bmatrix}}\equiv {\begin{bmatrix}0&0&0&0\end{bmatrix}}{\pmod {2}}$

समीकरण का एक समाधान बाएँ शून्य स्थान#बाएँ शून्य स्थान द्वारा दिया गया है

$S={\begin{bmatrix}1&1&1\end{bmatrix}}$

इस प्रकार सभी 3 समीकरणों का गुणनफल एक वर्ग (मॉड एन) प्राप्त करता है।

$29\cdot 782\cdot 22678=22678^{2}$

और

$124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2}$

तो एल्गोरिदम मिल गया

$22678^{2}\equiv 3070860^{2}{\pmod {15347}}$

परिणाम का परीक्षण करने पर जीसीडी (3070860 - 22678, 15347) = 103 प्राप्त होता है, जो 15347 का एक गैर-तुच्छ कारक है, दूसरा 149 है।

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

एकाधिक बहुपद

व्यवहार में, y के लिए कई अलग-अलग बहुपदों का उपयोग किया जाता है, क्योंकि केवल एक बहुपद आम तौर पर पर्याप्त (x, y) जोड़े प्रदान नहीं करेगा जो कारक आधार पर सुचारू हों। उपयोग किए गए बहुपदों का एक विशेष रूप होना चाहिए, क्योंकि उन्हें वर्ग मॉड्यूलो n होना आवश्यक है। सभी बहुपदों का रूप मूल y(x) = x के समान होना चाहिए² − n:

$y(x)=(Ax+B)^{2}-n\qquad A,B\in \mathbb {Z}$

यह मानते हुए $B^{2}-n$ A का गुणज है, अतः $B^{2}-n=AC$ बहुपद y(x) को इस प्रकार लिखा जा सकता है $y(x)=A\cdot (Ax^{2}+2Bx+C)$. यदि A एक वर्ग है, तो केवल गुणनखंड $(Ax^{2}+2Bx+C)$ विचार करना होगा.

यह दृष्टिकोण (जिसे एमपीक्यूएस, एकाधिक बहुपद द्विघात छलनी कहा जाता है) समानांतर एल्गोरिदम के लिए आदर्श रूप से उपयुक्त है, क्योंकि कारकीकरण में शामिल प्रत्येक केंद्रीय प्रसंस्करण इकाई को एन, कारक आधार और बहुपदों का संग्रह दिया जा सकता है, और इसके साथ संचार करने की कोई आवश्यकता नहीं होगी केंद्रीय प्रोसेसर जब तक कि यह अपने बहुपदों के साथ समाप्त न हो जाए।

बड़े अभाज्य

एक बड़ा अभाज्य

यदि A से कम सभी गुणनखंडों से भाग देने पर संख्या का शेष भाग (सहकारक) A से कम हो², तो यह सहकारक अभाज्य होना चाहिए। वास्तव में, संबंधों की सूची को सहकारक के आधार पर क्रमबद्ध करके, इसे कारक आधार में जोड़ा जा सकता है। यदि y(a) = 7*11*23*137 और y(b) = 3*5*7*137, तो y(a)y(b) = 3*5*11*23 * 7²*137². यह छलनी सरणी में प्रविष्टियों की सीमा को कम करके काम करता है जिसके ऊपर एक पूर्ण गुणनखंडन किया जाता है।

अधिक बड़े अभाज्य

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

यथार्थवादी उदाहरण से पैरामीटर

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

• ट्रायल फैक्टरिंग कटऑफ: 27 बिट्स
• चलनी अंतराल (प्रति बहुपद): 393216 (32768 आकार के 12 ब्लॉक)
• स्मूथनेस बाउंड: 1300967 (50294 अभाज्य)
• बहुपद A गुणांक के लिए कारकों की संख्या: 10 (ऊपर #एकाधिक बहुपद देखें)
• लार्ज प्राइम बाउंड: 128795733 (26 बिट्स) (ऊपर #लार्ज प्राइम बाउंड देखें)
• सहज मान पाए गए: सीधे छानने से 25952, बड़े अभाज्य संख्याओं के साथ संख्याओं को मिलाकर 24462
• अंतिम मैट्रिक्स आकार: 50294 × 50414, फ़िल्टर करके घटाकर 35750 × 35862 कर दिया गया
• गैर-तुच्छ निर्भरताएँ पाई गईं: 15
• कुल समय (1.6 गीगाहर्ट्ज़ अल्ट्रास्पार्क III पर): 35 मिनट 39 सेकंड
• उपयोग की गई अधिकतम मेमोरी: 8 एमबी

फैक्टरिंग रिकॉर्ड

सामान्य संख्या फ़ील्ड चलनी (एनएफएस) की खोज तक, क्यूएस एसिम्प्टोटिक रूप से सबसे तेज़ ज्ञात सामान्य-उद्देश्य फैक्टरिंग एल्गोरिदम था। अब, लेनस्ट्रा अण्डाकार वक्र फ़ैक्टराइज़ेशन में QS के समान एसिम्प्टोटिक रनिंग टाइम होता है (ऐसे मामले में जहां n में समान आकार के बिल्कुल दो अभाज्य कारक होते हैं), लेकिन व्यवहार में, QS तेज़ है क्योंकि यह बहु-परिशुद्धता के बजाय एकल-परिशुद्धता संचालन का उपयोग करता है अण्डाकार वक्र विधि द्वारा प्रयुक्त संचालन।

2 अप्रैल, 1994 को QS का उपयोग करके RSA-129 का गुणनखंडन पूरा किया गया। यह 129 अंकों की संख्या थी, जो दो बड़े अभाज्य संख्याओं का गुणनफल थी, एक 64 अंकों की और दूसरी 65 अंकों की। इस गुणनखंडन के कारक आधार में 524339 अभाज्य संख्याएँ थीं। डेटा संग्रह चरण में 5000 एमआईपीएस-वर्ष लगे, जो इंटरनेट पर वितरित तरीके से किया गया। एकत्र किया गया डेटा कुल 2गीगाबाइट था। बेलकोर (अब टेलकोर्डिया टेक्नोलॉजीज) के मासपार (बड़े पैमाने पर समानांतर) सुपरकंप्यूटर पर डेटा प्रोसेसिंग चरण में 45 घंटे लगे। यह सामान्य-उद्देश्य एल्गोरिदम द्वारा सबसे बड़ा प्रकाशित फैक्टराइजेशन था, जब तक कि एनएफएस का उपयोग आरएसए-130 को फैक्टर करने के लिए नहीं किया गया था, 10 अप्रैल 1996 को पूरा हुआ। तब से फैक्टर किए गए सभी आरएसए संख्या ों को एनएफएस का उपयोग करके फैक्टर किया गया है।

वर्तमान QS फ़ैक्टराइज़ेशन रिकॉर्ड 140 अंक (463 बिट) RSA-140 है, जिसे जून 2020 में पैट्रिक कोन्सर द्वारा 6 दिनों में लगभग 6,000 कोर घंटों का उपयोग करके फ़ैक्टर किया गया था।

कार्यान्वयन

• PPMPQS और PPSIQS
• mpqs
• SIMPQS विलियम हार्ट द्वारा लिखित स्व-प्रारंभिक बहुपद द्विघात चलनी का एक तेज़ कार्यान्वयन है। यह बड़े प्राइम वैरिएंट के लिए समर्थन प्रदान करता है और रैखिक बीजगणित चरण के लिए जेसन पापाडोपोलोस के ब्लॉक लैंज़ोस कोड का उपयोग करता है। SIMPQS SageMath कंप्यूटर बीजगणित पैकेज में qsieve कमांड के रूप में पहुंच योग्य है या स्रोत रूप में डाउनलोड किया जा सकता है। SIMPQS को एथलॉन और ओपर्टन मशीनों पर उपयोग के लिए अनुकूलित किया गया है, लेकिन यह अधिकांश सामान्य 32- और 64-बिट आर्किटेक्चर पर काम करेगा। यह पूरी तरह से सी में लिखा गया है।
• डारियो अल्पर्न द्वारा एक फैक्टरिंग एप्लेट, जो कुछ शर्तों के पूरा होने पर द्विघात छलनी का उपयोग करता है।
• PARI/GP कंप्यूटर बीजगणित पैकेज में बड़े प्राइम वेरिएंट को लागू करने वाले स्व-प्रारंभिक बहुपद द्विघात छलनी का कार्यान्वयन शामिल है। इसे LiDIA परियोजना के लिए लिखी गई छलनी से थॉमस पापनिकोलाउ और जेवियर रोब्लॉट द्वारा अनुकूलित किया गया था। स्व-आरंभीकरण योजना थॉमस सोस्नोव्स्की की थीसिस के एक विचार पर आधारित है।
• द्विघात छलनी का एक प्रकार मैग्मा कंप्यूटर बीजगणित प्रणाली कंप्यूटर बीजगणित पैकेज में उपलब्ध है। यह 1995 से आर्जेन लेनस्ट्रा के कार्यान्वयन पर आधारित है, जिसका उपयोग ईमेल प्रोग्राम द्वारा फैक्टरिंग में किया गया था।
• msieve, एकल और दोहरे बड़े अभाज्यों के समर्थन के साथ एकाधिक बहुपद द्विघात छलनी का कार्यान्वयन, जेसन पापाडोपोलोस द्वारा लिखित। स्रोत कोड और एक विंडोज़ बाइनरी उपलब्ध हैं।
• YAFU, बेन बुहरो द्वारा लिखित, संभवतः द्विघात छलनी का सबसे तेज़ उपलब्ध कार्यान्वयन है। उदाहरण के लिए, RSA-100 को 2.5 GHz Xeon 6248 CPU के 4 कोर पर 15 मिनट से भी कम समय में तैयार किया गया था। सभी महत्वपूर्ण सबरूटीन्स AMD या Intel प्रोसेसर के लिए AVX2 या AVX-512 SIMD निर्देशों का उपयोग करते हैं। यह जेसन पापाडोपोलोस के ब्लॉक लैंज़ोस कोड का उपयोग करता है। विंडोज़ और लिनक्स के लिए सोर्स कोड और बायनेरिज़ उपलब्ध हैं।
• एरियल, उपदेशात्मक उद्देश्यों के लिए द्विघात छलनी का एक सरल जावा कार्यान्वयन।
• java-math-library में संभवतः जावा में लिखी गई सबसे तेज़ द्विघात छलनी (PSIQS 4.0 का उत्तराधिकारी) शामिल है।
• Java QS, एक खुला स्रोत जावा प्रोजेक्ट जिसमें QS का बुनियादी कार्यान्वयन शामिल है। इल्या गज़मैन द्वारा 4 फरवरी 2016 को रिलीज़ किया गया
• C Quadratic Sieve, एक फ़ैक्टराइज़र जो पूरी तरह से C में लिखा गया है जिसमें सेल्फ-इनिशियलाइज़िंग क्वाड्रैटिक छलनी का कार्यान्वयन शामिल है। यह परियोजना विलियम हार्ट के फ्लिंट फ़ैक्टराइज़र से प्रेरित है। मिशेल लियोनार्ड द्वारा 2022 में जारी किया गया स्रोत बाहरी लाइब्रेरी पर निर्भर नहीं है, यह एक मिनट में 240-बिट संख्याओं और 2 घंटों में 300-बिट संख्याओं को फैक्टर करने में सक्षम है।
• जोसेफ वुड द्वारा RcppBigIntAlgos पैकेज, R_(प्रोग्रामिंग_भाषा) के लिए बहुपद द्विघात चलनी का एक कुशल कार्यान्वयन प्रदान करता है। यह C++ में लिखा गया है और 100 अंकों के सेमीप्राइम को आराम से फ़ैक्टर करने में सक्षम है। उदाहरण के लिए, RSA-100 को 2.8 गीगाहर्ट्ज़ क्वाड-कोर इंटेल कोर i7 पर्सनल कंप्यूटर पर 16 घंटे से कम समय में तैयार किया गया था।

यह भी देखें

• लेनस्ट्रा अण्डाकार वक्र गुणनखंडन
• प्राथमिकता परीक्षण

संदर्भ

• Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective (1st ed.). Springer. ISBN 0-387-94777-9. Section 6.1: The quadratic sieve factorization method, pp. 227–244.

• Samuel S. Wagstaff, Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. pp. 195–202. ISBN 978-1-4704-1048-3.

अन्य बाहरी लिंक

• संदर्भ पत्र द क्वाड्रैटिक सीव फैक्टरिंग एल्गोरिथम एरिक लैंडक्विस्ट द्वारा

श्रेणी:पूर्णांक गुणनखंड एल्गोरिदम