خوارزمية شور لمشكلة اللوغاريتم المتقطع للمنحنيات الإهليلجية (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.

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

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

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

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

بدلاً من بناء مصفوفات كثيفة، يتم تحلل كل تبديل "إضافة 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 = نقطة عند اللانهاية)

يتم حساب كل عملية "إضافة 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 (الهدف + ثابت) مودولو 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 عاملًا ثابتًا أكبر بحوالي 150 مرة، مما يجعل النهج الحسابي أكثر كفاءة فقط للمنحنيات التي تزيد رتبة مجموعتها عن حوالي 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 الكمومية.

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

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

الاستراتيجية 6: الجمع النمطي المتسلسل بالحمل (Ripple-Carry) (--oracle ripple)

منفذة في ripple_carry_shor.py. تستخدم جامعات 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 الكمومية لمنحنيات التحدي حتى 17 بت:

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

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

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

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

عند 8 بت فما فوق، يصبح النهج شبه الكلاسيكي غير عملي على أجهزة 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 بت على 16 كتلة if_else — لا يزال ذلك كافيًا للتسبب في انتهاء المهلة على أجهزة IBM عند هذا العدد من البوابات.

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

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

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

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

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

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

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

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

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

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

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

لاختبار ما إذا كانت الدائرة الكمومية تساهم بإشارة تتجاوز عتبة الضوضاء الكلاسيكية هذه، قمنا بتشغيل تحدي 6 بت (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 et al., ["تأمين العملات الرقمية ذات المنحنيات الإهليلجية ضد الثغرات الكمومية: تقديرات الموارد ووسائل التخفيف"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## الترخيص

هذا المشروع هو مشاركة في تحدي جائزة Q-Day صدر بموجب [MIT LICENSE](https://github.com/giancarlolelli/quantum/blob/HEAD/LICENSE)