خوارزمية شور لـ 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 بت)، لذا فإن توفير الكيوبتات يأتي بالكامل من إلغاء مسجلي العد.

حجم المنحنى	الكيوبتات القياسية	الكيوبتات شبه الكلاسيكية	التوفير	تم التحقق عليه على العتاد
4-bit (n=7)	11	5	55%	نعم
6-bit (n=31)	17	7	59%	نعم
7-bit (n=79)	26 + مساعدات	14	46%	نعم
8-bit (n=139)	25 + مساعدات	10 + مساعدات	60%	لا (عبء مزامنة QPU)
10-bit (n=547)	31 + مساعدات	12 + مساعدات	61%	لا (عبء مزامنة QPU)

• الترميز: نفس الاستراتيجية الأساسية (فهرس المجموعة)
• الكيوبتات: 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 في هذا التعداد.