خوارزمية شور لـ ECDLP — تقديم جائزة Q-Day

حل كمومي لمسألة اللوغاريتم المتقطع للمنحنى الإهليلجي (ECDLP)، مبني لتحدي جائزة Q-Day بواسطة Project Eleven. الهدف: استعادة المفاتيح الخاصة لـ ECC على عتاد كمومي حقيقي باستخدام خوارزمية شور.

• المؤلف: Giancarlo Lelli
• جهة الاتصال: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• الخلفية: قائد تكنولوجي مع أكثر من 10 سنوات في برمجيات المؤسسات، وهندسة التطبيقات الكاملة، والتطوير السحابي الأصلي. خلفية في علوم الكمبيوتر مع خبرة عملية عبر أنظمة .NET، Python، Rust، والأنظمة السحابية. يعمل حاليًا كأخصائي GTM سحابي يركز على هندسة الحلول وهندسة المبيعات.

النهج

جميع منحنيات التحدي تستخدم y^2 = x^3 + 7 فوق F_p (a = 0, b = 7)، مطابقة لعائلة secp256k1. ينفذ الحل المتغير ذو المسجلين لخوارزمية شور لـ ECDLP:

1. تحضير مسجلَي العد |j>، |k> في حالة تراكب منتظم (بوابات هادامارد)
2. حساب |j>|k>|jG + kQ> عبر 2t من عمليات الجمع النقطية المُحكمة (t = عدد كيوبتات العد)
3. قياس مسجل النقطة، مما ينهاره إلى عنصر جماعي R
4. تطبيق تحويل فورييه الكمومي العكسي على مسجلَي العد
5. قياس j, k واستخراج d من العلاقة j + kd = r (mod n)

يتم استعادة المفتاح الخاص d عن طريق جمع عينات متعددة من (j, k) تحقق نفس العلاقة الخطية بترتيب المجموعة n. يدعم الحل ست استراتيجيات أوراكل لعمليات الجمع النقطية المُحكمة، تُختار تلقائيًا بناءً على حجم المنحنى أو يدويًا عبر --oracle.

استراتيجيات الأوراكل

الاستراتيجية 1: الوحدة الكثيفة (الافتراضية لـ n_bits <= 6)

تُستخدم للمنحنيات ذات ترتيب مجموعة يصل إلى ~6 بت. مُنفذة في projecteleven.py.

كل عملية "add S" نقطية مُحكمة يتم تمثيلها كمصفوفة تبديل 2^(n+1) x 2^(n+1) تُطبق عبر qc.unitary(). المصفوفة ترمز لفعل المجموعة الكامل: الكتلة العلوية اليسرى هي المحايد (control=0)، الكتلة السفلية اليمنى تبدل حالات الأساس وفقًا للخريطة P -> P+S (control=1).

• الترميز: فهرس المجموعة (0..n-1)
• الذاكرة: O(2^{2n}) لكل مصفوفة
• الكيوبتات: 2t + n (مسجلا العد + مسجل النقطة)
• القيود: تحليل الوحدة في Qiskit هو O(4^n)، مما يجعل هذا غير عملي بعد ~6 بت

الاستراتيجية 2: تحليل التبديل الفعال (الافتراضية لـ n_bits > 6)

تُستخدم للمنحنيات الأكبر. مُنفذة في quantum_arithmetic.py.

بدلاً من بناء مصفوفات كثيفة، يتم تحليل كل تبديل "add S" إلى دورات ثم إلى تباديل ثنائية. كل تبادل ثنائي (تبديل حالتين أساسيتين |a> <-> |b>) يُنفذ باستخدام:

1. تقليل CNOT -- بوابات CNOT من بت محوري إلى جميع البتات المختلفة الأخرى، مما يقلل الفرق متعدد البتات إلى فرق بت واحد
2. X متعدد التحكم -- بوابة MCX على البت المحوري، مشروطة بمطابقة جميع البتات الأخرى للنمط الهدف
3. إلغاء بوابات CNOT -- عكس الخطوة 1 لاستعادة البتات غير المحورية

يستخدم MCX تحليل V-chain مع (n-2) كيوبتات مساعدة مخصصة، مما يعطي O(n) بوابات Toffoli لكل MCX بدلاً من O(n^2) بدون مساعدات. تُبنى كل عملية جمع محكمة كـ دارة فرعية معزولة وتُضاف كبوابة واحدة معتمة، متجنبة النمو التربيعي لـ DAG في Qiskit.

• الترميز: فهرس المجموعة (0..n-1)
• الذاكرة: O(N) لكل عملية جمع (N = ترتيب المجموعة)
• الكيوبتات: 2t + n + (n-2) مساعدات
• البوابات لكل عملية جمع: O(N * n)

الاستراتيجية 3: الأوراكل الكمومي المعتمد على الإحداثيات (--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" محكمة من صيغة الجمع على المنحنى الإهليلجي عبر جميع ترميزات الإحداثيات الصالحة، منتجة تبديلاً على مسجل الإحداثيات. يُحلل هذا التبديل إلى تباديل ثنائية باستخدام نفس بنية تقليل CNOT + MCX كما في الاستراتيجية 2.

• الترميز: إحداثيات (x, y, id_flag)
• الكيوبتات: 2t + 2f_bits + 1 + max(0, 2f_bits - 1) مساعدات
• البوابات لكل عملية جمع: O(N * f_bits)

الاستراتيجية 4: الأوراكل الحسابي (--oracle arithmetic)

إطار لجمع النقاط ذو مقياس متعدد الحدود. مُنفذة في quantum_oracle.py و quantum_arithmetic.py.

يستخدم ترميز الإحداثيات (نفس الاستراتيجية 3) مع أساسيات حسابية معيارية مبنية على QFT كخطوات بناء نحو جمع نقاط حسابي كامل. تشمل قاعدة الكود تطبيقات مختبرة لـ:

• جمع Beauregard المعياري -- مبني على QFT (هدف + ثابت) mod p مع إلغاء مساعد مناسب
• ضرب كمومي-كمومي معياري -- |a>|b>|0> -> |a>|b>|a*b mod p> عبر تحويل وإضافة مع مضاعفة معيارية صريحة، O(n^3) بوابات
• تبديل مقلوب معياري -- |x> -> |x^{-1} mod p> عبر تبديلات جدول بحث
• جمع كمومي-كمومي معياري محكم -- |a> مُحكم -> |a + b mod p> مع تقليل Beauregard

تحقق الأساسيات الحسابية مقياس O(n^3) لكل جمع نقطي مقابل O(N*n) لنهج التبديل. ومع ذلك، تحمل العمليات المبنية على QFT عامل ثابت أكبر بحوالي 150x، مما يجعل النهج الحسابي أكثر كفاءة فقط للمنحنيات التي يزيد ترتيب مجموعتها عن ~20 بت. لأحجام التحدي الحالية (حتى 12 بت)، يبقى المُجمع القائم على التبديل أسرع ويُستخدم افتراضيًا.

الاستراتيجية 5: تقدير الطور شبه الكلاسيكي من Google (--oracle google)

مُنفذة في google_semiclassical.py. مستوحاة من تقنية إعادة تدوير الكيوبت لتقدير الطور من Griffiths & Niu (1996)، المطبقة على نطاق واسع في Babbush et al. (2026) لتقديرات موارد ECDLP secp256k1. نُشرت ورقة Babbush et al. في 30 مارس 2026.

تستبدل مسجلي العد متعددي الكيوبت (j, k) وتحويل فورييه الكمومي العكسي الضخم بـ كيوبتين معاد تدويرهما مفردين وتصحيحات طور مشروطة كلاسيكيًا. تُعالج كل بتة من مسجل العد بالتسلسل: تحضر في |+>، تطبق جمع نقطي محكم، تصحح الطور بناءً على جميع البتات المقاسة سابقًا، ثم تقيس. تتيح أساسيات الدارة الديناميكية reset + if_test في Qiskit ذلك على عتاد IBM Quantum.

يتم تفويض الأوراكل لعمليات الجمع النقطية المُحكمة إلى البنية الأساسية الحالية (وحدة كثيفة لـ <= 6 بت، تبديل فعال لـ > 6 بت)، لذا فإن توفير الكيوبتات يأتي بالكامل من إلغاء مسجلي العد.

• الترميز: نفس الاستراتيجية الأساسية (فهرس المجموعة)
• الكيوبتات: 2 + n_bits + مساعدات (مقابل 2t + n_bits + مساعدات)
• المقايضة: يتطلب دوائر ديناميكية (قياس في منتصف الدارة، إعادة تعيين، بوابات مشروطة كلاسيكيًا). يعمل على IBM Heron r2 حتى 7 بت؛ عند 8 بت فأكثر، يتجاوز عبء مزامنة التغذية الراجعة الكلاسيكية ميزانية وقت QPU

الاستراتيجية 6: الجمع المعياري ripple-carry (--oracle ripple)

مُنفذة في ripple_carry_shor.py. تستخدم جامعات ripple-carry CDKM (Cuccaro et al. 2004) لعمليات الجمع النقطية المُحكمة، مستبدلةً كلاً من مصفوفات الوحدة الكثيفة ودوائر التبديل المحللة إلى دورات.

في ترميز فهرس المجموعة، النقطة P = kG ممثلة بفهرسها k في المجموعة الدائرية. إضافة S = sG تصبح جمعًا معياريًا للثابت الكلاسيكي s (mod n). الفكرة الرئيسية: كل عملية جمع نقطية محكمة تختزل إلى عملية جمع معياري محكم واحد لثابت معروف، يتم تنفيذه عبر CDKMRippleCarryAdder و IntegerComparator من Qiskit.

يتكون الأوراكل من 2m من عمليات الجمع المعياري المُحكمة (m لكل مسجل عد)، حيث يؤدي كل جمع معياري محكم ما يلي:

1. تحميل الثابت في مسجل مساعد عبر CX من كيوبت التحكم
2. نصف جامع CDKM لإضافة المساعد إلى المُجمّع (بوابات الجوار الأقرب فقط)
3. مقارن صحيح للكشف عن الفائض (acc >= n)
4. طرح مشروط لـ n عبر إضافة مشروطة لـ 2^m1 - n بواسطة العلم
5. إلغاء العلم عبر استقصاء قائم على الحمل

لا يُستخدم أي معرفة بالمفتاح الخاص d في بناء الدارة. يتم حساب فهارس المجموعة لقوى G كـ 2^i mod n (عامة). يتم اشتقاق فهارس المجموعة لقوى Q من التعداد العام للمجموعة الدائرية المولدة بواسطة G — يتم البحث عن النقطة Q في هذا التعداد.

• الترميز: فهرس المجموعة (0..n-1)
• الكيوبتات: 4m + 5 حيث m = ceil(log2(n))
• البوابات لكل عملية جمع: O(m) عمليات CDKM، كل منها O(m) بوابة CX
• مقياس CX الكلي: O(m^3)
• التخطيط على العتاد: يستخدم CDKM بوابات الجوار الأقرب فقط، مما يعطي عبء توجيه ~1x على طبولوجيا IBM heavy-hex (مقابل 26-33x للجامعات المبنية على QFT)

المقارنة

أساسيات QFT الحسابية

تتضمن قاعدة الكود أساسيات حسابية معيارية مبنية على QFT (جامعات Beauregard/Draper، ضرب كمومي-كمومي معياري، مقلوب/نفي معياري) كأساس نحو ترميز إحداثي كامل عند 256 بت. تم التحقق من صحة هذه الأساسيات عبر محاكاة Statevector للأعداد الأولية حتى p=13.

النتائج

تم استعادة المفاتيح الخاصة بنجاح على عتاد IBM Quantum لمنحنيات التحدي حتى 17-bit:

تم تنفيذ جميع عمليات التشغيل على خطة المثيل المفتوح IBM Quantum، التي تمنح 10 دقائق من الحوسبة الكمومية المجانية شهريًا. سجلات التنفيذ الكاملة موجودة في مجلد executions/.

مكنت استراتيجية ripple-carry (الاستراتيجية 6) من قفزة كبيرة: من 10-bit (40 كيوبت، 2M بوابة) إلى 17-bit (69 كيوبت، 112K بوابة) — زيادة في حجم المفتاح بمقدار 7 بت مع تقليل عدد بوابات الكيوبت الثنائي بمقدار 18 مرة. بنية بوابة الجوار الأقرب لجامع CDKM تُخطط بكفاءة على طبولوجيا IBM heavy-hex، مما يحافظ على عبء توجيه قريب من 1x.

تقدير الطور شبه الكلاسيكي: دوائر ديناميكية على عتاد IBM

استعادت الاستراتيجية شبه الكلاسيكية (--oracle google) المفاتيح بنجاح عند 4-bit و6-bit و7-bit باستخدام دوائر ديناميكية (reset في منتصف الدارة، بوابات p مشروطة كلاسيكيًا عبر if_test) على معالجات IBM Heron r2. عند 7-bit، تستخدم الدارة فقط 14 كيوبت (مقابل 26 لنهج التبديل القياسي) مع إنتاج أعداد بوابة 2Q مماثلة بعد النقل.

عند 8-bit فأكثر، يصبح النهج شبه الكلاسيكي غير عملي على عتاد IBM الحالي. على الرغم من دعم if_else و reset على Heron r2 (تم تأكيده عبر فحص الهدف الخلفي)، تتطلب كل نقطة تغذية راجعة كلاسيكية مزامنة كاملة لـ QPU — يجب أن تظل جميع الكيوبتات الفيزيائية الـ 156 خاملة بينما يعالج المتحكم الكلاسيكي الشرطي للـ ~16 كيوبت نشط. مع ~295K بوابة CZ موزعة على 16+ نقطة تغذية راجعة، يتجاوز عبء التنفيذ لكل طلقة ميزانية وقت QPU. نهج التبديل القياسي، الذي يشغل نفس عدد البوابات كدفعة واحدة مستمرة بدون دوائر ديناميكية، يكتمل بنجاح على هذا المقياس.

يعمل تقريب QFT التقريبي (معامل max_corrections) على تقليل عدد كتل if_else من O(n^2) إلى O(n) عن طريق الاحتفاظ فقط بأقرب k تصحيحات طور لكل خطوة قياس (الزوايا بعد k تساهم بأقل من < pi/2^{k+1}، تحت عتبة الضوضاء في العتاد). مع max_corrections=1، تحتوي الدارة 8-bit على 16 كتلة if_else — لا يزال كافيًا للتسبب في انتهاء المهلة على عتاد IBM عند هذا العدد من البوابات.

تحليل الضوضاء والإخلاص

الإخلاص المقدر للدارة

بافتراض إخلاص نموذجي لبوابة IBM Quantum ثنائية الكيوبت (CX) يبلغ ~99.5%، ينخفض الإخلاص المقدر للدارة أسيًا مع عدد البوابات:

يُحسب إخلاص الدارة كـ F ≈ (0.995)^{CX_count}. بالنسبة لكل ما بعد 4-bit، الإخلاص المقدر صغير فلكيًا — توزيع المخرجات يغلب عليه الضوضاء بشكل ساحق.

لماذا لا يزال يعمل

بالنسبة لـ 8-bit فأكثر، تنتج كل طلقة سلسلة بتات فريدة تقريبًا (8,128 نتيجة فريدة من أصل 8,192 طلقة عند 8-bit؛ جميع الـ 20,000 فريدة عند 16-bit و17-bit). المخرجات لا يمكن تمييزها عن أخذ عينات عشوائية منتظمة على مستوى سلسلة البتات. ومع ذلك، لا يزال الخوارزمي يستعيد المفتاح الخاص الصحيح.

الفكرة الرئيسية هي أن معالجة شور اللاحقة مقاومة للضوضاء بطريقة لا يكون عليها تحليل سلسلة البتات الخام. تنتج كل طلقة ثلاثية (j, k, r) مقاسة. يستخرج الحساب d_cand = (r - j) · k^{-1} mod n ويتحقق عبر d_cand · G == Q. فقط d الحقيقي يمرر التحقق من EC، لذا حتى مرشح صحيح واحد من بين آلاف طلقات الضوضاء يكفي.

تنتج ثلاثية (j, k, r) عشوائية بحتة d_cand الصحيح باحتمال ~1/n. مع S طلقة، العدد المتوقع للنتائج المؤكدة من الضوضاء وحدها هو ~S/n. عند 17-bit (n=65,173، S=20,000)، يعطي هذا ~0.3 نتيجة ضوضاء متوقعة — أي استعادة ناجحة على هذا المقياس تقدم دليلاً على إشارة كمومية تتجاوز عتبة الضوضاء الكلاسيكية.

بالنسبة للمنحنيات الأصغر حيث الطلقات >> n (على سبيل المثال، 10-bit مع n=547 و1,024 طلقة)، عتبة الضوضاء هي ~1,024/547 ≈ 1.9 صوت لكل مرشح. حتى حفنة من الطلقات الحاملة للإشارة تدفع d الصحيح فوق عتبة الضوضاء. هذا يشرح كيف ينجح الخوارزمي على الرغم من إخلاص الدارة الذي قد يجعل الحساب يبدو مستحيلاً.

الإشارة الكمومية مقابل الضوضاء الكلاسيكية

على مقياس الألعاب، تعمل خطوة التحقق من الاستخراج (d_cand * G == Q) كمرشح يقبل فقط d الحقيقي. هذا يعني أنه حتى الثلاثيات (j, k, r) العشوائية البحتة ستنتج مرشحات صالحة بمعدل يقارب طلقات / n لكل تشغيل. عندما طلقات >> n، يمكن للضوضاء العشوائية وحدها استعادة d باحتمال عالٍ.

لاختبار ما إذا كانت الدارة الكمومية تساهم بإشارة تتجاوز عتبة الضوضاء الكلاسيكية هذه، قمنا بتشغيل تحدي 6-bit (n=31) بـ 8 طلقات فقط (أقل بكثير من ترتيب المجموعة) 10 مرات على ibm_kingston:

النتيجة: 4/10 نجاحات (40%) مقابل خط أساس ضوضاء كلاسيكي يبلغ ~20% (محسوب عبر محاكاة مونت كارلو: 8 سلاسل بتات عشوائية مع (r-j)*k_inv mod 31 مصفاة عبر التحقق). اختبار ذو حدين أحادي الطرف: P(X >= 4 | n=10, p=0.20) = 0.121، مما يشير إلى تحسن بمقدار 2x عن عتبة الضوضاء. على الرغم من أنه ليس ذا دلالة إحصائية فردية عند p < 0.05 (والذي يتطلب 5+ نجاحات)، فإن المعدل الملاحظ يتوافق مع إشارة كمومية تساهم بحوالي 1-2 زوج إضافي صالح (j, k) لكل تشغيل يتجاوز ما توفره الفرصة العشوائية.

تقع هذه النتيجة بين عتبة الضوضاء الكلاسيكية ونظام الميزة الكمومية النظرية. عند أحجام المنحنيات الأكبر حيث n >> طلقات، تنخفض عتبة الضوضاء إلى أقل من 1% وأي استعادة ناجحة للمفتاح تصبح دليلاً قوياً على الحساب الكمومي.

البداية السريعة```bash

git clone https://github.com/GiancarloLelli/quantum.git cd quantum

python -m venv . Scripts\Activate.ps1 # For Windows only

pip install -r requirements.txt

### كيفية التشغيل

تحتاج إلى حساب [IBM Quantum](https://quantum.ibm.com/). قم بتمرير رمز API الخاص بك في أول تشغيل وسيتم حفظه محليًا:```bash
# Solve the 4-bit challenge curve:
python projecteleven.py --challenge 4 --token YOUR_IBM_TOKEN --backend ibm_marrakesh

# Subsequent runs (token already saved):
python projecteleven.py --challenge 4 --backend ibm_marrakesh

# Use the coordinate-based quantum oracle:
python projecteleven.py --challenge 4 --oracle coordinate --backend ibm_marrakesh

# Use the arithmetic oracle (coordinate encoding + QFT primitives):
python projecteleven.py --challenge 4 --oracle arithmetic --backend ibm_marrakesh

# Use ripple-carry modular addition (CDKM — best for 8-bit+):
python projecteleven.py --challenge 16 --oracle ripple --backend ibm_fez --shots 20000

# Use Google semiclassical phase estimation (qubit-recycled):
python projecteleven.py --challenge 4 --oracle google --backend ibm_marrakesh

# Use a specific IBM Quantum instance:
python projecteleven.py --challenge 4 --instance ibm-q/open/main --backend ibm_marrakesh

# Verify curve parameters without quantum execution:
python projecteleven.py --curve curve_4 --verify-only

خيارات CLI

هيكل المشروع```

projecteleven.py # Shor solver — dense unitary approach + CLI entry point quantum_arithmetic.py # Efficient permutation decomposition + QFT arithmetic primitives quantum_oracle.py # Coordinate-based oracle + arithmetic oracle framework google_semiclassical.py # Google semiclassical PE — qubit-recycled phase estimation ripple_carry_shor.py # Ripple-carry modular addition oracle (CDKM) — best for 8-bit+ input_curves.json # Challenge curves (4-bit to 30-bit) problem/curves.py # Curve generation utility requirements.txt # qiskit, qiskit-ibm-runtime

## المراجع

- P. Shor، ["خوارزميات الحوسبة الكمومية: اللوغاريتمات المنفصلة والتحليل إلى عوامل"](https://arxiv.org/abs/quant-ph/9508027) (1994)
- S. Beauregard، ["دائرة لخوارزمية شور باستخدام 2n+3 كيوبت"](https://arxiv.org/abs/quant-ph/0205095) (2003)
- S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton، ["دائرة جمع تموجية كمومية جديدة"](https://arxiv.org/abs/quant-ph/0410184) (2004)
- M. Roetteler, M. Naehrig, K. Svore, K. Lauter، ["تقديرات الموارد الكمومية لحساب اللوغاريتمات المنفصلة للمنحنيات الإهليلجية"](https://arxiv.org/abs/1706.06752) (2017)
- R. Griffiths, C.-S. Niu، ["تحويل فورييه شبه التقليدي للحوسبة الكمومية"](https://arxiv.org/abs/quant-ph/9511007) (1996)
- R. Babbush وآخرون، ["تأمين العملات المشفرة القائمة على المنحنيات الإهليلجية ضد نقاط الضعف الكمومية: تقديرات الموارد وسبل التخفيف"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## الترخيص

هذا المشروع هو تقديم لتحدي جائزة اليوم-كيوم المنشور بموجب [رخصة MIT](https://github.com/yuvadm/quantumslop/blob/HEAD/LICENSE)