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

Latest revision as of 10:10, 1 July 2023

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

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

अनुमानी रूप से पूर्णांक के गुणनखंड में इसका अभिकलन जटिलता सिद्धांत $n$ रूप का है जो इस प्रकार है ^[1]

\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 का उपयोग NFS जाल एक स्वयंसेवक वितरित गणना का प्रयास NFS@Home और अन्य लोगों द्वारा कनिंघम परियोजना की संख्याओं का गुणनखण्ड करने के लिए बड़े पैमाने पर किया गया है कुछ समय के लिए पूर्णांक गुणनखंड लेखबद्ध करने को SNFS द्वारा संख्याबद्ध किया गया है।

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

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

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

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

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

विधि का विवरण

n वह पूर्णांक बनें जिसे हम कारक बनाना चाहते हैं तथा पूर्णांक गुणांक के साथ एक अलघुकरणीय बहुपद f चुनते हैं और एक पूर्णांक m ऐसा है कि f(m)≡0 प्रमापीय अंकगणित n हम जानते हैं कि वे अगले भाग में कैसे चुने जाते हैं मान लीजिए कि α f के फलन का मूल है फिर हम वलय गणित पूर्णांक [α] बना सकते हैं 'Z'[α] से प्रमापीय अंकगणित अनुरूपता में Z/n'Z' तक एक अद्वितीय वलय समरूपता φ है जो α से m को सही करता है सरलता के लिए हम मान लेंगे कि '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$ .^[2]यदि आप पहले से ही एक बड़ी SNFS-संख्या के कुछ कारकों को जानते हैं तो आप शेष भाग में SNFS गणना कर सकते हैं उपरोक्त NFSNET उदाहरण के लिए $3^{479}+1=(4\times 158071\times 7167757\times 7759574882776161031)$ 197 अंकों की समग्र संख्या छोटे कारकों को अण्डाकार वक्र विधि द्वारा हटा दिया गया था का गुना और SNFS को 197 अंकों की संख्या के रूप में प्रदर्शित किया गया था एसएनएफएस द्वारा आवश्यक संबंधों की संख्या अभी भी बड़ी संख्या के आकार पर निर्भर करती है लेकिन अलग-अलग गणनाएं छोटी संख्या के त्वरित रूप में होती हैं।

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

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

यह भी देखें

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

संदर्भ

↑ Pomerance, Carl (December 1996), "A Tale of Two Sieves" (PDF), Notices of the AMS, vol. 43, no. 12, pp. 1473–1485
↑ Franke, Jens. "Installation notes for ggnfs-lasieve4". MIT Massachusetts Institute of Technology.

अग्रिम पठन

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

[1] Pomerance, Carl (December 1996), "A Tale of Two Sieves" (PDF), Notices of the AMS, vol. 43, no. 12, pp. 1473–1485

[2] Franke, Jens. "Installation notes for ggnfs-lasieve4". MIT Massachusetts Institute of Technology.

[1]

[2]

@@ Line 1: / Line 1: @@
-[[संख्या सिद्धांत]] में गणित की एक शाखा विशेष संख्या क्षेत्र छलनी एसएनएफएस एक विशेष उद्देश्य पूर्णांक गुणनखंड प्रारूप है [[सामान्य संख्या क्षेत्र छलनी]] (GNFS) इससे प्राप्त की गई थी।
+[[संख्या सिद्धांत]] में गणित की एक शाखा है जो संख्या क्षेत्र छलनी एसएनएफएस एक विशेष उद्देश्य का पूर्णांक गुणनखंड प्रारूप है [[सामान्य संख्या क्षेत्र छलनी|तथा सामान्य संख्या क्षेत्र छलनी]] (GNFS) इससे प्राप्त की गई थी।
-विशेष क्षेत्र में छलनी ''r'' रूप के पूर्णांकों के लिए कुशल हैजहॉं <sup>e</sup> ± s व r और s छोटे हैं उदाहरण के लिए मिश्रित संख्याएँ
+विशेष क्षेत्र में छलनी ''r'' रूप के पूर्णांकों के लिए कुशल है जहॉं <sup>e</sup> ± s व r और s छोटे हैं उदाहरण मिश्रित संख्याएँ
 [[अनुमानी]] रूप से पूर्णांक के गुणनखंड में इसका [[कम्प्यूटेशनल जटिलता सिद्धांत|अभिकलन जटिलता सिद्धांत]] <math>n</math> रूप का है जो इस प्रकार है <ref>{{Citation|last=Pomerance|first=Carl|author-link=Carl Pomerance|date=December 1996|title=A Tale of Two Sieves|periodical=Notices of the AMS|volume=43|issue=12|pages=1473–1485|url=http://www.ams.org/notices/199612/pomerance.pdf}}</ref>
@@ Line 11: / Line 11: @@
 == विधि का अवलोकन ==
-एसएनएफएस बहुत सरल तर्कसंगत छलनी के समान विचार पर आधारित है; विशेष रूप से, पाठकों को एसएनएफएस से निपटने से पहले, तर्कसंगत छलनी के बारे में पढ़ने में मदद मिल सकती है।
+एसएनएफएस बहुत सरल तर्कसंगत छलनी के समान विचार पर आधारित है यह विशेष रूप से पाठकों को एसएनएफएस से निपटने से पहले तर्कसंगत छलनी के बारे में पढ़ने में मदद मिल सकती है
-एसएनएफएस निम्नानुसार काम करता है। चलो n वह पूर्णांक बनें जिसे हम कारक बनाना चाहते हैं। [[तर्कसंगत चलनी]] के रूप में, एसएनएफएस को दो चरणों में तोड़ा जा सकता है:
+एसएनएफएस निम्नानुसार काम करता है n वह पूर्णांक बनें जिसे हम कारक बनाना चाहते हैं [[तर्कसंगत चलनी]] के रूप में एसएनएफएस को दो चरणों में तोड़ा जा सकता है
-*सबसे पहले, मॉड्यूलर अंकगणित #Congruence|'Z'/n'Z' के तत्वों के एक कारक आधार के बीच बड़ी संख्या में गुणात्मक संबंध खोजें, जैसे गुणक संबंधों की संख्या कारक आधार में तत्वों की संख्या से बड़ी हो।
+*सबसे पहले प्रमापीय अंकगणित अनुरूपता Z /nZ के तत्वों के एक कारक आधार के बीच बड़ी संख्या में गुणात्मक संबंध खोजें जैसे गुणक संबंधों की संख्या कारक आधार में तत्वों की संख्या से बड़ी हो
-*दूसरा, इन संबंधों के उपसमुच्चयों को एक साथ इस तरह से गुणा करें कि सभी घातांक सम हों, परिणाम स्वरूप a की सर्वांगसमता हो<sup>2</sup>≡बी<sup>2</sup> ([[मॉड्यूलर अंकगणित]] n)। बदले में ये तुरंत n के गुणनखंडों की ओर ले जाते हैं: n=महानतम समापवर्तक(a+b,n)×gcd(a-b,n)। यदि सही तरीके से किया जाता है, तो यह लगभग निश्चित है कि कम से कम एक ऐसा गुणनखंड गैर-तुच्छ होगा।
+*दूसरा इन संबंधों के उपसमुच्चयों को एक साथ इस तरह से गुणा करें कि सभी घातांक सम हों परिणाम स्वरूप a की सर्वांगसमता हो<sup>2</sup>≡बी<sup>2</sup> प्रमापीय [[मॉड्यूलर अंकगणित|अंकगणित]] 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'[α] एक अद्वितीय गुणनखण्ड डोमेन है; एल्गोरिथ्म को काम करने के लिए संशोधित किया जा सकता है जब यह नहीं होता है, लेकिन फिर कुछ अतिरिक्त जटिलताएँ होती हैं।
+n वह [[पूर्णांक]] बनें जिसे हम कारक बनाना चाहते हैं तथा पूर्णांक गुणांक के साथ एक [[अलघुकरणीय बहुपद]] f चुनते हैं और एक पूर्णांक m ऐसा है कि f(m)≡0 प्रमापीय अंकगणित n हम जानते हैं कि वे अगले भाग में कैसे चुने जाते हैं मान लीजिए कि α f के फलन का मूल है फिर हम वलय गणित पूर्णांक [α] बना सकते हैं 'Z'[α] से प्रमापीय अंकगणित अनुरूपता में Z/n'Z' तक एक अद्वितीय [[रिंग समरूपता|वलय समरूपता]] φ है जो α से m को सही करता है सरलता के लिए हम मान लेंगे कि 'Z'[α] एक अद्वितीय गुणनखण्ड कार्य क्षेत्र है जो प्रारूप को काम करने के लिए संशोधित किया जा सकता है जब यह नहीं होता है फिर भी कुछ अतिरिक्त जटिलताएँ होती हैं।
-अगला, हम दो समानांतर कारक आधार स्थापित करते हैं, एक 'Z' [α] में और एक 'Z' में। 'Z' [α] में से एक में 'Z' [α] में सभी प्रमुख आदर्श शामिल हैं, जिसका मानदंड एक चुने हुए मूल्य से घिरा है <math>N_{\max}</math>. जेड में कारक आधार, जैसा कि तर्कसंगत छलनी मामले में है, में सभी प्रमुख पूर्णांक होते हैं जो किसी अन्य सीमा तक होते हैं।
+हम दो समानांतर कारक आधार स्थापित करते हैं एक Z [α] में और एक Z [α] में से एक में 'Z' [α] में सभी प्रमुख आदर्श सम्मिलित हैं जिसका मानदंड एक चुने हुए मूल्य से घिरा है <math>N_{\max}</math>. जेड में कारक आधार जैसा कि तर्कसंगत छलनी के स्थान में है इसमें सभी प्रमुख पूर्णांक होते हैं जो किसी अन्य सीमा तक होते हैं
-इसके बाद हम पूर्णांकों के अपेक्षाकृत अभाज्य युग्मों (''a'',''b'') की खोज करते हैं जैसे कि:
+इसके बाद हम पूर्णांकों के अपेक्षाकृत अभाज्य युग्मों (''a'',''b'') की खोज करते हैं जैसे कि
-*''a''+''bm'' Z में कारक आधार के संबंध में [[चिकनी संख्या]] है (यानी, यह कारक आधार में तत्वों का उत्पाद है)।
+*''a''+''bm'' Z में कारक आधार के संबंध में [[चिकनी संख्या]] है यानी यह कारक आधार में तत्वों का उत्पाद है।
-*''a''+''bα'' Z[''α''] में कारक आधार के संबंध में चिकना है; यह देखते हुए कि हमने कारक आधार को कैसे चुना, यह ''a''+''bα'' के मानदंड के बराबर है जो केवल प्राइम्स से कम से विभाज्य है <math>N_{\max}</math>.
+*''a''+''bα'' Z[''α''] में कारक आधार के संबंध में चिकना है यह देखते हुए कि हमने कारक आधार को कैसे चुना यह ''a''+''bα'' के मानदंड के बराबर है जो केवल ऊंचाई से कम से विभाज्य है <math>N_{\max}</math>.
-ये जोड़े एक छलनी प्रक्रिया के माध्यम से पाए जाते हैं, [[एराटोस्थनीज की छलनी]] के अनुरूप; यह नाम संख्या क्षेत्र छलनी को प्रेरित करता है।
+ये जोड़े एक छलनी प्रक्रिया के माध्यम से पाए जाते हैं [[एराटोस्थनीज की छलनी]] के अनुरूप यह नाम संख्या क्षेत्र छलनी को प्रेरित करता है।
-ऐसी प्रत्येक जोड़ी के लिए, हम रिंग समरूपता φ को a+bα के गुणनखंड में लागू कर सकते हैं, और हम a+bm के गुणनखंडन के लिए 'Z' से 'Z'/n'Z' तक विहित वलय समरूपता लागू कर सकते हैं। इन्हें बराबर सेट करने से 'Z'/n'Z' में एक बड़े कारक आधार के तत्वों के बीच गुणक संबंध मिलता है, और यदि हमें पर्याप्त जोड़े मिलते हैं तो हम उपरोक्त वर्णित संबंधों और कारक n को जोड़ने के लिए आगे बढ़ सकते हैं।
+ऐसी प्रत्येक जोड़ी के लिए हम वलय समरूपता φ को a+bα के गुणनखंड में लागू कर सकते हैं और हम a+bm के गुणनखंडन के लिए Z से Z/n'Z' तक विहित वलय समरूपता लागू कर सकते हैं इन्हें बराबर समूह में करने से Z/n'Z' में एक बड़े कारक आधार के तत्वों के बीच गुणक संबंध मिलता है और यदि हमें पर्याप्त जोड़े मिलते हैं तो हम उपरोक्त वर्णित संबंधों और कारक n को जोड़ने के लिए आगे बढ़ सकते हैं।
 == मापदंडों का चुनाव ==
-एसएनएफएस के लिए प्रत्येक संख्या एक उपयुक्त विकल्प नहीं है: आपको पहले से उपयुक्त डिग्री के एक बहुपद एफ को जानना होगा (इष्टतम डिग्री होने का अनुमान लगाया गया है) <math>\left(3 \frac{\log N}{\log \log N}\right) ^\frac{1}{3}</math>, जो 4, 5, या 6 है N के आकार के लिए जो वर्तमान में कारक बनाने के लिए संभव है) छोटे गुणांक के साथ, और एक मान x ऐसा है कि <math>f(x) \equiv 0 \pmod N</math> जहाँ N वह संख्या है जिसका गुणनखंड किया जाना है। एक अतिरिक्त शर्त है: x को संतुष्ट होना चाहिए <math>ax+b \equiv 0 \pmod N</math> ए और बी से बड़ा नहीं <math>N^{1/d}</math>.
+एसएनएफएस के लिए प्रत्येक संख्या एक उपयुक्त विकल्प नहीं है तथा पहले से उपयुक्त डिग्री के एक बहुपद एफ को जानना होगा और इष्टतम डिग्री होने का अनुमान लगाया गया है <math>\left(3 \frac{\log N}{\log \log N}\right) ^\frac{1}{3}</math>जो 4, 5, या 6 N आकार के लिए जो वर्तमान में कारक बनाने के लिए संभव है तथा छोटे गुणांक के साथ और एक मान x ऐसा है कि <math>f(x) \equiv 0 \pmod N</math> जहाँ N वह संख्या है जिसका गुणनखंड किया जाना है एक अतिरिक्त शर्त है x को संतुष्ट होना चाहिए <math>ax+b \equiv 0 \pmod N</math> ए और बी से बड़ा नहीं <math>N^{1/d}</math>.
-संख्याओं का एक सेट जिसके लिए इस तरह के बहुपद मौजूद हैं <math>a^b \pm 1</math> कनिंघम परियोजना से संख्याएँ; उदाहरण के लिए, जब NFSNET ने फैक्टर किया {{tmath|1=3^{479}+1}}, उन्होंने बहुपद का प्रयोग किया {{tmath|1=x^6+3}} साथ {{tmath|1=x=3^{80} }}, तब से {{tmath|1=(3^{80})^6+3 = 3^{480}+3}}, और <math>3^{480}+3 \equiv 0 \pmod {3^{479}+1}</math>.
+संख्याओं का एक समूह जिसके लिए इस तरह के बहुपद हम एकत्र करते हैं <math>a^b \pm 1</math> कनिंघम परियोजना से संख्याएँ उदाहरण के लिए जब NFSNET ने गुणनखण्ड किया {{tmath|1=3^{479}+1}}, उन्होंने बहुपद का प्रयोग किया {{tmath|1=x^6+3}} साथ {{tmath|1=x=3^{80} }}, तब से {{tmath|1=(3^{80})^6+3 = 3^{480}+3}}, और <math>3^{480}+3 \equiv 0 \pmod {3^{479}+1}</math>.
-रेखीय पुनरावृत्ति द्वारा परिभाषित संख्याएँ, जैसे कि [[फाइबोनैचि संख्या]] और [[लुकास संख्या]] संख्याएँ, में भी SNFS बहुपद होते हैं, लेकिन इनका निर्माण करना थोड़ा अधिक कठिन होता है। उदाहरण के लिए, <math>F_{709}</math> बहुपद है <math>n^5 + 10n^3 + 10n^2 + 10n + 3</math>, और x का मान संतुष्ट करता है <math>F_{142} x - F_{141} = 0</math>.<ref>{{cite web
+रेखीय पुनरावृत्ति द्वारा परिभाषित संख्याएँ जैसे कि [[फाइबोनैचि संख्या]] और [[लुकास संख्या]] संख्याएँ भी SNFS बहुपद होते हैं लेकिन इनका निर्माण करना थोड़ा अधिक कठिन होता है उदाहरण के लिए <math>F_{709}</math> बहुपद है <math>n^5 + 10n^3 + 10n^2 + 10n + 3</math>, और x का मान संतुष्ट करता है <math>F_{142} x - F_{141} = 0</math>.<ref>{{cite web
    | last = Franke
    | first = Jens
    | title = Installation notes for ggnfs-lasieve4
    | url=http://stuff.mit.edu/afs/sipb/project/pari-gp/ggnfs/Linux/src/lasieve4/INSTALL.and.USE
-   | publisher =[[MIT]] Massachusetts Institute of Technology}}</ref>
+   | publisher =[[MIT]] Massachusetts Institute of Technology}}</ref>यदि आप पहले से ही एक बड़ी SNFS-संख्या के कुछ कारकों को जानते हैं तो आप शेष भाग में SNFS गणना कर सकते हैं उपरोक्त NFSNET उदाहरण के लिए{{tmath|1=3^{479}+1 = (4 \times 158071 \times 7167757 \times 7759574882776161031)}} 197 अंकों की समग्र संख्या छोटे कारकों को [[अण्डाकार वक्र विधि]] द्वारा हटा दिया गया था का गुना और SNFS को 197 अंकों की संख्या के रूप में प्रदर्शित किया गया था एसएनएफएस द्वारा आवश्यक संबंधों की संख्या अभी भी बड़ी संख्या के आकार पर निर्भर करती है लेकिन अलग-अलग गणनाएं छोटी संख्या के त्वरित रूप में होती हैं।
-यदि आप पहले से ही एक बड़ी SNFS-संख्या के कुछ कारकों को जानते हैं, तो आप शेष भाग में SNFS गणना मॉड्यूलो कर सकते हैं; उपरोक्त NFSNET उदाहरण के लिए, {{tmath|1=3^{479}+1 = (4 \times 158071 \times 7167757 \times 7759574882776161031)}} 197 अंकों की समग्र संख्या (छोटे कारकों को [[अण्डाकार वक्र विधि]] द्वारा हटा दिया गया था) का गुना, और SNFS को 197 अंकों की संख्या के रूप में प्रदर्शित किया गया था। एसएनएफएस द्वारा आवश्यक संबंधों की संख्या अभी भी बड़ी संख्या के आकार पर निर्भर करती है, लेकिन अलग-अलग गणनाएं छोटी संख्या के त्वरित रूप से होती हैं।
 == एल्गोरिथम की सीमाएं ==
-यह एल्गोरिथम, जैसा कि ऊपर बताया गया है, फॉर्म आर की संख्याओं के लिए बहुत कुशल है<sup>e</sup>±s, r और s के लिए अपेक्षाकृत छोटा है। यह किसी भी पूर्णांक के लिए भी कुशल है जिसे छोटे गुणांक वाले बहुपद के रूप में दर्शाया जा सकता है। इसमें अधिक सामान्य रूप ar के पूर्णांक शामिल हैं<sup>और</sup>±बीएस<sup>f</sup>, और कई पूर्णांकों के लिए भी जिनके बाइनरी प्रतिनिधित्व में हैमिंग वजन कम है। इसका कारण इस प्रकार है: संख्या क्षेत्र छलनी दो अलग-अलग क्षेत्रों में छानने का काम करती है।
+यह एक कलन विधि है जैसा कि ऊपर बताया गया है कि फॉर्म आर की संख्याओं के लिए बहुत कुशल है<sup>e</sup>±s, r और s के लिए अपेक्षाकृत छोटा है यह किसी भी पूर्णांक के लिए कुशल है जिसे छोटे गुणांक वाले बहुपद के रूप में दर्शाया जा सकता है इसमें अधिक सामान्य रूप ar के पूर्णांक सम्मिलित हैं<sup>और</sup>±बीएस<sup>f</sup> और कई पूर्णांकों के लिए भी जिनके बाइनरी प्रतिनिधित्व में वजन कम है इसका कारण यह है कि संख्या क्षेत्र छलनी दो अलग-अलग क्षेत्रों में छानने का काम करती है पहला क्षेत्र आमतौर पर तर्कसंगत है दूसरा एक उच्च डिग्री क्षेत्र है तथा कलन विधि की दक्षता दृढ़ता से इन क्षेत्रों में कुछ तत्वों के मानदंडों पर निर्भर करती है जब एक पूर्णांक को छोटे गुणांक वाले बहुपद के रूप में दर्शाया जा सकता है, तो उत्पन्न होने वाले मानदंड उन लोगों की तुलना में बहुत छोटे होते हैं, जब एक पूर्णांक को एक सामान्य बहुपद द्वारा दर्शाया जाता है तो  इसका कारण यह होता है कि एक सामान्य बहुपद के बहुत बड़े गुणांक होंगे और मानदंड तदनुसार बड़े होंगे कलन विधि इन मानदंडों को अभाज्य संख्याओं के एक निश्चित समूह पर कारक बनाने का प्रयास करता है जब मानदंड छोटे होते हैं तो इन नंबरों के कारक होने की अधिक संभावना है।
-पहला क्षेत्र आमतौर पर तर्कसंगत है। दूसरा एक उच्च डिग्री क्षेत्र है। एल्गोरिथम की दक्षता दृढ़ता से इन क्षेत्रों में कुछ तत्वों के मानदंडों पर निर्भर करती है। जब एक पूर्णांक को छोटे गुणांक वाले बहुपद के रूप में दर्शाया जा सकता है, तो उत्पन्न होने वाले मानदंड उन लोगों की तुलना में बहुत छोटे होते हैं, जब एक पूर्णांक को एक सामान्य बहुपद द्वारा दर्शाया जाता है। इसका कारण यह है कि एक सामान्य बहुपद के बहुत बड़े गुणांक होंगे, और मानदंड तदनुसार बड़े होंगे। एल्गोरिथ्म इन मानदंडों को अभाज्य संख्याओं के एक निश्चित सेट पर कारक बनाने का प्रयास करता है। जब
-मानदंड छोटे हैं, इन नंबरों के कारक होने की अधिक संभावना है।
 == यह भी देखें ==
-* सामान्य संख्या क्षेत्र छलनी
+* सामान्य संख्या क्षेत्र छलनी।
 == संदर्भ ==
@@ Line 66: / Line 63: @@
 *{{citation |last=Silverman |first=Robert D.  |title=Optimal Parameterization of SNFS |journal= Journal of Mathematical Cryptology|volume=1 |issue=2  |year=2007 |pages= 105–124 |doi=10.1515/JMC.2007.007|citeseerx=10.1.1.12.2975  |s2cid=16236028 }}
-{{number theoretic algorithms}}[[Category: पूर्णांक कारककरण एल्गोरिदम]]
+{{number theoretic algorithms}}
+[[Category:Collapse templates]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 08/06/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with script errors]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Translated in Hindi]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:पूर्णांक कारककरण एल्गोरिदम]]

v t e संख्या-सिद्धांत एल्गोरिथ्म
प्राइमैलिटी टेस्ट	AKS अप्रैल BAILLIE -PSW अण्डाकार वक्र पॉकलिंगटन Fermat लुकास लुकास -लेहमेर लुकास -लेहमेर -रेज़ल ' प्रोथ का प्रमेय पेपिन का द्विघात फ्रोबेनियस सोलोवे -स्ट्रासेन मिलर -रबिन
प्राइम-जनरेटिंग	एटकिन की छलनी एरातोस्टेनेस की छलनी प्रिचर्ड की छलनी सुंदरम की छलनी पहिया कारक
पूर्णांक कारक	निरंतर अंश कारक। निरंतर अंश (CFRAC) डिक्सन Lenstra अण्डाकार-वक्र कारक Euler's पोलार्ड्स आरएचओ P - 1 पी + 1 द्विघात छलनी (क्यूएस) सामान्य संख्या क्षेत्र छलनी (GNFS) विशेष संख्या क्षेत्र छलनी (SNFS) तर्कसंगत छलनी फर्माट शैंक्स स्क्वायर फॉर्म ट्रायल डिवीजन शोर
गुणा	प्राचीन मिस्र लंबा करत्सुबा टूम - कुक Schönhage - Strassen Für's
Euclidean डिवीजन	बाइनरी चंकिंग फूरियर Goldschmidt न्यूटन-रफसन लंबा छोटा SRT
असतत लघुगणक	बेबी-स्टेप विशाल-चरण पोलार्ड रो पोलार्ड कंगारू Pohlig -Hellman इंडेक्स कैलकुलस फ़ंक्शन फ़ील्ड छलनी
महत्तम सामान्य भाजक	बाइनरी Euclidean विस्तारित यूक्लिडियन लेहमर
मॉड्यूलर वर्गमूल	Cipolla पॉकलिंगटन तनेली -शंक Berlekamp कुनरथ
अन्य एल्गोरिदम	चक्रवाला कॉर्नचिया वर्ग द्वारा घातक पूर्णांक वर्गमूल पूर्णांक संबंध मॉड्यूलर घातांक मोंटगोमरी में कमी शूफ़ ट्रेचेनबर्ग सिस्टम
इटैलिक इंगित करता है कि एल्गोरिथ्म विशेष रूपों की संख्या के लिए है

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 10:10, 1 July 2023

Contents

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

विधि का विवरण

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

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

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 10:10, 1 July 2023

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

विधि का विवरण

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

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

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories