Double Index Calculus Algorithm: Faster Solving Discrete Logarithm Problem in Finite Prime Field

ملخص تقني: خوارزمية حساب الجدولة المزدوجة لمسائل اللوغاريتم المنفصل

بيان المسألة
تتناول الورقة مسألة اللوغاريتم المنفصل (DLP) في الحقول الأولية المحدودة، وهي مسألة حسابية جوهرية تشكل ركيزة أمن العديد من المخططات التشفيرية، بما في ذلك التشفير بالمفتاح العام والتوقيعات الرقمية. وبينما تمثل خوارزمية حساب الجدولة (Index Calculus) ومتغيراتها (مثل نخلة المجال العدد - Number Field Sieve ونخلة حقل الدوال - Function Field Sieve) أحدث ما توصل إليه العلم لحل مسألة اللوغاريتم المنفصل في هذه الحقول، إلا أنها تواجه قيودًا محددة. فبشكل أساسي، تتطلب هذه الخوارزميات حساب اللوغاريتمات المنفصلة لجميع الأعداد الأولية في قاعدة العامل (بحجم $k$) بالإضافة إلى العدد المستهدف، بإجمالي $k+1$ لوغاريتم، قبل إمكانية حل المسألة المستهدفة. علاوة على ذلك، غالبًا ما تفشل خوارواتم حساب الجدولة القياسية إذا لم يكن أساس اللوغاريتم المنفصل مولدًا ضربيًا للمجال، حيث قد لا توجد لوغاريتمات منفصلة لبعض الأعداد الأولية في قاعدة العامل.

المنهجية: خوارزمية حساب الجدولة المزدوجة
يقترح المؤلفون "خوارزمية حساب الجدولة المزدوجة"، والتي تغير بشكل جذري النهج المتبع لحل مسألة اللوغاريتم المنفصل عبر تقليل عدد اللوغاريتمات المنفصلة المطلوبة.

1. أنظمة المعادلات المزدوجة: بدلاً من تثبيت معادلة هدف واحدة، تقوم الخوارزمية بإنشاء نظامين منفصلين من المعادلات الخطية:
   • يقوم النظام الأول بحساب اللوغاريتمات المنفصلة للأعداد الأولية في قاعدة العامل بالنسبة للمولد $g$ (إيجاد $\log_g p_i$).
   • يقوم النظام الثاني بحساب اللوغاريتمات المنفصلة لنفس الأعداد الأولية بالنسبة للأساس المستهدف $b$ (إيجاد $\log_b p_i$).
2. استراتيجية التقاطع: يكمن الابتكار الجوهري في تحديد عدد أولي $p_i$ في قاعدة العامل يكون قد تم حساب كل من $\log_g p_i$ و $\log_b p_i$ له بنجاح.
3. حل الهدف: بمجرد العثور على مثل هذا العدد الأولي، تقوم الخوارزمية بحل اللوغاريتم المنفصل المستهدف $x$ (حيث $g^x \equiv b \pmod p$) باستخدام العلاقة:
   $$x \equiv \alpha \beta^{-1} \pmod{p-1}$$
   حيث $g^\alpha \equiv p_i \pmod p$ و $b^\beta \equiv p_i \pmod p$.
4. الكفاءة الاحتمالية: تعتمد الخوارزمية على الطبيعة الاحتمالية لإيجاد الأعداد الصحيحة الناعمة (smooth integers). وبينما يجب على خوارزمية حساب الجدولة القياسية حل $k+1$ لوغاريتم بشكل حتمي، يمكن لخوارزمية حساب الجدولة المزدولة النجاح بمجرد أن يصبح تقاطع مجموعتي اللوغاريتمات المحسوبة غير فارغ. ويجادل المؤلفون بأن عدد "الحالات اللطيفة" (السيناريوهات التي يكون فيها الهدف قابلاً للحل بعدد أقل من $k+1$ لوغاريتم) هائل، مما يؤدي إلى احتمالية عالية للإنهاء المبكر.
5. التوازي: عمليات حساب اللوغاريتمات للأساس $g$ والأساس $b$ هي عمليات مستقلة، مما يسم un allows للتنفيذ المتوازي، وهو ما يقلل إجمالي وقت التشغيل إلى الحد الأقصى للعمليتين المتوازيتين بدلاً من مجموعهما.

المساهمات الرئيسية

• الاختراق النظري: تدعي الورقة تحقيق اختزال نظري في عدد اللوغاريتمات المنفصلة المطلوبة. فبينما تتطلب الطرق التقلية $k+1$ لوغاريتم، يمكن للخوارزمية المقترحة حل المسألة بأقل من $k+1$ لوغاريتم من خلال الاستفادة من تقاطع مجموعتين جزئيتين من اللوغاريتمات.
• تعزيز العمومية: صُممت الخوارزمية لتعمل حتى عندما لا يكون الأساس $g$ مولدًا ضربيًا للمجال. وفي مثل هذه الحالات، حيث قد تفشل خوارزمية حساب الجدولة القياسية لأن $\log_g p_i$ لا يوجد لبعض الأعداد الأولية، يمكن لخوارزمية حساب الجدولة المزدوجة أن تنجح طالما وجد عدد أولي واحد على الأقل يوجد له كل من $\log_g p_i$ و $\log_b p_i$.
• التوافق: الطريقة متوافقة مع تقنيات التحسين الموجودة (مثل طرق النخل - sieve methods) المستخدمة لتسريع إيجاد الأعداد الصحيحة الناعمة. ويمكنها استخدام هذه الحيل لإيجاد الأعداد الناعمة بشكل أسرع، ثم تطبيق منطقها الخاص لتقليل عدد الأعداد الناعمة المطلوبة.

النتائج التجريبية
أجرى المؤلفون تجارب تجريبية واسعة النطاق لمقارنة خوارزميتهم بخوارزمية حساب الجدولة القياسية والطرق الكلاسيكية الأخرى (مثل Baby-Step Giant-Step، وRho، وPohlig-Hellman).

• تسريع الأداء: بالنسبة للحقول الأولية المحدودة بطول 70 بت، أظهرت خوارزمية حساب الجدولة المزدوجة تسريعًا قدره 34 ضعفًا تقريبًا مقارنة بخوارزمية حساب الجدولة (2211 ثانية مقابل 75426 ثانية).
• القابلية للتوسع: تتسع فجوة الأداء مع زيادة طول البتات. فعند 50 بت، كانت الخوارزمية المقترحة أسرع بنحو 10 مرات؛ وعند 70 بت، كانت أسرع بأكثر من 30 ضعفًا.
• حد النعومة: أشارت التجارب إلى أن حد النعومة الأمثل للخوارزمية المقترحة يختلف قليلاً عن حساب الجدولة القياسي (غالباً حوالي $0.65B_i$ مقابل $0.5B_i$)، ولكن الخوارزمية المقترحة حافظت باستمرار على متوسط وقت تشغيل أقل عبر مختلف أطوال البتات (من 30 إلى 75 بت).

الأهمية والادعاءات
تضع الورقة خوارزمية حساب الجدولة المزدوجة كتحسين كبير على أحدث ما توصل إليه العلم لحل مسألة اللوغاريتم المنفصل في الحقول الأولية المحدودة. ويدعي المؤلفون أنه من خلال تقليل عدد اللوغاريتمات المنفصلة التي يجب حسابها، تحقق الخوارزمية زيادة كبيرة في سرعة الحوسبة. ويؤكدون أن هذا التحسين ليس مجرد تنويع على طرق النخل الموجودة، بل هو تغيير هيكلي في عملية الحل. ويشير المؤلفون إلى أن هذه النتائج قد تؤثر على كيفية اختيار الباحثين لمعايير الأمان للمخططات التشفيرية التي تعتمد على صعوبة مسألة اللوغاريتم المنفصل، حيث قد يكون مستوى الأمان الفعلي لحجم مفتاح معين أقل مما هو مقدر سابقًا بواسطة نماذج تعقيد حساب الجدولة القياسي.