सामान्य संख्या क्षेत्र चालिका (जीएनएफएस)

संख्या सिद्धांत में, सामान्य संख्या क्षेत्र चलनी (जीएनएफएस) सबसे अधिक कलन विधि दक्षता वाला शास्त्रीय एल्गोरिदम है जो पूर्णांक गुणनखंडन के लिए जाना जाता है। 10¹⁰⁰. अनुमानतः, एक पूर्णांक का गुणनखंड करने के लिए इसका कम्प्यूटेशनल जटिलता सिद्धांत n (को मिलाकर ⌊log₂ n⌋ + 1 बिट्स) रूप का है

$\exp \left(\left((64/9)^{1/3}+o(1)\right)\left(\log n\right)^{1/3}\left(\log \log n\right)^{2/3}\right)=L_{n}\left[1/3,(64/9)^{1/3}\right]$

बिग ओ अंकन और एल-नोटेशन में। यह विशेष संख्या क्षेत्र छलनी का एक सामान्यीकरण है: जबकि बाद वाला केवल एक निश्चित विशेष रूप की संख्याओं का गुणनखंड कर सकता है, सामान्य संख्या क्षेत्र चलनी अभाज्य शक्तियों के अलावा किसी भी संख्या का गुणनखंड कर सकती है (जो कि मूल लेकर कारक के लिए तुच्छ हैं)।

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

एल्गोरिथम में इनपुट का आकार है log₂ n या के बाइनरी प्रतिनिधित्व में बिट्स की संख्या n. आदेश का कोई भी तत्व n^c एक स्थिरांक के लिए c में घातीय है log n. संख्या फ़ील्ड चलनी का चलने का समय सुपर-बहुपद है लेकिन इनपुट के आकार में उप-घातांकीय है।

संख्या फ़ील्ड

Main article: Number field

कल्पना करना f एक है k-डिग्री बहुपद खत्म Q (तर्कसंगत संख्याएँ), और r की एक जटिल जड़ है f. तब, f(r) = 0, जिसे व्यक्त करने के लिए पुनर्व्यवस्थित किया जा सकता है r^k की शक्तियों के एक रैखिक संयोजन के रूप में r से कम k. इस समीकरण का उपयोग किसी भी शक्ति को कम करने के लिए किया जा सकता है r प्रतिपादक के साथ e ≥ k. उदाहरण के लिए, यदि f(x) = x² + 1 और r काल्पनिक इकाई है i, तब i² + 1 = 0, या i² = −1. यह हमें जटिल उत्पाद को परिभाषित करने की अनुमति देता है:

$(a+bi)(c+di)=ac+(ad+bc)i+(bd)i^{2}=(ac-bd)+(ad+bc)i.$

सामान्य तौर पर, यह सीधे बीजगणितीय संख्या क्षेत्र की ओर ले जाता है Q[r], जिसे निम्नलिखित द्वारा दी गई सम्मिश्र संख्याओं के समुच्चय के रूप में परिभाषित किया जा सकता है:

$a_{k-1}r^{k-1}+...+a_{1}r^{1}+a_{0}r^{0},{\text{ where }}a_{0},...,a_{k-1}{\text{ in }}\mathbf {Q} .$

ऐसे किन्हीं दो मानों के गुणनफल की गणना गुणनफल को बहुपद के रूप में लेकर, फिर किसी भी घात को कम करके की जा सकती है r प्रतिपादक के साथ e ≥ k जैसा कि ऊपर बताया गया है, उसी रूप में मान प्राप्त होता है। यह सुनिश्चित करने के लिए कि यह फ़ील्ड वास्तव में है k-आयामी और इससे भी छोटे क्षेत्र में नहीं सिमटता, यही पर्याप्त है f परिमेय पर एक अप्रासंगिक बहुपद है। इसी प्रकार, कोई पूर्णांकों के वलय को परिभाषित कर सकता है O_Q[r] के उपसमुच्चय के रूप में Q[r] जो पूर्णांक गुणांक वाले राक्षसी बहुपद के मूल हैं। कुछ मामलों में, पूर्णांकों का यह वलय वलय के समतुल्य होता है Z[r]. हालाँकि, कई अपवाद भी हैं, जैसे कि Q[√d] कब d 1 मॉड्यूलो 4 के बराबर है।

विधि

एक बहुपद d और e की छोटी घात वाले दो बहुपद f(x) और g(x) चुने जाते हैं, जिनमें पूर्णांक गुणांक होते हैं, जो परिमेय संख्या के ऊपर अप्रासंगिक बहुपद होते हैं, और जो, जब मॉड्यूलर अंकगणित की व्याख्या करते हैं, तो एक सामान्य पूर्णांक मूल होता है एक फ़ंक्शन का एम. इन बहुपदों को चुनने के लिए कोई इष्टतम रणनीति ज्ञात नहीं है; एक सरल विधि यह है कि एक बहुपद के लिए एक घात d चुना जाए, क्रम n के विभिन्न m की संख्या के लिए मूलांक में n के विस्तार पर विचार किया जाए (−m और m के बीच अंकों की अनुमति दी जाए)^1/d, और सबसे छोटे गुणांक वाले बहुपद के रूप में f(x) और x - m के रूप में g(x) को चुनें।

संख्या फ़ील्ड रिंग 'Z'[r' पर विचार करें₁] और Z[r₂], जहां आर₁ और आर₂ बहुपद f और g की जड़ें हैं। चूँकि f पूर्णांक गुणांकों के साथ घात d का है, यदि a और b पूर्णांक हैं, तो b भी पूर्णांक होंगे^d·f(a/b), जिसे हम r कहते हैं। इसी प्रकार, s = b^e·g(a/b) एक पूर्णांक है. लक्ष्य ए और बी के पूर्णांक मानों को ढूंढना है जो एक साथ अभाज्य संख्याओं के चुने हुए आधार के सापेक्ष आर और एस को सहज संख्या बनाते हैं। यदि a और b छोटे हैं, तो r और s भी छोटे होंगे, लगभग m के आकार के, और हमारे पास एक ही समय में उनके सुचारू होने की बेहतर संभावना है। इस खोज के लिए वर्तमान सबसे प्रसिद्ध तरीका जाली छानना है; स्वीकार्य उपज प्राप्त करने के लिए बड़े कारक आधार का उपयोग करना आवश्यक है।

ऐसे पर्याप्त जोड़े होने पर, गाऊसी उन्मूलन का उपयोग करके, एक ही समय में कुछ आर और संबंधित एस के उत्पादों को वर्ग के रूप में प्राप्त किया जा सकता है। थोड़ी मजबूत स्थिति की आवश्यकता है - कि वे हमारे संख्या क्षेत्रों में वर्गों के क्षेत्र मानदंड हैं, लेकिन वह स्थिति इस विधि द्वारा भी प्राप्त की जा सकती है। प्रत्येक r, a - r का एक मानक है₁b और इसलिए संबंधित कारकों का उत्पाद a − r है₁b 'Z'[r' में एक वर्ग है₁], एक वर्गमूल के साथ जिसे निर्धारित किया जा सकता है (Z[r में ज्ञात कारकों के उत्पाद के रूप में)₁])—इसे आम तौर पर एक अपरिमेय बीजगणितीय संख्या के रूप में दर्शाया जाएगा। इसी प्रकार, कारकों का उत्पाद a − r₂b 'Z'[r' में एक वर्ग है₂], एक वर्गमूल के साथ जिसकी गणना भी की जा सकती है। यह टिप्पणी की जानी चाहिए कि गॉसियन उन्मूलन का उपयोग एल्गोरिदम का इष्टतम रन टाइम नहीं देता है। इसके बजाय, विरल मैट्रिक्स सॉल्विंग एल्गोरिदम जैसे कि एक परिमित क्षेत्र पर मैट्रिक्स के नलस्पेस के लिए ब्लॉक लैंज़ोस एल्गोरिदम या ब्लॉक विडेमैन एल्गोरिथम का उपयोग किया जाता है।

चूँकि m, f और g mod n दोनों का मूल है, रिंग 'Z'[r' से समरूपताएँ हैं₁] और Z[r₂] रिंग Z/nZ (पूर्णांक मॉड्यूलर अंकगणित|modulo n), जो मानचित्र r₁ और आर₂ से मी, और ये समरूपताएं प्रत्येक वर्गमूल (आमतौर पर तर्कसंगत संख्या के रूप में प्रदर्शित नहीं) को उसके पूर्णांक प्रतिनिधि में मैप करेंगी। अब गुणनखंड a - mb mod n का गुणनफल दो तरीकों से एक वर्ग के रूप में प्राप्त किया जा सकता है - प्रत्येक समरूपता के लिए एक। इस प्रकार, कोई व्यक्ति x के साथ दो संख्याएँ x और y पा सकता है² − और²n से विभाज्य और फिर से कम से कम एक आधे की संभावना के साथ हमें n और x - y का सबसे बड़ा सामान्य भाजक ढूंढकर n का एक कारक मिलता है।

बहुपद विकल्प में सुधार

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

ऐसी ही एक विधि मर्फी और ब्रेंट द्वारा सुझाई गई थी; वे बहुपदों के लिए दो-भाग का स्कोर पेश करते हैं, जो मूल मॉड्यूलो छोटे अभाज्यों की उपस्थिति और उस औसत मूल्य पर आधारित होता है जो बहुपद छानने वाले क्षेत्र पर लेता है।

सर्वोत्तम रिपोर्ट किए गए परिणाम थॉर्स्टन क्लेनजंग की विधि द्वारा प्राप्त किए गए थे, अनुमति अनुसार g(x) = ax + b, और खोज करता है a 1 मॉड्यूलो 2 के अनुरूप छोटे अभाज्य कारकों से बना हैd और के अग्रणी गुणांक f जो 60 से विभाज्य हैं।

कार्यान्वयन

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

बहुपद चयन आम तौर पर क्लेनजंग द्वारा लिखित जीपीएल सॉफ्टवेयर द्वारा या एमसिवे द्वारा किया जाता है, और फ्रांके और क्लेनजंग द्वारा लिखित जीपीएल सॉफ्टवेयर द्वारा जाली छानने का कार्य किया जाता है; इन्हें जीजीएनएफएस में वितरित किया जाता है।

• NFS@Home
• GGNFS
• gnfs द्वारा कारक
• CADO-NFS
• msieve (जिसमें अंतिम-प्रसंस्करण कोड, छोटी संख्याओं के लिए अनुकूलित एक बहुपद चयन और लाइन छलनी का कार्यान्वयन शामिल है)
• kmGNFS

यह भी देखें

• विशेष संख्या क्षेत्र चलनी

संदर्भ

• Arjen K. Lenstra and H. W. Lenstra, Jr. (eds.). "The development of the number field sieve". Lecture Notes in Math. (1993) 1554. Springer-Verlag.
• Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective (2001). 2nd edition, Springer. ISBN 0-387-25282-7. Section 6.2: Number field sieve, pp. 278–301.

• Matthew E. Briggs: An Introduction to the General Number Field Sieve, 1998