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

संख्या सिद्धांत में, गणित की एक शाखा, विशेष संख्या क्षेत्र छलनी (एसएनएफएस) एक विशेष-उद्देश्य पूर्णांक गुणनखंड एल्गोरिथ्म है। सामान्य संख्या क्षेत्र छलनी (GNFS) इससे प्राप्त की गई थी।

विशेष संख्या क्षेत्र छलनी r रूप के पूर्णांकों के लिए कुशल है^e ± s, जहाँ r और s छोटे हैं (उदाहरण के लिए Mersenne संख्याएँ)।

अनुमानी रूप से, पूर्णांक के गुणनखंड के लिए इसका कम्प्यूटेशनल जटिलता सिद्धांत $n$ रूप का है:

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

बिग ओ नोटेशन और एल अंकन में।

SNFS का उपयोग NFSNet (एक स्वयंसेवक वितरित कंप्यूटिंग प्रयास), NFS@Home और अन्य लोगों द्वारा कनिंघम परियोजना की संख्याओं का गुणनखण्ड करने के लिए बड़े पैमाने पर किया गया है; कुछ समय के लिए पूर्णांक गुणनखंड रिकॉर्ड को SNFS द्वारा संख्याबद्ध किया गया है।

विधि का अवलोकन

एसएनएफएस बहुत सरल तर्कसंगत छलनी के समान विचार पर आधारित है; विशेष रूप से, पाठकों को एसएनएफएस से निपटने से पहले, तर्कसंगत छलनी के बारे में पढ़ने में मदद मिल सकती है।

एसएनएफएस निम्नानुसार काम करता है। चलो n वह पूर्णांक बनें जिसे हम कारक बनाना चाहते हैं। तर्कसंगत चलनी के रूप में, एसएनएफएस को दो चरणों में तोड़ा जा सकता है:

• सबसे पहले, मॉड्यूलर अंकगणित #Congruence|'Z'/n'Z' के तत्वों के एक कारक आधार के बीच बड़ी संख्या में गुणात्मक संबंध खोजें, जैसे गुणक संबंधों की संख्या कारक आधार में तत्वों की संख्या से बड़ी हो।
• दूसरा, इन संबंधों के उपसमुच्चयों को एक साथ इस तरह से गुणा करें कि सभी घातांक सम हों, परिणाम स्वरूप a की सर्वांगसमता हो²≡बी² (मॉड्यूलर अंकगणित n)। बदले में ये तुरंत n के गुणनखंडों की ओर ले जाते हैं: n=महानतम समापवर्तक(a+b,n)×gcd(a-b,n)। यदि सही तरीके से किया जाता है, तो यह लगभग निश्चित है कि कम से कम एक ऐसा गुणनखंड गैर-तुच्छ होगा।

दूसरा चरण तर्कसंगत छलनी के मामले के समान है, और एक सीधा रैखिक बीजगणित समस्या है। पहला कदम, हालांकि, बीजगणितीय संख्या क्षेत्र का उपयोग करके तर्कसंगत छलनी की तुलना में एक अलग, अधिक एल्गोरिथम दक्षता तरीके से किया जाता है।

विधि का विवरण

चलो n वह पूर्णांक बनें जिसे हम कारक बनाना चाहते हैं। हम पूर्णांक गुणांक के साथ एक अलघुकरणीय बहुपद f चुनते हैं, और एक पूर्णांक m ऐसा है कि f(m)≡0 (मॉड्यूलर अंकगणितीय n) (हम समझाएंगे कि वे अगले भाग में कैसे चुने जाते हैं)। मान लीजिए कि α f के फलन का मूल है; फिर हम वलय (गणित) 'पूर्णांक' [α] बना सकते हैं। 'Z'[α] से मॉड्यूलर अंकगणित#Congruence|'Z'/n'Z' तक एक अद्वितीय रिंग समरूपता φ है जो α से m को मैप करता है। सरलता के लिए, हम मान लेंगे कि 'Z'[α] एक अद्वितीय गुणनखण्ड डोमेन है; एल्गोरिथ्म को काम करने के लिए संशोधित किया जा सकता है जब यह नहीं होता है, लेकिन फिर कुछ अतिरिक्त जटिलताएँ होती हैं।

अगला, हम दो समानांतर कारक आधार स्थापित करते हैं, एक 'Z' [α] में और एक 'Z' में। 'Z' [α] में से एक में 'Z' [α] में सभी प्रमुख आदर्श शामिल हैं, जिसका मानदंड एक चुने हुए मूल्य से घिरा है $N_{\max }$. जेड में कारक आधार, जैसा कि तर्कसंगत छलनी मामले में है, में सभी प्रमुख पूर्णांक होते हैं जो किसी अन्य सीमा तक होते हैं।

इसके बाद हम पूर्णांकों के अपेक्षाकृत अभाज्य युग्मों (a,b) की खोज करते हैं जैसे कि:

• a+bm Z में कारक आधार के संबंध में चिकनी संख्या है (यानी, यह कारक आधार में तत्वों का उत्पाद है)।
• a+bα Z[α] में कारक आधार के संबंध में चिकना है; यह देखते हुए कि हमने कारक आधार को कैसे चुना, यह a+bα के मानदंड के बराबर है जो केवल प्राइम्स से कम से विभाज्य है $N_{\max }$.

ये जोड़े एक छलनी प्रक्रिया के माध्यम से पाए जाते हैं, एराटोस्थनीज की छलनी के अनुरूप; यह नाम संख्या क्षेत्र छलनी को प्रेरित करता है।

ऐसी प्रत्येक जोड़ी के लिए, हम रिंग समरूपता φ को a+bα के गुणनखंड में लागू कर सकते हैं, और हम a+bm के गुणनखंडन के लिए 'Z' से 'Z'/n'Z' तक विहित वलय समरूपता लागू कर सकते हैं। इन्हें बराबर सेट करने से 'Z'/n'Z' में एक बड़े कारक आधार के तत्वों के बीच गुणक संबंध मिलता है, और यदि हमें पर्याप्त जोड़े मिलते हैं तो हम उपरोक्त वर्णित संबंधों और कारक n को जोड़ने के लिए आगे बढ़ सकते हैं।

मापदंडों का चुनाव

एसएनएफएस के लिए प्रत्येक संख्या एक उपयुक्त विकल्प नहीं है: आपको पहले से उपयुक्त डिग्री के एक बहुपद एफ को जानना होगा (इष्टतम डिग्री होने का अनुमान लगाया गया है) $\left(3{\frac {\log N}{\log \log N}}\right)^{\frac {1}{3}}$, जो 4, 5, या 6 है N के आकार के लिए जो वर्तमान में कारक बनाने के लिए संभव है) छोटे गुणांक के साथ, और एक मान x ऐसा है कि $f(x)\equiv 0{\pmod {N}}$ जहाँ N वह संख्या है जिसका गुणनखंड किया जाना है। एक अतिरिक्त शर्त है: x को संतुष्ट होना चाहिए $ax+b\equiv 0{\pmod {N}}$ ए और बी से बड़ा नहीं $N^{1/d}$.

संख्याओं का एक सेट जिसके लिए इस तरह के बहुपद मौजूद हैं $a^{b}\pm 1$ कनिंघम परियोजना से संख्याएँ; उदाहरण के लिए, जब NFSNET ने फैक्टर किया $3^{479}+1$, उन्होंने बहुपद का प्रयोग किया $x^{6}+3$ साथ $x=3^{80}$, तब से $(3^{80})^{6}+3=3^{480}+3$, और $3^{480}+3\equiv 0{\pmod {3^{479}+1}}$.

रेखीय पुनरावृत्ति द्वारा परिभाषित संख्याएँ, जैसे कि फाइबोनैचि संख्या और लुकास संख्या संख्याएँ, में भी SNFS बहुपद होते हैं, लेकिन इनका निर्माण करना थोड़ा अधिक कठिन होता है। उदाहरण के लिए, $F_{709}$ बहुपद है $n^{5}+10n^{3}+10n^{2}+10n+3$, और x का मान संतुष्ट करता है $F_{142}x-F_{141}=0$. यदि आप पहले से ही एक बड़ी SNFS-संख्या के कुछ कारकों को जानते हैं, तो आप शेष भाग में SNFS गणना मॉड्यूलो कर सकते हैं; उपरोक्त NFSNET उदाहरण के लिए, $3^{479}+1=(4\times 158071\times 7167757\times 7759574882776161031)$ 197 अंकों की समग्र संख्या (छोटे कारकों को अण्डाकार वक्र विधि द्वारा हटा दिया गया था) का गुना, और SNFS को 197 अंकों की संख्या के रूप में प्रदर्शित किया गया था। एसएनएफएस द्वारा आवश्यक संबंधों की संख्या अभी भी बड़ी संख्या के आकार पर निर्भर करती है, लेकिन अलग-अलग गणनाएं छोटी संख्या के त्वरित रूप से होती हैं।

एल्गोरिथम की सीमाएं

यह एल्गोरिथम, जैसा कि ऊपर बताया गया है, फॉर्म आर की संख्याओं के लिए बहुत कुशल है^e±s, r और s के लिए अपेक्षाकृत छोटा है। यह किसी भी पूर्णांक के लिए भी कुशल है जिसे छोटे गुणांक वाले बहुपद के रूप में दर्शाया जा सकता है। इसमें अधिक सामान्य रूप ar के पूर्णांक शामिल हैं^और±बीएस^f, और कई पूर्णांकों के लिए भी जिनके बाइनरी प्रतिनिधित्व में हैमिंग वजन कम है। इसका कारण इस प्रकार है: संख्या क्षेत्र छलनी दो अलग-अलग क्षेत्रों में छानने का काम करती है। पहला क्षेत्र आमतौर पर तर्कसंगत है। दूसरा एक उच्च डिग्री क्षेत्र है। एल्गोरिथम की दक्षता दृढ़ता से इन क्षेत्रों में कुछ तत्वों के मानदंडों पर निर्भर करती है। जब एक पूर्णांक को छोटे गुणांक वाले बहुपद के रूप में दर्शाया जा सकता है, तो उत्पन्न होने वाले मानदंड उन लोगों की तुलना में बहुत छोटे होते हैं, जब एक पूर्णांक को एक सामान्य बहुपद द्वारा दर्शाया जाता है। इसका कारण यह है कि एक सामान्य बहुपद के बहुत बड़े गुणांक होंगे, और मानदंड तदनुसार बड़े होंगे। एल्गोरिथ्म इन मानदंडों को अभाज्य संख्याओं के एक निश्चित सेट पर कारक बनाने का प्रयास करता है। जब मानदंड छोटे हैं, इन नंबरों के कारक होने की अधिक संभावना है।

यह भी देखें

• सामान्य संख्या क्षेत्र छलनी

अग्रिम पठन

• Byrnes, Steven (May 18, 2005), "The Number Field Sieve" (PDF), Math 129
• Lenstra, A. K.; Lenstra, H. W., Jr.; Manasse, M. S. & Pollard, J. M. (1993), "The Factorization of the Ninth Fermat Number", Mathematics of Computation, 61 (203): 319–349, Bibcode:1993MaCom..61..319L, doi:10.1090/S0025-5718-1993-1182953-4{{citation}}: CS1 maint: multiple names: authors list (link)
• Lenstra, A. K.; Lenstra, H. W., Jr., eds. (1993), The Development of the Number Field Sieve, Lecture Notes in Mathematics, vol. 1554, New York: Springer-Verlag, ISBN 978-3-540-57013-4{{citation}}: CS1 maint: multiple names: editors list (link)
• Silverman, Robert D. (2007), "Optimal Parameterization of SNFS", Journal of Mathematical Cryptology, 1 (2): 105–124, CiteSeerX 10.1.1.12.2975, doi:10.1515/JMC.2007.007, S2CID 16236028