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

संख्या सिद्धांत में, सामान्य संख्या क्षेत्र चालिका (जीएनएफएस) सबसे अधिक कलन विधि दक्षता वाला पारम्परिक कलन विधि है जो 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 एक स्थिरांक log n के लिए c में घातीय है। संख्या अनुक्षेत्र चलनी का चलने का समय सुपर-बहुपद है लेकिन निविष्ट के आकार में उप-घातांकीय है।

संख्या अनुक्षेत्र

Main article: संख्या अनुक्षेत्र

मान लीजिए कि f, Q (तर्कसंगत संख्या) पर एक k-डिग्री बहुपद है, और r, f का एक जटिल मूल है। तब, f(r) = 0, जिसे k से कम r की घात के रैखिक संयोजन के रूप में r^k को व्यक्त करने के लिए पुनर्व्यवस्थित किया जा सकता है। इस समीकरण का उपयोग घातांक e ≥ k के साथ r की किसी भी घात को कम करने के लिए किया जा सकता है। उदाहरण के लिए, यदि 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} .$

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

विधि

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

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

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

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

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

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

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

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

कार्यान्वयन

कुछ कार्यान्वयन संख्याओं के एक निश्चित छोटे वर्ग पर ध्यान केंद्रित करते हैं। इन्हें विशेष संख्या क्षेत्र छलनी तकनीकों के रूप में जाना जाता है, जैसे कि कनिंघम परियोजना में उपयोग किया जाता है।

एनएफएसएनईटी नामक एक परियोजना 2002 से कम से कम 2007 तक चली। इसमें इंटरनेट पर स्वैच्छिक रूप से वितरित कंप्यूटिंग का उपयोग किया गया।

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

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

• NFS@Home
• GGNFS
• factor by gnfs
• CADO-NFS
• एमएसआईईवीई (जिसमें अंतिम-प्रसंस्करण कूट, छोटी संख्याओं के लिए अनुकूलित एक बहुपद चयन और रेखा छलनी का कार्यान्वयन सम्मिलित है)
• 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