Shor का ECDLP के लिए एल्गोरिदम — Q-Day Prize Submission

Q-Day Prize Challenge के लिए Project Eleven द्वारा निर्मित Elliptic Curve Discrete Logarithm Problem (ECDLP) का क्वांटम हल। लक्ष्य: Shor के एल्गोरिदम का उपयोग करके वास्तविक क्वांटम हार्डवेयर पर ECC निजी कुंजियाँ प्राप्त करना।

• लेखक: Giancarlo Lelli
• संपर्क: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• पृष्ठभूमि: एंटरप्राइज़ सॉफ़्टवेयर, फुल-स्टैक आर्किटेक्चर और क्लाउड-नेटिव डेवलपमेंट में 10+ वर्षों का अनुभव रखने वाले टेक्नोलॉजी लीडर। .NET, Python, Rust और Cloud इकोसिस्टम में व्यावहारिक अनुभव के साथ कंप्यूटर साइंस में पृष्ठभूमि। वर्तमान में Cloud GTM Specialist के रूप में कार्यरत, जो सॉल्यूशन आर्किटेक्चर और सेल्स इंजीनियरिंग पर केंद्रित है।

दृष्टिकोण

सभी चुनौती वक्र F_p पर y^2 = x^3 + 7 का उपयोग करते हैं (a = 0, b = 7), जो secp256k1 परिवार से मेल खाता है। सॉल्वर ECDLP के लिए Shor के एल्गोरिदम के दो-रजिस्टर वेरिएंट को कार्यान्वित करता है:

1. गणना रजिस्टरों |j>, |k> को एकसमान सुपरपोज़िशन (Hadamard) में तैयार करें
2. 2t नियंत्रित बिंदु योग (t = num_counting qubits) के माध्यम से |j>|k>|jG + kQ> की गणना करें
3. बिंदु रजिस्टर को मापें, इसे किसी समूह तत्व R पर संक्षिप्त करें
4. गणना रजिस्टरों पर व्युत्क्रम QFT लागू करें
5. j, k मापें और संबंध j + kd = r (mod n) से d निकालें

समूह क्रम n के मॉड्यूलो समान रैखिक संबंध को संतुष्ट करने वाले कई (j, k) नमूने एकत्र करके निजी कुंजी d पुनर्प्राप्त की जाती है। सॉल्वर नियंत्रित बिंदु योगों के लिए छह संभावित रणनीतियों का समर्थन करता है, जिन्हें वक्र आकार के आधार पर स्वचालित रूप से या --oracle के माध्यम से मैन्युअल रूप से चुना जाता है।

Oracle रणनीतियाँ

रणनीति 1: Dense Unitary (n_bits <= 6 के लिए डिफ़ॉल्ट)

~6 बिट तक के समूह क्रम वाले वक्रों के लिए उपयोग किया जाता है। projecteleven.py में कार्यान्वित।

प्रत्येक नियंत्रित बिंदु योग "add S" को qc.unitary() के माध्यम से लागू 2^(n+1) x 2^(n+1) आव्यूह (permutation matrix) के रूप में दर्शाया जाता है। मैट्रिक्स पूर्ण समूह क्रिया को एन्कोड करता है: ऊपरी-बाएं ब्लॉक पहचान है (control=0), निचला-दायां ब्लॉक मैप P -> P+S (control=1) के अनुसार आधार अवस्थाओं को क्रमपरिवर्तित करता है।

• एन्कोडिंग: समूह सूचकांक (0..n-1)
• मेमोरी: प्रति मैट्रिक्स O(2^{2n})
• क्यूबिट: 2t + n (दो गणना रजिस्टर + बिंदु रजिस्टर)
• सीमा: Qiskit का एकात्मक अपघटन O(4^n) है, जो ~6-बिट से परे अव्यवहारिक बनाता है

रणनीति 2: Efficient Permutation Decomposition (n_bits > 6 के लिए डिफ़ॉल्ट)

बड़े वक्रों के लिए उपयोग किया जाता है। quantum_arithmetic.py में कार्यान्वित।

सघन आव्यूह बनाने के बजाय, प्रत्येक "add S" क्रमपरिवर्तन को चक्र-अपघटित करके क्रमचयों में बदल दिया जाता है। प्रत्येक क्रमचय (दो आधार अवस्थाओं का स्वैप |a> <-> |b>) को इस प्रकार कार्यान्वित किया जाता है:

1. CNOT न्यूनीकरण -- एक पिवट बिट से अन्य सभी भिन्न बिट्स पर CNOT, जो मल्टी-बिट अंतर को एकल-बिट अंतर तक कम करता है
2. मल्टी-नियंत्रित X -- पिवट बिट पर एक MCX गेट, जो अन्य सभी बिट्स के लक्ष्य पैटर्न से मेल खाने की शर्त पर होता है
3. CNOT को पूर्ववत करें -- गैर-पिवट बिट्स को पुनर्स्थापित करने के लिए चरण 1 को उलटें

MCX (n-2) समर्पित एंसिला क्यूबिट के साथ V-चेन अपघटन का उपयोग करता है, जो एंसिला के बिना O(n^2) के बजाय प्रति MCX O(n) Toffoli गेट देता है। प्रत्येक नियंत्रित जोड़ को एक पृथक उप-सर्किट के रूप में बनाया जाता है और एक एकल अपारदर्शी गेट के रूप में जोड़ा जाता है, जो Qiskit में द्विघात DAG वृद्धि से बचता है।

• एन्कोडिंग: समूह सूचकांक (0..n-1)
• मेमोरी: प्रति जोड़ O(N) (N = समूह क्रम)
• क्यूबिट: 2t + n + (n-2) एंसिला
• गेट प्रति जोड़: O(N * n)

रणनीति 3: Coordinate-Based Quantum Oracle (--oracle coordinate)

~6-बिट तक के वक्रों के लिए उपलब्ध। quantum_oracle.py में कार्यान्वित।

बिंदुओं को समूह सूचकांक के रूप में एन्कोड करने के बजाय, क्वांटम रजिस्टर में बाइनरी में वास्तविक (x, y) क्षेत्र-तत्व निर्देशांक और एक पहचान फ़्लैग होता है। बिंदु रजिस्टर का लेआउट है:

• x_reg: f_bits क्यूबिट (f_bits = ceil(log2(p)))
• y_reg: f_bits क्यूबिट
• id_flag: 1 क्यूबिट (1 = अनंत पर बिंदु)

प्रत्येक नियंत्रित "add S" की गणना सभी मान्य निर्देशांक एन्कोडिंग पर EC योग सूत्र से की जाती है, जो निर्देशांक रजिस्टर पर एक क्रमपरिवर्तन उत्पन्न करता है। इस क्रमपरिवर्तन को CNOT-न्यूनीकरण + MCX बुनियादी ढांचे का उपयोग करके उसी तरह से क्रमचयों में चक्र-अपघटित किया जाता है जैसे रणनीति 2 में।

• एन्कोडिंग: (x, y, id_flag) निर्देशांक
• क्यूबिट: 2t + 2f_bits + 1 + max(0, 2f_bits - 1) एंसिला
• गेट प्रति जोड़: O(N * f_bits)

रणनीति 4: Arithmetic Oracle (--oracle arithmetic)

बहुपद-पैमाने पर बिंदु योग के लिए ढांचा। quantum_oracle.py और quantum_arithmetic.py में कार्यान्वित।

निर्देशांक एन्कोडिंग (रणनीति 3 के समान) का उपयोग करता है जिसमें पूरी तरह से अंकगणितीय बिंदु योग की दिशा में बिल्डिंग ब्लॉक के रूप में QFT-आधारित मॉड्यूलर अंकगणितीय प्राइमिटिव शामिल हैं। कोडबेस में इनका परीक्षण कार्यान्वयन शामिल है:

• Beauregard मॉड्यूलर योजक -- QFT-आधारित (target + constant) mod p उचित एंसिला अनगणना के साथ
• क्वांटम-क्वांटम मॉड्यूलर गुणक -- |a>|b>|0> -> |a>|b>|a*b mod p> via shift-and-add स्पष्ट मॉड्यूलर दोहरीकरण के साथ, O(n^3) गेट
• मॉड्यूलर व्युत्क्रम क्रमपरिवर्तन -- |x> -> |x^{-1} mod p> via लुकअप टेबल क्रमचय
• नियंत्रित क्वांटम-क्वांटम मॉड्यूलर योग -- नियंत्रित |a> -> |a + b mod p> Beauregard न्यूनीकरण के साथ

अंकगणितीय प्राइमिटिव क्रमपरिवर्तन दृष्टिकोण के लिए O(N*n) की तुलना में प्रति बिंदु योग O(n^3) स्केलिंग प्राप्त करते हैं। हालांकि, QFT-आधारित संक्रियाओं में ~150x बड़ा स्थिर कारक होता है, जिससे अंकगणितीय दृष्टिकोण केवल ~20-बिट समूह क्रम से ऊपर के वक्रों के लिए अधिक कुशल होता है। वर्तमान चुनौती आकारों (12-बिट तक) के लिए, क्रमपरिवर्तन-आधारित योजक तेज़ रहता है और डिफ़ॉल्ट रूप से उपयोग किया जाता है।

रणनीति 5: Google Semiclassical Phase Estimation (--oracle google)

google_semiclassical.py में कार्यान्वित। Griffiths & Niu (1996) की qubit-पुनर्चक्रित चरण अनुमान तकनीक से प्रेरित, Babbush et al. (2026) द्वारा secp256k1 ECDLP संसाधन अनुमानों के लिए पैमाने पर लागू। Babbush et al. पेपर 30 मार्च, 2026 को प्रकाशित हुआ था।

दो बहु-क्यूबिट गणना रजिस्टरों (j, k) और बल्क व्युत्क्रम QFT को दो एकल पुनर्चक्रित क्यूबिट और शास्त्रीय रूप से वातानुकूलित चरण सुधारों से बदल देता है। प्रत्येक गणना रजिस्टर बिट को क्रमिक रूप से संसाधित किया जाता है: |+> में तैयार करें, नियंत्रित बिंदु योग लागू करें, पहले मापे गए सभी बिट्स के आधार पर चरण सुधारें, फिर मापें। Qiskit में reset और if_test डायनेमिक सर्किट प्रिमिटिव IBM Quantum हार्डवेयर पर इसे सक्षम करते हैं।

नियंत्रित बिंदु योगों के लिए oracle मौजूदा बुनियादी ढांचे (<= 6-बिट के लिए सघन एकात्मक, > 6-बिट के लिए कुशल क्रमपरिवर्तन) को सौंपा गया है, इसलिए क्यूबिट बचत पूरी तरह से गणना रजिस्टरों को खत्म करने से आती है।

Curve size	Standard qubits	Semiclassical qubits	Savings	Hardware verified
4-bit (n=7)	11	5	55%	हाँ
6-bit (n=31)	17	7	59%	हाँ
7-bit (n=79)	26 + anc	14	46%	हाँ
8-bit (n=139)	25 + anc	10 + anc	60%	नहीं (QPU सिंक ओवरहेड)
10-bit (n=547)	31 + anc	12 + anc	61%	नहीं (QPU सिंक ओवरहेड)

• एन्कोडिंग: अंतर्निहित रणनीति (समूह सूचकांक) के समान
• क्यूबिट: 2 + n_bits + ancillas (बनाम 2t + n_bits + ancillas)
• व्यापार-बंद: डायनेमिक सर्किट (मध्य-सर्किट माप, रीसेट, शास्त्रीय रूप से वातानुकूलित गेट) की आवश्यकता होती है। IBM Heron r2 पर 7-बिट तक काम करता है; 8-बिट+ पर शास्त्रीय फीडबैक सिंक्रोनाइज़ेशन ओवरहेड QPU समय बजट से अधिक हो जाता है

रणनीति 6: Ripple-Carry Modular Addition (--oracle ripple)

ripple_carry_shor.py में कार्यान्वित। नियंत्रित बिंदु योगों के लिए CDKM रिपल-कैरी योजक (Cuccaro et al. 2004) का उपयोग करता है, जो सघन एकात्मक आव्यूह और चक्र-अपघटित क्रमचय सर्किट दोनों को प्रतिस्थापित करता है।