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

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

विधि

मान लीजिए कि हम समग्र संख्या 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}$

(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⁸ (मॉड 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) के लिए मान्य है या नहीं है .

सबसे बड़ी समस्या पर्याप्त संख्या में 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.

फुटनोट्स

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