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

حجم المنحنى	الكيوبتات القياسية	الكيوبتات شبه الكلاسيكية	التوفير	تم التحقق منه على الأجهزة
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. تستخدم جامعات 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. إلغاء العلامة عبر استقصاء قائم على الحمل