सामान्य संख्या क्षेत्र चलनी (GNFS) की सच्ची गणितीय संरचना

GNFS का अंतिम उद्देश्य $X, Y$ खोजना है ताकि $X^2 \equiv Y^2 \pmod N$ हो सके। इसे प्राप्त करने के लिए, गणितज्ञों ने “वास्तविक पूर्णांकों की दुनिया” और “बीजगणितीय क्षेत्रों की दुनिया” के बीच एक पुल बनाया। वह पुल “होमोमोर्फिज़्म (Homomorphism)” है।

चरण 1: दुनियाओं को जोड़ने वाला “होमोमोर्फिज़्म”

1. बहुपद का चयन और जड़ों की परिभाषा

एक विशाल भाज्य संख्या $N$ के लिए, हम एक पूर्णांक $m$ और एक बहुपद $f(x)$ चुनते हैं ताकि $f(m) \equiv 0 \pmod N$ हो। (उदाहरण: $N$ को $m$ के आधार पर विस्तारित करें और इसके गुणांकों से $f(x)$ बनाएँ। यहाँ हम मान लेते हैं कि $f(x)$ परिमेय संख्याओं के क्षेत्र $\mathbb{Q}$ पर अप्राप्य (irreducible) है (इसे और फ़ैक्टर नहीं किया जा सकता))।

अगला, हम समीकरण $f(x) = 0$ की “जटिल संख्याओं में जड़ों” में से एक को $\alpha$ के रूप में परिभाषित करते हैं। स्वाभाविक रूप से, $f(\alpha) = 0$ है। $\alpha$ एक पूर्णांक नहीं है, बल्कि एक जटिल संख्या है जिसमें वर्गमूल और काल्पनिक संख्याएँ शामिल हैं (एक बीजगणितीय संख्या)।

2. रिंग (Ring) और होमोमोर्फिज़्म का निर्माण

यहाँ, हम दो गणितीय “रिंग” (वे दुनिया जहाँ जोड़ और गुणा परिभाषित हैं) तैयार करते हैं।

• दुनिया A: $\mathbb{Z}[\alpha]$ (बीजगणितीय पूर्णांकों की रिंग जिसमें $\alpha$ शामिल है) यह $a + b\alpha + c\alpha^2 + \dots$ के रूप में व्यक्त संख्याओं की दुनिया है।
• दुनिया B: $\mathbb{Z}/N\mathbb{Z}$ ($N$ से भाग देने पर शेषफल की रिंग) यह केवल $0$ से $N-1$ तक के पूर्णांकों से बनी सर्वांगसमता (modulo) की दुनिया है।

यहाँ, हम दुनिया A से दुनिया B तक निम्नलिखित मैपिंग $\phi$ को परिभाषित करते हैं। $$\phi : \mathbb{Z}[\alpha] \to \mathbb{Z}/N\mathbb{Z}$$ $$\phi(\alpha) = m \pmod N$$

यह मैपिंग $\phi$ एक जादुई ऑपरेशन है जो दुनिया A के चर $\alpha$ को दुनिया B के पूर्णांक $m$ से बदल देता है। इस $\phi$ में एक अत्यंत शक्तिशाली गुण है जिसे “रिंग होमोमोर्फिज़्म (Ring Homomorphism)” कहा जाता है। होमोमोर्फिज़्म का अर्थ है “जोड़ और गुणा की संरचना को नष्ट किए बिना किसी दूसरी दुनिया में टेलीपोर्ट करना” । दूसरे शब्दों में, निम्नलिखित समीकरण सत्य हैं:

• $\phi(X \times Y) = \phi(X) \times \phi(Y)$
• $\phi(X^2) = \phi(X)^2$

इसका क्या मतलब है? अगर हम “दुनिया A ($\alpha$ की दुनिया)” में किसी जटिल तत्व $\gamma$ का “वर्ग ($\gamma^2$)” बना सकते हैं, और इसे $\phi$ का उपयोग करके “दुनिया B (शेषफल की दुनिया)” में टेलीपोर्ट कर सकते हैं, तो वर्ग रूप $\phi(\gamma)^2$ पूरी तरह से संरक्षित रहता है ।

चरण 2: अभाज्य गुणनखंडन का पतन और “आदर्शों (Ideals)” का जन्म

हम दुनिया A ($\mathbb{Z}[\alpha]$) में कई उपयुक्त तत्वों $(a - b\alpha)$ को इकट्ठा करना चाहते हैं, और उन्हें गुणा करके एक “पूर्ण वर्ग (वर्ग तत्व)” बनाना चाहते हैं। आम तौर पर, हम प्रत्येक $(a - b\alpha)$ को “अभाज्य गुणनखंड (prime factorization)” करेंगे और उन्हें इस तरह जोड़ेंगे कि अभाज्य संख्याओं के घातांक सभी सम (even) हों (मैट्रिक्स के साथ हल करके) ताकि एक वर्ग बनाया जा सके।

हालाँकि, यहाँ बीजगणित की निराशाजनक दीवार खड़ी है। $\mathbb{Z}[\alpha]$ जैसी बीजगणितीय दुनिया में, मिडिल स्कूल में सिखाई गई “अभाज्य गुणनखंडन की विशिष्टता (किसी भी संख्या को विशिष्ट रूप से अभाज्य संख्याओं के उत्पाद के रूप में व्यक्त किया जा सकता है)” ढह जाती है ।

(उदाहरण: एक निश्चित बीजगणितीय क्षेत्र की दुनिया में, $6 = 2 \times 3$ है, और साथ ही $6 = (1+\sqrt{-5}) \times (1-\sqrt{-5})$ है, और हम यह नहीं जानते कि कौन सा असली अभाज्य है)

यदि अभाज्य गुणनखंडन अद्वितीय नहीं है, तो “अभाज्य संख्याओं की गिनती करके उन्हें सम बनाना” की पहेली (चलनी विधि) सैद्धांतिक रूप से असंभव है।

कुमेर और डेडेकिंड का बचाव: “आदर्श (Ideal)”

इस पतन से जो बचाया गया, वह 19वीं सदी के गणितज्ञों द्वारा बनाई गई “आदर्श (Ideal: आदर्श संख्या)” की अवधारणा थी। तत्व के बजाय, तत्व द्वारा उत्पन्न “गुणकों के सेट (आदर्श)” पर विचार करके, अभाज्य गुणनखंडन फिर से संभव हो गया।

एक बीजगणितीय क्षेत्र की पूर्णांक रिंग $\mathcal{O}_K$ ($\mathbb{Z}[\alpha]$ सहित अधिक पूर्ण रिंग) में, यह सिद्ध होता है कि भले ही तत्वों को विशिष्ट रूप से गुणनखंडित नहीं किया जा सकता, “एक आदर्श को हमेशा ‘अभाज्य आदर्शों ($\mathfrak{p}$)’ के उत्पाद के रूप में विशिष्ट रूप से गुणनखंडित किया जा सकता है” ।

इसलिए GNFS में, तत्व $(a - b\alpha)$ को सीधे गुणनखंडित करने के बजाय, हम इसके द्वारा उत्पन्न प्रमुख आदर्श (principal ideal) $\langle a - b\alpha \rangle$ को अभाज्य आदर्शों में गुणनखंडित करते हैं ।

चरण 3: नॉर्म (Norm) और दो चलनियां (Sieves)

तो, हम कैसे जानेंगे कि आदर्श $\langle a - b\alpha \rangle$ किन अभाज्य आदर्शों में विघटित होगा? यहाँ हम “नॉर्म (Norm)” नामक फ़ंक्शन का उपयोग करते हैं। नॉर्म एक ऐसा फ़ंक्शन है जो बीजगणितीय क्षेत्रों के जटिल तत्वों को “सामान्य वास्तविक पूर्णांकों $\mathbb{Z}$” में परिवर्तित करता है।

तत्व $(a - b\alpha)$ का नॉर्म एक साधारण बहुपद गणना $b^d f(a/b)$ द्वारा पाया जाता है ($d$, $f(x)$ की डिग्री है)।

बीजगणितीय प्रमेयों से, हम जानते हैं कि “यदि किसी आदर्श के नॉर्म को छोटी अभाज्य संख्याओं में पूरी तरह से गुणनखंडित किया जा सकता है (चिकना है), तो मूल आदर्श को भी छोटे अभाज्य आदर्शों में पूरी तरह से गुणनखंडित किया जा सकता है” ।

इसलिए GNFS पूर्णांक युग्मों $(a, b)$ की एक बड़ी संख्या के लिए निम्नलिखित दो की एक साथ गणना करता है, और केवल उन युग्मों को एकत्र करता है जहाँ दोनों “चिकनी संख्या (smooth number)” बन जाते हैं:

1. परिमेय चलनी (Rational Sieve) : $a - bm$ (वास्तविक दुनिया में मान)
2. बीजगणितीय चलनी (Algebraic Sieve) : $b^d f(a/b)$ (बीजगणितीय दुनिया में नॉर्म)

दशकों लाख युग्मों $(a, b)$ को इकट्ठा करने के बाद, हम अभाज्य आदर्श गुणनखंडन डेटा (कितने अभाज्य आदर्श शामिल हैं) को एक विशाल मैट्रिक्स (GF(2) पर रैखिक बीजगणित) के रूप में हल करते हैं ताकि युग्मों का एक सेट $S$ मिल सके जहाँ “गुणा करने पर सभी अभाज्य आदर्शों के घातांक सम हो जाते हैं”।

चरण 4: दो “बाधाएं” और आदर्श वर्ग समूह (Ideal Class Group)

मैट्रिक्स गणना से, हमने पाया कि सेट $S$ से संबंधित सभी $(a - b\alpha)$ के आदर्शों को गुणा करने पर एक निश्चित आदर्श $I$ का वर्ग प्राप्त होता है।

हालाँकि, यह अभी खत्म नहीं हुआ है। GNFS में सबसे गहरी और सबसे कठिन गणितीय दीवार यहीं है।

अंत में हम “आदर्श का वर्ग” नहीं चाहते हैं, बल्कि मैपिंग $\phi$ में बदलने के लिए “तत्व का वर्ग ($\gamma^2$)” चाहते हैं। सिर्फ इसलिए कि यह एक आदर्श का वर्ग बन गया, इसका मतलब यह नहीं है कि तत्व भी एक वर्ग है। यहाँ दो मजबूत गणितीय बाधाएं (Obstructions) हैं।

बाधा ①: आदर्श वर्ग समूह (Ideal Class Group) की दीवार

आदर्श $I$ हमेशा “एक ही तत्व द्वारा उत्पन्न आदर्श (प्रमुख आदर्श)” नहीं होता है। गैर-प्रमुख आदर्शों से किसी विशिष्ट तत्व $\gamma$ को निकालना असंभव है।

यहाँ “आदर्श वर्ग समूह (Class Group, $Cl_K$)” की अवधारणा आती है। आदर्श वर्ग समूह एक ऐसा समूह है जो यह मापता है कि “उस बीजगणितीय क्षेत्र की दुनिया में कितने आदर्श हैं जो प्रमुख नहीं हैं (अभाज्य गुणनखंडन की विशिष्टता कितनी टूट गई है)"। भले ही $\prod \langle a - b\alpha \rangle$, $I^2$ बन जाए, यदि $I$ आदर्श वर्ग समूह में पहचान तत्व (प्रमुख आदर्श) नहीं है, तो इसे तत्व के वर्ग में वापस नहीं लाया जा सकता है।

बाधा ②: इकाई समूह (Unit Group) की दीवार

मान लीजिए कि सौभाग्य से $I$ प्रमुख आदर्श $\langle \gamma \rangle$ है। तब, $\prod \langle a - b\alpha \rangle = \langle \gamma^2 \rangle$ होता है। आप सोच सकते हैं, “बहुत बढ़िया, तत्व भी एक वर्ग है!”, लेकिन यह एक बड़ी गलती है।

आदर्शों (गुणकों के सेट) के समान होने का मतलब यह नहीं है कि तत्व पूरी तरह से समान हैं। हमेशा एक “इकाई (Unit: एक ऐसी संख्या जिसका व्युत्क्रम भी एक पूर्णांक है। जैसे 1 या -1)” का विचलन होगा। दूसरे शब्दों में, वास्तविक तत्व समीकरण इस प्रकार बन जाता है:

($u$ इकाई समूह $U_K$ का एक तत्व है)

जब तक यह इकाई $u$ स्वयं किसी चीज़ का वर्ग नहीं है, तब तक बायाँ पक्ष कभी भी “सही तत्व का वर्ग” नहीं बन सकता।

चरण 5: एडलमैन का जादू “द्विघात वर्ण (Quadratic Characters)”

आदर्श वर्ग समूह की बाधा और इकाई समूह की बाधा। इन दोनों को कैसे पार करें? यहाँ क्रिप्टोग्राफर लियोनार्ड एडलमैन (RSA का “A”) और अन्य लोगों द्वारा पेश की गई शानदार विधि “द्विघात वर्ण (Quadratic Characters)” आती है।

यह निर्धारित करने के लिए कि “क्या बीजगणितीय क्षेत्र में कोई निश्चित तत्व पूर्ण वर्ग है?”, हम लीजेंड्रे प्रतीक (द्विघात अवशेष) के बीजगणितीय क्षेत्र संस्करण का उपयोग करते हैं। उस विशाल मैट्रिक्स (अभाज्य आदर्शों की संख्या को सम बनाने के लिए पहेली) में, हम चुपके से दर्जनों अतिरिक्त शर्तें (कॉलम) जोड़ते हैं, जिसमें कहा गया है कि “कुछ विशेष अभाज्य आदर्शों $\mathfrak{q}$ के लिए द्विघात वर्ण भी सभी $1$ (सम) होने चाहिए” ।

जब हम मैट्रिक्स गणना द्वारा इन अतिरिक्त शर्तों को भी पूरा करने वाला एक सेट $S$ खोजते हैं, तो बीजगणितीय संख्या सिद्धांत के गहरे प्रमेयों द्वारा यह गारंटी दी जाती है कि “आदर्श वर्ग समूह की बाधा और इकाई समूह की बाधा दोनों ही भारी संभावना के साथ स्वाभाविक रूप से गायब हो जाएंगे” ।

इसके साथ, अंततः हमें सच्चा समीकरण मिल जाता है:

अंतिम चरण: दुनियाओं का विलय और क्रिप्टोग्राफ़िक पतन

अंत में, पहेली के सभी टुकड़े अपनी जगह पर हैं।

[बीजगणितीय क्षेत्रों की दुनिया में तत्व (दुनिया A)] $\gamma^2 = \prod (a - b\alpha)$ (हम $\gamma$ खोजने के लिए वर्गमूल एल्गोरिदम का उपयोग करते हैं)

[वास्तविक दुनिया में तत्व (परिमेय संख्याओं की दुनिया)] $V^2 = \prod (a - bm)$ (चूंकि यह साधारण पूर्णांक गुणन है, हम आसानी से वर्गमूल $V$ पा सकते हैं)

अब, उस जादुई पुल का समय आ गया है जिसे हमने शुरुआत में बनाया था, होमोमोर्फिज़्म $\phi$ । हम $\phi$ ($\alpha$ को $m$ से बदलने वाला मैपिंग) का उपयोग करके दुनिया A के तत्व $\gamma$ को दुनिया B ($N$ के शेषफल की दुनिया) में टेलीपोर्ट करते हैं।

दूसरी ओर, हम वास्तविक दुनिया में बनाए गए $V$ को सीधे शेषफल की दुनिया में लाते हैं और इसे $X$ कहते हैं।

होमोमोर्फिज़्म की “संरचना संरक्षण” संपत्ति के कारण, दुनिया A में वर्ग संबंध दुनिया B (मोडुलो $N$ की दुनिया) में पूरी तरह से संरक्षित है। इसके अलावा, चूंकि मूल युग्म $(a, b)$, $a - b\alpha$ और $a - bm$ के रूप में बनाए गए थे, ये $X$ और $Y$ मोडुलो $N$ की दुनिया में टकराते हैं और निम्नलिखित पूर्ण समीकरण उत्पन्न करते हैं:

$$X^2 \equiv Y^2 \pmod N$$

अब हमें बस यह प्रार्थना करनी है कि ये $X$ और $Y$ तुच्छ समाधान ($X \equiv \pm Y$) न हों, और $\gcd(X - Y, N)$ की गणना करें।

यदि यह एक गैर-तुच्छ समाधान है, तो यूक्लिड का एल्गोरिदम 0.001 सेकंड में चलेगा, और RSA क्रिप्टोग्राफी का दिल कहे जाने वाले गुप्त अभाज्य $p$ और $q$ आउटपुट स्क्रीन पर छप जाएंगे।

यह आधुनिक गणित के सार का संग्रह, “सामान्य संख्या क्षेत्र चलनी (GNFS)” की पूरी तस्वीर है।