तर्कसंगत छलनी: Difference between revisions

Latest revision as of 11:29, 23 June 2023

गणित में तर्कसंगत सीव पूर्णांकों को प्रमुख कारकों में विभाजित करने के लिए एक सामान्य एल्गोरिथ्म है। यह सामान्य संख्या क्षेत्र सीव का एक विशेष स्थिति है। जबकि यह सामान्य एल्गोरिथम की तुलना में कम कुशल है, यह वैचारिक रूप से सरल है। यह समझने में सहायक है जो की पहले कदम के रूप में कार्य करता है कि सामान्य संख्या क्षेत्र सीव कैसे काम करती है।

विधि

मान लीजिए कि हम समग्र संख्या n को गुणनखंडित करने का प्रयास कर रहे हैं। हम एक बाध्य B चुनते हैं और कारक आधार की पहचान करते हैं (जिसे हम P कहते हैं) B से कम या उसके समान सभी प्राइम्स का सेट है इसके पश्चात हम सकारात्मक पूर्णांक z की खोज करते हैं जैसे कि z और z+n दोनों B-स्मूथ हैं - अथार्त उनके सभी प्रमुख गुणनखंड P में हैं। इसलिए हम उपयुक्त घातांक $a_{i}$ के लिए लिख सकते हैं।

$z=\prod _{p_{i}\in P}p_{i}^{a_{i}}$

और इसी तरह उपयुक्त $b_{i}$ के लिए हमारे पास है

$z+n=\prod _{p_{i}\in P}p_{i}^{b_{i}}$ .

किंतु $z$ और $z+n$ सर्वांगसम सापेक्ष $n$ हैं, और इसलिए प्रत्येक ऐसा पूर्णांक z जो हमें P के तत्वों के बीच गुणक संबंध (मॉड n) देता है, अर्थात

\prod _{p_{i}\in P}p_{i}^{a_{i}}\equiv \prod _{p_{i}\in P}p_{i}^{b_{i}}{\pmod {n}}

(जहां a_i और b_i अऋणात्मक पूर्णांक हैं।)

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

उदाहरण

हम तर्कसंगत सीव का उपयोग करके पूर्णांक n = 187 का गुणनखंड करेंगे। जिस प्रकार हम कारक आधार P = {2,3,5,7} देते हुए इच्छानुसार रूप से मान B = 7 का प्रयास करते है जिसका पहला कदम P के प्रत्येक सदस्य द्वारा विभाज्यता के लिए n का परीक्षण करना है; जिसमे स्पष्ट रूप से यदि n इनमें से किसी एक अभाज्य संख्या से विभाज्य है तो हम पहले ही समाप्त कर चुके हैं। चूँकि 187, 2, 3, 5, या 7 से विभाज्य नहीं है। अगला हम z के उपयुक्त मानों की खोज करते हैं; पहले कुछ 2, 5, 9 और 56 हैं। z के चार उपयुक्त मान चार गुणात्मक संबंध देते हैं (मॉड 187)

2^{1}3^{0}5^{0}7^{0}=2\equiv 189=2^{0}3^{3}5^{0}7^{1}

(1)

2^{0}3^{0}5^{1}7^{0}=5\equiv 192=2^{6}3^{1}5^{0}7^{0}

(2)

2^{0}3^{2}5^{0}7^{0}=9\equiv 196=2^{2}3^{0}5^{0}7^{2}

(3)

2^{3}3^{0}5^{0}7^{1}=56\equiv 243=2^{0}3^{5}5^{0}7^{0}

(4)

इन्हें संयोजित करने और सम घातांकों के साथ समाप्त करने के लिए अब कई अनिवार्य रूप से भिन्न विधियाँ हैं। उदाहरण के लिए,

(1)×(4): इन्हें गुणा करने और 7 के सामान्य कारक को समाप्त करने के पश्चात् (जो हम 7 के बाद से कर सकते हैं, P के सदस्य होने के नाते, पहले से ही n^[1] के साथ कोप्राइम होने के लिए निर्धारित किया गया है), यह कम हो जाता है 2⁴ ≡ 3⁸ (मॉड n), या 4² ≡ 81² (मॉड n)। परिणामी गुणनखंड 187 = gcd(81-4,187) × gcd(81+4,187) = 11×17 है

वैकल्पिक रूप से, समीकरण (3) पहले से ही उचित रूप में है:

(3): यह 3² ≡ 14² (मॉड n) कहता है, जो गुणनखंड 187 = gcd(14-3,187) × gcd(14+3,187) = 11×17 देता है।

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

परिमेय सीव सामान्य संख्या क्षेत्र सीव की तरह, संख्या को p^m के रूप में गुणनखंडित नहीं कर सकती है, जहाँ p एक अभाज्य संख्या है और m एक पूर्णांक है। यह कोई बड़ी समस्या नहीं है, चूँकि —ऐसी संख्याएं सांख्यिकीय रूप से दुर्लभ हैं और इसके अतिरिक्त यह जांचने की एक सरल और तेज प्रक्रिया है कि दी गई संख्या इस रूप की है या नहीं। संभवतः सबसे सुंदर विधि यह जांचना है कि क्या $\lfloor n^{1/b}\rfloor ^{b}=n$ जड़ निष्कर्षण के लिए न्यूटन की विधि के पूर्णांक संस्करण का उपयोग करके किसी भी 1 < b < log(n) के लिए मान्य है या नहीं है ^[2].

सबसे बड़ी समस्या पर्याप्त संख्या में z का पता लगाना है जैसे कि z और z+n दोनों B-स्मूथ हैं। किसी दिए गए बी के लिए, B-स्मूथ संख्याओं का अनुपात संख्या के आकार के साथ तेजी से घटता है। इसलिए यदि n बड़ा है (कहते हैं, सौ अंक), एल्गोरिथम के काम करने के लिए पर्याप्त z खोजना कठिन या असंभव होगा। सामान्य संख्या क्षेत्र सीव का लाभ यह है कि किसी को क्रम n^1/d की स्मूथ संख्याओं की खोज करने की आवश्यकता होती है जो कुछ धनात्मक पूर्णांक d (सामान्यतः 3 या 5) के लिए, न कि क्रम n के लिए जैसा कि यहाँ आवश्यक है।

संदर्भ

A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The Factorization of the Ninth Fermat Number, Math. Comp. 61 (1993), 319-349. Available at [2].
A. K. Lenstra, H. W. Lenstra, Jr. (eds.) The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554, Springer-Verlag, New York, 1993.

फुटनोट्स

↑ Note that common factors cannot in general be canceled in a congruence, but they can in this case, since the primes of the factor base are all required to be coprime to n, as mentioned above. See modular multiplicative inverse.
↑ R. Crandall and J. Papadopoulos, On the implementation of AKS-class primality tests, available at [1]

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

[1] Note that common factors cannot in general be canceled in a congruence, but they can in this case, since the primes of the factor base are all required to be coprime to n, as mentioned above. See modular multiplicative inverse.

[2] R. Crandall and J. Papadopoulos, On the implementation of AKS-class primality tests, available at [1]

[1]

[2]

@@ Line 1: / Line 1: @@
 गणित में तर्कसंगत सीव पूर्णांकों को प्रमुख कारकों में विभाजित करने के लिए एक सामान्य एल्गोरिथ्म है। यह सामान्य संख्या क्षेत्र सीव का एक विशेष स्थिति है। जबकि यह सामान्य एल्गोरिथम की तुलना में कम कुशल है, यह वैचारिक रूप से सरल है। यह समझने में सहायक है जो की पहले कदम के रूप में कार्य करता है कि सामान्य संख्या क्षेत्र सीव कैसे काम करती है।
@@ Line 14: / Line 12: @@
 <math>z+n=\prod_{p_i\in P} p_i^{b_i}</math>.
-किंतु <math>z</math> और <math>z+n</math> सर्वांगसम सापेक्ष <math>n</math> हैं, और इसलिए प्रत्येक ऐसा पूर्णांक z जो हमें P के तत्वों के बीच गुणक संबंध (mod n) देता है, अर्थात
+किंतु <math>z</math> और <math>z+n</math> सर्वांगसम सापेक्ष <math>n</math> हैं, और इसलिए प्रत्येक ऐसा पूर्णांक z जो हमें P के तत्वों के बीच गुणक संबंध (मॉड n) देता है, अर्थात
 :<math>\prod_{p_i\in P} p_i^{a_i} \equiv \prod_{p_i\in P} p_i^{b_i} \pmod n</math>
 (जहां ''a<sub>i</sub>''  और ''b<sub>i</sub>'' अऋणात्मक पूर्णांक हैं।)
-जब हमने इन संबंधों को पर्याप्त रूप से उत्पन्न कर लिया है (यह सामान्यतः पर्याप्त है कि संबंधों की संख्या P के आकार से कुछ अधिक हो) तो हम इन विभिन्न संबंधों को एक साथ गुणा करने के लिए रैखिक बीजगणित के विधियों का उपयोग कर सकते हैं जिससे के घातांक अभाज्य सभी सम हैं। यह हमें  a<sup>2</sup>≡b<sup>2</sup> (mod ''n''), के रूप के वर्गों की सर्वांगसमता देगा जिसे ''n'' = gcd(''a''-''b'',''n'')×gcd(''a''+''b'',''n'') के गुणनखंड में बदला जा सकता है। यह गुणनखंड तुच्छ हो सकता है (अथार्त n=n×1) जिस स्थिति में हमें संबंधों के एक अलग संयोजन के साथ फिर से प्रयास करना होगा; किंतु भाग्य से हमें n के कारकों की एक गैर-तुच्छ जोड़ी मिलेगी और एल्गोरिथ्म समाप्त हो जाएगा।
+जब हमने इन संबंधों को पर्याप्त रूप से उत्पन्न कर लिया है (यह सामान्यतः पर्याप्त है कि संबंधों की संख्या P के आकार से कुछ अधिक हो) तो हम इन विभिन्न संबंधों को एक साथ गुणा करने के लिए रैखिक बीजगणित के विधियों का उपयोग कर सकते हैं जिससे के घातांक अभाज्य सभी सम हैं। यह हमें  a<sup>2</sup>≡b<sup>2</sup> (मॉड ''n''), के रूप के वर्गों की सर्वांगसमता देगा जिसे ''n'' = gcd(''a''-''b'',''n'')×gcd(''a''+''b'',''n'') के गुणनखंड में बदला जा सकता है। यह गुणनखंड तुच्छ हो सकता है (अथार्त n=n×1) जिस स्थिति में हमें संबंधों के एक अलग संयोजन के साथ फिर से प्रयास करना होगा; किंतु भाग्य से हमें n के कारकों की एक गैर-तुच्छ जोड़ी मिलेगी और एल्गोरिथ्म समाप्त हो जाएगा।
+== उदाहरण                                                                                           ==
-'''सकते हैं जिससे के घातांक अभाज्य सभी सम हैं। यह हमें  a<sup>2</sup>≡b<sup>2</sup> (mod ''n''), के रूप के वर्गों की सर्वांगसमता देगा जिसे ''n'' = gcd(''a''-''b'',''n'')×gcd(''a''+''b'',''n'') के गुणनखंड में बदला जा सकता है। यह गुणनखंड तुच्छ हो सकता है (अथार्त n=n×1) जिस स्थिति में हमें संबंधों के एक अलग संयोजन के साथ फिर से प्रयास करना होगा;'''
-== उदाहरण                         ==
+हम तर्कसंगत सीव का उपयोग करके पूर्णांक n = 187 का गुणनखंड करेंगे। जिस प्रकार हम कारक आधार P = {2,3,5,7} देते हुए इच्छानुसार रूप से मान B = 7 का प्रयास करते है जिसका पहला कदम ''P'' के प्रत्येक सदस्य द्वारा विभाज्यता के लिए ''n'' का परीक्षण करना है; जिसमे स्पष्ट रूप से यदि n इनमें से किसी एक अभाज्य संख्या से विभाज्य है तो हम पहले ही समाप्त कर चुके हैं। चूँकि 187, 2, 3, 5, या 7 से विभाज्य नहीं है। अगला हम z के उपयुक्त मानों की खोज करते हैं; पहले कुछ 2, 5, 9 और 56 हैं। z के चार उपयुक्त मान चार गुणात्मक संबंध देते हैं (मॉड 187)
-हम तर्कसंगत सीव का उपयोग करके पूर्णांक n = 187 का गुणनखंड करेंगे। जिस प्रकार हम कारक आधार P = {2,3,5,7} देते हुए इच्छानुसार रूप से मान B = 7 का प्रयास करते है जिसका पहला कदम ''P'' के प्रत्येक सदस्य द्वारा विभाज्यता के लिए ''n'' का परीक्षण करना है; जिसमे स्पष्ट रूप से यदि n इनमें से किसी एक अभाज्य संख्या से विभाज्य है तो हम पहले ही समाप्त कर चुके हैं। चूँकि 187, 2, 3, 5, या 7 से विभाज्य नहीं है। अगला हम z के उपयुक्त मानों की खोज करते हैं; पहले कुछ 2, 5, 9 और 56 हैं। z के चार उपयुक्त मान चार गुणात्मक संबंध देते हैं (mod 187)
 :
@@ Line 63: / Line 57: @@
 श्रेणी:पूर्णांक गुणनखंड एल्गोरिथम
+[[Category:Collapse templates|Rational Sieve]]
-[[Category: Machine Translated Page]]
+[[Category:Created On 08/06/2023|Rational Sieve]]
-[[Category:Created On 08/06/2023]]
+[[Category:Machine Translated Page|Rational Sieve]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Rational Sieve]]
+[[Category:Pages with script errors|Rational Sieve]]
+[[Category:Sidebars with styles needing conversion|Rational Sieve]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Translated in Hindi|Rational Sieve]]
+[[Category:Templates Vigyan Ready|Rational Sieve]]
+[[Category:Templates generating microformats|Rational Sieve]]
+[[Category:Templates that are not mobile friendly|Rational Sieve]]
+[[Category:Templates using TemplateData|Rational Sieve]]
+[[Category:Wikipedia metatemplates|Rational Sieve]]

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 11:29, 23 June 2023

Contents

विधि

उदाहरण

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

संदर्भ

फुटनोट्स

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

तर्कसंगत छलनी: Difference between revisions

Latest revision as of 11:29, 23 June 2023

विधि

उदाहरण

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

संदर्भ

फुटनोट्स

Navigation

Wiki tools

Page tools

Other projects

Hidden categories