GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

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

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

ولحل هذه المشكلة، استخدم الفريق تقنية تسمى "التخمير المحاكي" (simulated annealing)، والتي تحاكي العملية الفيزيائية لتبريد المعادن لإزالة العيوب. في نسختهم الرقمية، يبدأ النظام بترتيب عشوائي للمفاتيح ومستوى عالٍ من "الحرارة"، مما يسمح للمفاتيح بالتحرك بحرية. ومع انخفاض درجة حرارة النظام، تستقر المفاتيح في نمط أكثر استقراراً. صمم الباحثون برنامجهم ليعمل على شريحة رسومات واحدة قوية، وهي NVIDIA GH200، والتي يمكنها إجراء آلاف العمليات الحسابية في وقت واحد. ولأن الخريطة الرياضية التي أنشأوها فارغة في معظمها — بمعنى أن معظم المفاتيح لا تتفاعل مع بعضها البعض — فقد نظموا العمل بحيث يركز الحاسوب فقط على الاتصالات الموجودة بالفعل. سمح هذا بتحديث العديد من المفاتيح في آن واحد دون التسبب في أخطاء، وهو إنجاز تطلب طريقة فرز ذكية لضمان عدم تغيير أي اثنين من المفاتيح المتفاعلة في اللحظة نفسها.

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

اختبر الباحثون مسار عملهم على أرقام تتراوح بين 16 و128 بت. وبينما نجحوا في تحليل أرقام مكونة من 100 بت في غضض دقائق، فقد أشاروا إلى أن الطريقة لا تزال تعتمد على خطوة بحث نهائية للعثور على الإجابة الدقيقة. وتعتمد سرعة هذه الخطوة النهائية بشكل كبير على مدى قرب التخمين الأولي من الحقيقة. وجد الفريق أن طريقتهم توفر باستمرار نقطة انطلاق أفضل بكثير من التخمينات الأقدم والأبسط، مما قلل الوقت اللازم للبحث النهائي بهامش كبير. كما أظهروا أن استخدام تقنية رياضية محددة تُعرف باسم "طريقة كوبيرسميث" (Coppersmith's method) يمكن أن يسرع العملية للأرقام الأكبر، مما قد يقلل الوقت من شهور إلى أيام للأرقام المكونة من 128 بت.

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