तर्कसंगत छलनी

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

विधि

मान लीजिए कि हम समग्र संख्या n को गुणनखंडित करने का प्रयास कर रहे हैं। हम एक बाध्य बी चुनते हैं, और कारक आधार (जिसे हम पी कहते हैं) की पहचान करते हैं, बी से कम या उसके बराबर सभी प्राइम्स का सेट। अगला, हम सकारात्मक पूर्णांक जेड की खोज करते हैं जैसे कि जेड और जेड + एन दोनों बी हैं- चिकनी संख्या - यानी उनके सभी प्रमुख गुणनखंड 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}}$

(जहां ए_iऔर बी_iअऋणात्मक पूर्णांक हैं।)

जब हमने इन संबंधों को पर्याप्त रूप से उत्पन्न कर लिया है (आमतौर पर यह पर्याप्त है कि संबंधों की संख्या P के आकार से कुछ अधिक हो), तो हम इन विभिन्न संबंधों को एक साथ गुणा करने के लिए रैखिक बीजगणित के तरीकों का उपयोग कर सकते हैं ताकि के घातांक अभाज्य संख्याएँ सभी सम हैं। यह हमें a के रूप के वर्गों की सर्वांगसमता देगा²≡बी² (mod n), जिसे n = महत्तम सामान्य भाजक(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):

$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 के साथ सहअभाज्य होना निर्धारित किया गया है), यह घटकर 2 हो जाता है⁴ ≡ 3⁸ (मॉड एन), या 4² ≡ 81² (मॉड एन)। परिणामी गुणनखंड 187 = gcd(81-4,187) × gcd(81+4,187) = 11×17 है।

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

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

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

परिमेय छलनी, सामान्य संख्या क्षेत्र छलनी की तरह, p ​​के रूप की संख्याओं का गुणनखण्ड नहीं कर सकती^m, जहाँ p एक अभाज्य संख्या है और m एक पूर्णांक है। यह कोई बड़ी समस्या नहीं है, हालांकि—ऐसी संख्याएं सांख्यिकीय रूप से दुर्लभ हैं, और इसके अलावा यह जांचने की एक सरल और तेज प्रक्रिया है कि दी गई संख्या इस रूप की है या नहीं। शायद सबसे सुरुचिपूर्ण तरीका यह जांचना है कि क्या $\lfloor n^{1/b}\rfloor ^{b}=n$ रूट निष्कर्षण के लिए न्यूटन की विधि के पूर्णांक संस्करण का उपयोग करके किसी भी 1 <बी <लॉग (एन) के लिए धारण करता है। सबसे बड़ी समस्या पर्याप्त संख्या में z का पता लगाना है जैसे कि z और z+n दोनों B-चिकनी हैं। किसी दिए गए बी के लिए, बी-चिकनी संख्याओं का अनुपात संख्या के आकार के साथ तेजी से घटता है। इसलिए यदि n बड़ा है (कहते हैं, सौ अंक), एल्गोरिथम के काम करने के लिए पर्याप्त z खोजना मुश्किल या असंभव होगा। सामान्य संख्या फ़ील्ड छलनी का लाभ यह है कि किसी को ऑर्डर एन की चिकनी संख्याओं की खोज करने की आवश्यकता होती है^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.

फुटनोट्स

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