[गणितीय सूत्रों से पूर्ण समझ] क्लासिकल में सबसे शक्तिशाली 'GNFS' क्वांटम एल्गोरिदम से क्यों हारता है? अभाज्य गुणनखंडन का पैराडाइम शिफ्ट

आधुनिक इंटरनेट समाज में सूचना सुरक्षा, RSA क्रिप्टोग्राफी जैसी पब्लिक-की क्रिप्टोग्राफी प्रणालियों द्वारा सुरक्षित है। RSA क्रिप्टोग्राफी की सुरक्षा का आधार इस तथ्य पर निर्भर करता है कि “विशाल भाज्य संख्याओं का अभाज्य गुणनखंडन (Prime Factorization) कम्प्यूटेशनल रूप से अत्यंत कठिन है” ।

इस लेख में, हम क्लासिकल कंप्यूटरों के लिए सबसे शक्तिशाली अभाज्य गुणनखंडन एल्गोरिदम “सामान्य संख्या क्षेत्र चलनी” (General Number Field Sieve, GNFS) के गणितीय तंत्र को खोलेंगे, और गणितीय सूत्रों तथा वैचारिक आरेखों (concept diagrams) का उपयोग करके गहराई से यह विश्लेषण करेंगे कि यह पीटर शोर द्वारा खोजे गए “शोर के एल्गोरिदम” (Shor’s Algorithm) से पूरी तरह क्यों हार जाता है, और यह पैराडाइम शिफ्ट कैसे होता है।

1. क्लासिकल कंप्यूटिंग में अभाज्य गुणनखंडन का दृष्टिकोण: फर्मेट की अभाज्य गुणनखंडन विधि से विकास

अभाज्य गुणनखंडन समस्या का अर्थ है, दी गई एक भाज्य संख्या (composite number) $N$ के लिए अभाज्य संख्याओं $p, q$ को खोजना, जिससे $N = p \times q$ हो।

मूल विचार निम्नलिखित सर्वांगसमता (congruence) को संतुष्ट करने वाले गैर-तुच्छ (non-trivial) $x, y$ खोजने पर आ जाता है:

$$ x^2 \equiv y^2 \pmod N $$

इसे रूपांतरित करने पर,

$$ x^2 - y^2 \equiv 0 \pmod N $$ $$ (x - y)(x + y) \equiv 0 \pmod N $$

यहाँ, यदि $x \not\equiv \pm y \pmod N$ हो, तो $\gcd(x-y, N)$ या $\gcd(x+y, N)$ की गणना करके, $N$ का एक गैर-तुच्छ गुणनखंड प्राप्त किया जा सकता है। यह तथ्य GNFS जैसे आधुनिक अभाज्य गुणनखंडन एल्गोरिदम का आधार है।

2. क्लासिकल का सबसे शक्तिशाली एल्गोरिदम: “सामान्य संख्या क्षेत्र चलनी” (GNFS) की गहराई

“GNFS” आज ज्ञात क्लासिकल कंप्यूटरों के लिए सबसे तेज़ अभाज्य गुणनखंडन एल्गोरिदम है। इसकी समय जटिलता (time complexity) उप-घातांकीय (Sub-exponential) समय लेती है।

GNFS की समय जटिलता

जब संख्या $N$ के अंकों की संख्या $b = \log_2 N$ हो, तो GNFS की जटिलता इस प्रकार व्यक्त की जाती है:

$$ O\left( \exp \left( \left(\frac{64}{9} b\right)^{1/3} (\log b)^{2/3} \right) \right) $$

जैसा कि इस सूत्र से देखा जा सकता है, जटिलता बहुपद समय (polynomial time) नहीं है, बल्कि घातांकीय फ़ंक्शन (exponential function) से थोड़ी धीमी “उप-घातांकीय समय” (sub-exponential time) है। फिर भी, यदि अंकों की संख्या बढ़ती है तो गणना का समय खगोलीय रूप से बढ़ जाता है।

GNFS का गणितीय तंत्र

GNFS मुख्य रूप से 4 चरणों से मिलकर बना है:

बहुपद चयन (Polynomial Selection)
छानना (Sieving)
मैट्रिक्स न्यूनीकरण (Matrix Reduction)
वर्गमूल की गणना (Square Root)

2.1. बहुपद चयन और बीजीय संख्या क्षेत्र (Algebraic Number Field)

सबसे पहले, पूर्णांक गुणांकों (integer coefficients) वाले अलघुकरणीय बहुपदों (irreducible polynomials) $f(x)$ और $g(x)$ को चुना जाता है। इन्हें इस प्रकार सेट किया जाता है कि इनका modulo $N$ पर एक सामान्य मूल $m$ हो। अर्थात,

$$ f(m) \equiv 0 \pmod N $$ $$ g(m) \equiv 0 \pmod N $$

आमतौर पर, $g(x)$ को रैखिक बहुपद $g(x) = x - m$ के रूप में चुना जाता है। यदि $f(x)$ के मूल को $\alpha$ मान लिया जाए, तो $\mathbb{Q}(\alpha)$ नामक “संख्या क्षेत्र” (Number Field) बनता है। $\mathbb{Q}(\alpha)$ के वलय (ring) में संचालन और सामान्य पूर्णांक वलय $\mathbb{Z}$ के संचालन की तुलना होमोमोर्फिज़्म (homomorphism) $\phi: \alpha \mapsto m$ के माध्यम से की जाती है।

2.2. छानना (Sieving)

इसके बाद, सह-अभाज्य (coprime) पूर्णांकों के जोड़े $(a, b)$ की बड़ी संख्या में खोज की जाती है। इसका उद्देश्य ऐसे जोड़े खोजना है जहाँ निम्नलिखित 2 मान “B-स्मूथ” (B-smooth, केवल अपेक्षाकृत छोटे अभाज्य गुणनखंडों से बने) हों:

$a - bm$ (पूर्णांक वलय पर मान)
$b^d f(a/b)$ (संख्या क्षेत्र पर मानदंड $N(a - b\alpha)$ के अनुरूप)

यहाँ “चलनी” (Sieve) नामक एक तेज़ खोज तकनीक का उपयोग किया जाता है। इसके द्वारा, विशाल उम्मीदवारों में से शर्तों को पूरा करने वाले $(a, b)$ जोड़ों को कुशलतापूर्वक निकाला जाता है।

2.3. मैट्रिक्स न्यूनीकरण (Linear Algebra over GF(2))

एकत्र किए गए जोड़े $(a, b)$ से, घातांक सदिश (exponent vectors) का निर्माण किया जाता है, और एक विशाल विरल मैट्रिक्स (sparse matrix) के बाएँ शून्य स्थान (left null space) को $\mathbb{F}_2$ (वह क्षेत्र जिसमें केवल 0 और 1 तत्व होते हैं) पर ज्ञात किया जाता है।

वेक्टर $v$ को एक समाधान के रूप में इस प्रकार खोजा जाता है कि संबंध $ \prod (a_i - b_i m) $ और $ \prod (a_i - b_i \alpha) $ दोनों वर्ग अवयव (square elements) बन जाएँ। यह,

$$ M \mathbf{x} \equiv \mathbf{0} \pmod 2 $$

जैसी रैखिक समीकरण प्रणाली को हल करने के अलावा और कुछ नहीं है। यहाँ, ब्लॉक लैंक्ज़ोस एल्गोरिदम (Block Lanczos Algorithm) या ब्लॉक विडमैन एल्गोरिदम (Block Wiedemann Algorithm) जैसे उन्नत संख्यात्मक संगणना एल्गोरिदम का उपयोग किया जाता है।

2.4. वर्गमूल की गणना

अंत में, संख्या क्षेत्र और पूर्णांक वलय दोनों में वर्गमूल लिया जाता है, और $x^2 \equiv y^2 \pmod N$ संबंध प्राप्त किया जाता है। फिर, $\gcd(x-y, N)$ की गणना की जाती है और गुणनखंड प्राप्त किया जाता है।

3. क्वांटम कंप्यूटिंग द्वारा सफलता: “शोर का एल्गोरिदम” (Shor’s Algorithm)

जबकि GNFS को उप-घातांकीय समय की आवश्यकता होती है, 1994 में पीटर शोर द्वारा प्रस्तुत किया गया “शोर का एल्गोरिदम” , क्वांटम कंप्यूटर का उपयोग करके इस समस्या को “बहुपद समय” (Polynomial Time) में हल कर सकता है।

शोर के एल्गोरिदम की समय जटिलता

जब क्यूबिट्स की संख्या $O(\log N)$ हो, तो समय जटिलता इस प्रकार होती है:

$$ O((\log N)^3) $$

इसका मतलब यह है कि यह बिट्स की संख्या के सापेक्ष घातांकीय विस्फोट नहीं करता है। यह एक आश्चर्यजनक परिणाम है कि “क्वांटम कंप्यूटिंग” कुछ घंटों से कुछ दिनों में उन विशाल भाज्य संख्याओं को डिक्रिप्ट कर सकता है, जिनकी “क्लासिकल कंप्यूटिंग” के लिए गणना का समय ब्रह्मांड के जीवनकाल से भी अधिक होगा।

शोर के एल्गोरिदम का समग्र दृश्य: आवर्त खोज समस्या (Period Finding Problem) में कमी

शोर का एल्गोरिदम अभाज्य गुणनखंडन समस्या को बड़ी चतुराई से “आवर्त खोज समस्या” में बदल देता है।

$N$ के साथ सह-अभाज्य एक यादृच्छिक पूर्णांक $a$ चुनें ($1 < a < N$)।
फलन $f(x) = a^x \bmod N$ परिभाषित करें।
$f(x)$ का आवर्त (period) $r$ खोजें, अर्थात वह सबसे छोटा धनात्मक पूर्णांक $r$ जिसके लिए $a^r \equiv 1 \pmod N$ हो।
यदि $r$ सम (even) है, तो जांचें कि क्या $a^{r/2} \not\equiv -1 \pmod N$ है, और अभाज्य गुणनखंड प्राप्त करने के लिए $\gcd(a^{r/2} \pm 1, N)$ की गणना करें।

चरण 3 में यह “आवर्त $r$ की खोज” ही वह बाधा है जिसमें क्लासिकल कंप्यूटर को घातांकीय समय लगता है, लेकिन क्वांटम कंप्यूटर “क्वांटम सुपरपोज़िशन” और “क्वांटम फूरियर ट्रांसफॉर्म” (QFT) का उपयोग करके इसे पल भर में हल कर देता है।

4. क्वांटम फूरियर ट्रांसफॉर्म (QFT) और आवर्त का निष्कर्षण

आइए शोर के एल्गोरिदम के मूल, क्वांटम अवस्थाओं (quantum states) के संचालन को गणितीय सूत्रों के माध्यम से विस्तार से देखें।

4.1. क्वांटम सुपरपोज़िशन का निर्माण

सबसे पहले, 2 क्वांटम रजिस्टर तैयार किए जाते हैं। रजिस्टर 1 इनपुट $x$ की सुपरपोज़िशन अवस्था (superposition state) रखता है, और रजिस्टर 2 फलन के गणना परिणाम $f(x)$ को रखता है। प्रारंभिक अवस्था $|0\rangle |0\rangle$ पर हैडामर्ड ट्रांसफॉर्म (Hadamard Transform) लागू करके सभी संभावित $x$ का सुपरपोज़िशन बनाया जाता है।

$$ |\psi_1\rangle = \frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} |x\rangle |0\rangle $$

(यहाँ $Q$, $N^2 \le Q < 2N^2$ को पूरा करने वाली 2 की घात है)

इसके बाद, क्वांटम ओरेकल $U_f$ का उपयोग करके $f(x) = a^x \bmod N$ की गणना की जाती है और इसे रजिस्टर 2 में संग्रहीत किया जाता है।

$$ |\psi_2\rangle = U_f |\psi_1\rangle = \frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} |x\rangle |a^x \bmod N\rangle $$

यहाँ मान लीजिए कि रजिस्टर 2 को मापा गया है (वास्तव में इसे मापे बिना भी गणितीय संरचना समान रहती है)। यदि कोई मान $y = a^{x_0} \bmod N$ देखा जाता है, तो रजिस्टर 1 की अवस्था उन सभी $x$ के सुपरपोज़िशन में सिमट (collapse) जाती है जिनके लिए $f(x) = y$ होता है। यदि आवर्त $r$ है, तो ऐसे $x$, $x_0, x_0 + r, x_0 + 2r, \dots$ होंगे।

$$ |\psi_3\rangle = \frac{1}{\sqrt{M}} \sum_{k=0}^{M-1} |x_0 + kr\rangle $$

(यहाँ $M \approx Q/r$ पदों की संख्या है)

यह अवस्था आवर्त $r$ की जानकारी को अंतर्निहित रखती है, लेकिन इसे सीधे मापने पर केवल एक यादृच्छिक (random) $x_0 + kr$ प्राप्त होगा, और आवर्त $r$ ज्ञात नहीं होगा। यहीं पर QFT काम आता है।

4.2. क्वांटम फूरियर ट्रांसफॉर्म (Quantum Fourier Transform) लागू करना

QFT एक ऐसा ऑपरेशन है जो क्वांटम अवस्थाओं के आयामों (amplitudes) पर असतत फूरियर ट्रांसफॉर्म (Discrete Fourier Transform) करता है। अवस्था $|x\rangle$ पर QFT की क्रिया को इस प्रकार परिभाषित किया गया है:

$$ \text{QFT} |x\rangle = \frac{1}{\sqrt{Q}} \sum_{y=0}^{Q-1} e^{2\pi i \frac{xy}{Q}} |y\rangle $$

जब इसे $|\psi_3\rangle$ पर लागू किया जाता है, तो चरण हस्तक्षेप (क्वांटम इंटरफेरेंस) होता है।

$$ |\psi_4\rangle = \text{QFT} |\psi_3\rangle = \frac{1}{\sqrt{MQ}} \sum_{y=0}^{Q-1} \sum_{k=0}^{M-1} e^{2\pi i \frac{(x_0 + kr)y}{Q}} |y\rangle $$

इस समीकरण के योग का विस्तार करने पर,

$$ \sum_{k=0}^{M-1} e^{2\pi i \frac{kry}{Q}} $$

यह भाग प्रकट होता है। इस ज्यामितीय श्रेणी का योग केवल तभी एक-दूसरे को मजबूत करता है (Constructive Interference) जब $ry/Q$ एक पूर्णांक के करीब होता है, और अन्य समय में यह एक-दूसरे को रद्द (Destructive Interference) कर देता है।

इसलिए, उच्च संभावना के साथ मापी जाने वाली अवस्था $|y\rangle$ वह होगी जिसके लिए,

$$ \frac{y}{Q} \approx \frac{c}{r} $$

शर्त को पूरा करने वाला पूर्णांक $y$ हो ($c$ कोई पूर्णांक है)।

4.3. निरंतर भिन्न विस्तार (Continued Fraction Expansion) द्वारा आवर्त की पहचान

माप से $y$ प्राप्त करने के बाद, क्लासिकल कंप्यूटर का उपयोग करके $y/Q$ का “निरंतर भिन्न विस्तार” (Continued Fraction Expansion) किया जाता है। इसके द्वारा, $y/Q$ के अनुमानित भिन्न $c/r$ की गणना की जाती है, और हर (denominator) से आवर्त $r$ के उम्मीदवार को अत्यधिक कुशलता से निकाला जा सकता है।

5. वैचारिक मॉडल की तुलना और पैराडाइम शिफ्ट

GNFS और शोर के एल्गोरिदम के बीच के अंतर को सहज रूप से समझने के लिए, Mermaid सिंटैक्स का उपयोग करके एक वैचारिक आरेख (concept diagram) नीचे दिया गया है।

क्वांटम सर्किट द्वारा शोर के एल्गोरिदम का वैचारिक आरेख

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
graph TD
    A[प्रारंभिक अवस्था: 0...0] --> B[Hadamard ट्रांसफॉर्म द्वारा सभी अवस्थाओं का सुपरपोज़िशन]
    B --> C[मॉड्यूलर घातांक गणना a^x mod N]
    C -->|क्वांटम एंटैंगलमेंट| D[आवधिकता (periodicity) वाली अवस्था में सिमटना]
    D --> E[क्वांटम फूरियर ट्रांसफॉर्म QFT]
    E -->|हस्तक्षेप (Interference) द्वारा प्रायिकता प्रवर्धन| F[माप: y प्राप्त करना]
    F --> G[क्लासिकल प्रक्रिया: निरंतर भिन्न विस्तार]
    G --> H[आवर्त r की खोज]
    H --> I[N के अभाज्य गुणनखंडों की गणना]
    
    style A fill:#f9f,stroke:#333,stroke-width:2px
    style E fill:#bbf,stroke:#333,stroke-width:2px
    style I fill:#bfb,stroke:#333,stroke-width:2px

पैराडाइम शिफ्ट का सार

GNFS “गणितीय स्थान (संख्या क्षेत्र) में संबंधों को खोजने” का दृष्टिकोण अपनाता है। हालाँकि, चूँकि खोज स्थान अंकों की संख्या के सापेक्ष घातांकीय रूप से फैलता है, इसलिए क्लासिकल कंप्यूटर की गणना क्षमता (समानांतरकरण सहित) के साथ, जब कुंजी की लंबाई 2048 बिट्स आदि से अधिक हो जाती है तो इसे डिक्रिप्ट करना लगभग असंभव हो जाता है।

दूसरी ओर, शोर का एल्गोरिदम “क्वांटम हस्तक्षेप के कारण तरंग गुणों” का उपयोग करता है। यह सुपरपोज़िशन अवस्था में सभी गणना पथों (computation paths) का एक साथ मूल्यांकन करता है, और QFT द्वारा अवांछित उत्तरों को रद्द (Destructive Interference) कर देता है, तथा केवल सही उत्तर वाले आवर्त के प्रायिकता आयाम (probability amplitude) को प्रवर्धित (Constructive Interference) करता है। इससे यह स्थान को खोजने के बजाय, “सही उत्तर को ही सामने लाने” के एक बिल्कुल अलग आयाम का दृष्टिकोण प्राप्त करता है।

6. निष्कर्ष

इस लेख में, हमने क्लासिकल सीमाओं की चरम सीमा “GNFS” और क्वांटम कंप्यूटिंग की शक्ति प्रदर्शित करने वाले “शोर के एल्गोरिदम” के गणितीय पृष्ठभूमि और एल्गोरिथम संरचना की गहराई से तुलना की है।

जबकि GNFS ने बहुपद चयन और विशाल मैट्रिक्स गणना जैसी गणितीय तकनीकों का उपयोग करके समय जटिलता को उप-घातांकीय समय तक कम किया, शोर के एल्गोरिदम ने क्वांटम यांत्रिकी के मूल सिद्धांतों, सुपरपोज़िशन और हस्तक्षेप को गणितीय उपकरण (QFT) के साथ मिलाया, और एक ही झटके में बहुपद समय की सफलता प्राप्त की।

वर्तमान में, व्यावहारिक पैमाने (हजारों क्यूबिट्स) पर शोर के एल्गोरिदम को चलाने में सक्षम कोई दोष-सहिष्णु क्वांटम कंप्यूटर (Fault-Tolerant Quantum Computer, FTQC) मौजूद नहीं है। हालाँकि, इस गणितीय और सैद्धांतिक पैराडाइम शिफ्ट का अस्तित्व ही वह सबसे बड़ा कारण है कि वर्तमान में दुनिया भर में पोस्ट-क्वांटम क्रिप्टोग्राफी (PQC) की ओर संक्रमण में तेज़ी आ रही है।