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

Revision as of 09:26, 20 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 के तत्वों के बीच गुणक संबंध (mod 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² (mod 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 के चार उपयुक्त मान चार गुणात्मक संबंध देते हैं (mod 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}

@@ Line 1: / Line 1: @@
-गणित में, तर्कसंगत छलनी [[पूर्णांक गुणनखंडन]] के लिए एक सामान्य [[ कलन विधि ]] है। यह [[सामान्य संख्या क्षेत्र छलनी]] का एक विशेष मामला है। जबकि यह सामान्य एल्गोरिथम की तुलना में कम [[एल्गोरिथम दक्षता]] है, यह वैचारिक रूप से सरल है। यह समझने में मददगार पहले कदम के रूप में कार्य करता है कि सामान्य संख्या फ़ील्ड छलनी कैसे काम करती है।
+गणित में तर्कसंगत सीव पूर्णांकों को प्रमुख कारकों में विभाजित करने के लिए एक सामान्य एल्गोरिथ्म है। यह सामान्य संख्या क्षेत्र सीव का एक विशेष स्थिति है। जबकि यह सामान्य एल्गोरिथम की तुलना में कम कुशल है, यह वैचारिक रूप से सरल है। यह समझने में सहायक है जो की पहले कदम के रूप में कार्य करता है कि सामान्य संख्या क्षेत्र सीव कैसे काम करती है।
 == विधि ==
-मान लीजिए कि हम [[समग्र संख्या]] n को गुणनखंडित करने का प्रयास कर रहे हैं। हम एक बाध्य बी चुनते हैं, और [[कारक आधार]] (जिसे हम पी कहते हैं) की पहचान करते हैं, बी से कम या उसके बराबर सभी प्राइम्स का सेट। अगला, हम सकारात्मक पूर्णांक जेड की खोज करते हैं जैसे कि जेड और जेड + एन दोनों बी हैं- [[चिकनी संख्या]] - यानी उनके सभी प्रमुख गुणनखंड P में हैं। इसलिए हम उपयुक्त घातांक के लिए लिख सकते हैं <math>a_i</math>,
+मान लीजिए कि हम समग्र संख्या n को गुणनखंडित करने का प्रयास कर रहे हैं। हम एक बाध्य ''B'' चुनते हैं, और कारक आधार की पहचान करते हैं (जिसे हम ''P'' कहते हैं) ''B'' से कम या उसके समान सभी प्राइम्स का सेट है  इसके पश्चात हम सकारात्मक पूर्णांक ''z''  की खोज करते हैं जैसे कि ''z'' और  ''z+n''  दोनों ''B''-स्मूथ हैं - अथार्त उनके सभी प्रमुख गुणनखंड P में हैं। इसलिए हम उपयुक्त घातांक <math>a_i</math> के लिए लिख सकते हैं।
 <math>z=\prod_{p_i\in P} p_i^{a_i}</math>
-और इसी तरह, उपयुक्त के लिए <math>b_i</math>, अपने पास
+और इसी तरह उपयुक्त <math>b_i</math> के लिए हमारे पास है
 <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 के तत्वों के बीच गुणक संबंध (mod n) देता है, अर्थात
 :<math>\prod_{p_i\in P} p_i^{a_i} \equiv \prod_{p_i\in P} p_i^{b_i} \pmod n</math>
-(जहां ए<sub>i</sub>और बी<sub>i</sub>अऋणात्मक पूर्णांक हैं।)
+(जहां ''a<sub>i</sub>''  और ''b<sub>i</sub>'' अऋणात्मक पूर्णांक हैं।)
-जब हमने इन संबंधों को पर्याप्त रूप से उत्पन्न कर लिया है (आमतौर पर यह पर्याप्त है कि संबंधों की संख्या P के आकार से कुछ अधिक हो), तो हम इन विभिन्न संबंधों को एक साथ गुणा करने के लिए रैखिक बीजगणित के तरीकों का उपयोग कर सकते हैं ताकि के घातांक अभाज्य संख्याएँ सभी सम हैं। यह हमें a के रूप के वर्गों की सर्वांगसमता देगा<sup>2</sup>≡बी<sup>2</sup> (mod n), जिसे n = [[महत्तम सामान्य भाजक]](a-b,n)×gcd(a+b,n) के गुणनखंड में बदला जा सकता है। यह गुणनखंड तुच्छ हो सकता है (यानी n=n×1), इस मामले में हमें संबंधों के एक अलग संयोजन के साथ फिर से प्रयास करना होगा; लेकिन भाग्य से हमें n के कारकों की एक गैर-तुच्छ जोड़ी मिलेगी, और एल्गोरिथ्म समाप्त हो जाएगा।
+जब हमने इन संबंधों को पर्याप्त रूप से उत्पन्न कर लिया है (यह आम तौर पर पर्याप्त है कि संबंधों की संख्या P के आकार से कुछ अधिक हो) तो हम इन विभिन्न संबंधों को एक साथ गुणा करने के लिए रैखिक बीजगणित के विधियों का उपयोग कर सकते हैं जिससे के घातांक अभाज्य सभी सम हैं। यह हमें  a<sup>2</sup>≡b<sup>2</sup> (mod ''n''), के रूप के वर्गों की सर्वांगसमता देगा जिसे ''n'' = gcd(''a''-''b'',''n'')×gcd(''a''+''b'',''n'') के गुणनखंड में बदला जा सकता है। यह गुणनखंड तुच्छ हो सकता है (अथार्त n=n×1) जिस स्थिति में हमें संबंधों के एक अलग संयोजन के साथ फिर से प्रयास करना होगा; किंतु भाग्य से हमें n के कारकों की एक गैर-तुच्छ जोड़ी मिलेगी और एल्गोरिथ्म समाप्त हो जाएगा।
 == उदाहरण ==
-हम तर्कसंगत छलनी का उपयोग करके पूर्णांक n = 187 का गुणनखंड करेंगे। हम कारक आधार P = {2,3,5,7} देते हुए मनमाने ढंग से मान B = 7 का प्रयास करेंगे। पहला कदम पी के प्रत्येक सदस्य द्वारा विभाज्यता के लिए एन का परीक्षण करना है; स्पष्ट रूप से यदि n इनमें से किसी एक अभाज्य संख्या से विभाज्य है, तो हम पहले ही समाप्त कर चुके हैं। हालाँकि, 187, 2, 3, 5, या 7 से विभाज्य नहीं है। अगला, हम z के उपयुक्त मानों की खोज करते हैं; पहले कुछ 2, 5, 9 और 56 हैं। z के चार उपयुक्त मान चार गुणात्मक संबंध देते हैं (mod 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)
+:
 {{NumBlk|:|<math>2^1 3^0 5^0 7^0  = 2 \equiv 189 = 2^0 3^3 5^0 7^1</math>|{{EquationRef|1}}}}
 {{NumBlk|:|<math>2^0 3^0 5^1 7^0  = 5 \equiv 192 = 2^6 3^1 5^0 7^0</math>|{{EquationRef|2}}}}
@@ Line 26: / Line 31: @@
 {{NumBlk|:|<math>2^3 3^0 5^0 7^1  = 56 \equiv 243 = 2^0 3^5 5^0 7^0</math>|{{EquationRef|4}}}}
-इन्हें संयोजित करने और सम घातांकों के साथ समाप्त करने के लिए अब कई अनिवार्य रूप से भिन्न तरीके हैं। उदाहरण के लिए,
+इन्हें संयोजित करने और सम घातांकों के साथ समाप्त करने के लिए अब कई अनिवार्य रूप से भिन्न विधियाँ हैं। उदाहरण के लिए,
-*({{EquationNote|1}})×({{EquationNote|4}}): इन्हें गुणा करने और 7 के सामान्य कारक को रद्द करने के बाद (जो हम 7 के बाद से कर सकते हैं, P का सदस्य होने के नाते, पहले से ही n के साथ सहअभाज्य होना निर्धारित किया गया है<ref>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]].</ref>), यह घटकर 2 हो जाता है<sup>4</sup> ≡ 3<sup>8</sup> (मॉड एन), या 4<sup>2</sup> ≡ 81<sup>2</sup> (मॉड एन)। परिणामी गुणनखंड 187 = gcd(81-4,187) × gcd(81+4,187) = 11×17 है।
+*({{EquationNote|1}})×({{EquationNote|4}}): इन्हें गुणा करने और 7 के सामान्य कारक को समाप्त करने के पश्चात् (जो हम 7 के बाद से कर सकते हैं, ''P'' के सदस्य होने के नाते, पहले से ही ''n''<ref>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]].</ref> के साथ कोप्राइम होने के लिए निर्धारित किया गया है), यह कम हो जाता है  2<sup>4</sup> ≡ 3<sup>8</sup>  (मॉड ''n''), या 4<sup>2</sup> ≡ 81<sup>2</sup> (मॉड ''n'')। परिणामी गुणनखंड 187 = gcd(81-4,187) × gcd(81+4,187) = 11×17 है
 वैकल्पिक रूप से, समीकरण ({{EquationNote|3}}) पहले से ही उचित रूप में है:
-*({{EquationNote|3}}): यह कहता है 3<sup>2</sup> ≡ 14<sup>2</sup> (mod n), जो गुणनखंड 187 = gcd(14-3,187) × gcd(14+3,187) = 11×17 देता है।
+*({{EquationNote|3}}): यह 3<sup>2</sup> ≡ 14<sup>2</sup>  (मॉड ''n'') कहता है, जो गुणनखंड 187 = gcd(14-3,187) × gcd(14+3,187) = 11×17 देता है।
 == एल्गोरिदम की सीमाएं ==
-परिमेय छलनी, सामान्य संख्या क्षेत्र छलनी की तरह, p के रूप की संख्याओं का गुणनखण्ड नहीं कर सकती<sup>m</sup>, जहाँ p एक अभाज्य संख्या है और m एक पूर्णांक है। यह कोई बड़ी समस्या नहीं है, हालांकि—ऐसी संख्याएं सांख्यिकीय रूप से दुर्लभ हैं, और इसके अलावा यह जांचने की एक सरल और तेज प्रक्रिया है कि दी गई संख्या इस रूप की है या नहीं। शायद सबसे सुरुचिपूर्ण तरीका यह जांचना है कि क्या <math>\lfloor n^{ 1/b }\rfloor^b=n</math> रूट निष्कर्षण के लिए न्यूटन की विधि के पूर्णांक संस्करण का उपयोग करके किसी भी 1 <बी <लॉग (एन) के लिए धारण करता है।<ref>R. Crandall and J. Papadopoulos, ''On the implementation of AKS-class primality tests,'' available at [https://www.apple.com/acg/pdf/aks3.pdf]</ref>
+परिमेय सीव सामान्य संख्या क्षेत्र सीव  की तरह, संख्या को ''p<sup>m</sup>'' के रूप में गुणनखंडित नहीं कर सकती है, जहाँ p एक अभाज्य संख्या है और m एक पूर्णांक है। यह कोई बड़ी समस्या नहीं है, चूँकि —ऐसी संख्याएं सांख्यिकीय रूप से दुर्लभ हैं और इसके अतिरिक्त  यह जांचने की एक सरल और तेज प्रक्रिया है कि दी गई संख्या इस रूप की है या नहीं। संभवतः सबसे सुंदर विधि यह जांचना है कि क्या <math>\lfloor n^{ 1/b }\rfloor^b=n</math> जड़ निष्कर्षण के लिए न्यूटन की विधि के पूर्णांक संस्करण का उपयोग करके किसी भी 1 < b < log(n) के लिए मान्य है या नहीं है <ref>R. Crandall and J. Papadopoulos, ''On the implementation of AKS-class primality tests,'' available at [https://www.apple.com/acg/pdf/aks3.pdf]</ref>.
-सबसे बड़ी समस्या पर्याप्त संख्या में z का पता लगाना है जैसे कि z और z+n दोनों B-चिकनी हैं। किसी दिए गए बी के लिए, बी-चिकनी संख्याओं का अनुपात संख्या के आकार के साथ तेजी से घटता है। इसलिए यदि n बड़ा है (कहते हैं, सौ अंक), एल्गोरिथम के काम करने के लिए पर्याप्त z खोजना मुश्किल या असंभव होगा। सामान्य संख्या फ़ील्ड छलनी का लाभ यह है कि किसी को ऑर्डर एन की चिकनी संख्याओं की खोज करने की आवश्यकता होती है<sup>1/d</sup> कुछ धनात्मक पूर्णांक d (आमतौर पर 3 या 5) के लिए, न कि क्रम n के लिए जैसा कि यहाँ आवश्यक है।
+सबसे बड़ी समस्या पर्याप्त संख्या में z का पता लगाना है जैसे कि z और z+n दोनों B-स्मूथ हैं। किसी दिए गए बी के लिए,  ''B''-स्मूथ संख्याओं का अनुपात संख्या के आकार के साथ तेजी से घटता है। इसलिए यदि n बड़ा है (कहते हैं, सौ अंक), एल्गोरिथम के काम करने के लिए पर्याप्त z खोजना कठिन या असंभव होगा। सामान्य संख्या क्षेत्र सीव का लाभ यह है कि किसी को  क्रम ''n''<sup>1/''d''</sup> की स्मूथ संख्याओं की खोज करने की आवश्यकता होती है जो कुछ धनात्मक पूर्णांक d (सामान्यतः 3 या 5) के लिए, न कि क्रम n के लिए जैसा कि यहाँ आवश्यक है।
 == संदर्भ ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 09:26, 20 June 2023

Contents

विधि

उदाहरण