توليد الأعداد الأولية الكبيرة

كتبه بركات يوم السبت, 15 آب 2015

تعرّف الأعداد الأولية بأنها مجموعة الأعداد الكلية الأكبر من واحد والتي تقبل القسمة على نفسها وعلى الواحد فقط، أوائل الأعداد الأولية 2، 3، 5، 7 وغيرها، وهي غير منتهية، الأعداد الأولية أعداد فريدة ولها تطبيقات مهمة في أمن المعلومات، فهي الأساس التي تعتمد عليه خوارزميات التشفير بالمفتاح المعلن، أو كمايعرف بالتشفير غير المتناظر.

حتى يكون التشفير فعال، فتُستخدم أعداد أولية كبيرة، كـ1024 بت وأكثر، إلا أن اللإشكال أنه كيف يتم توليد هذه الأعداد، فلا توجد آلية بسيطة لتوليدها، عمل جداول بأعداد أولية سبق توليدها عملية غير آمنة وغير ممكنة للأعداد الكبيرة كما سنرى لاحقاً، لكن هناك فكرة توليدها عن طريق "ضربة حظ"، قد تبدو فكرة غريبة إلا أنها فعالة، وهي الطريقة المستخدمة بالمناسبة.

أحد نظريات الأعداد التي أسهمت في التشفير هي نظرية العدد الأولي، حيث تنص على أنه لو كان لدينا دالة لعد الأعداد الأولية، اسمها $\pi(x)$ حيث تعطي عدد الأعداد الأولية الأصغر من $x$ (مثلاً $\pi(10) = 4$ لأن هناك 4 أعداد أولية أصغر من 10 وهي 2، 3، 5، 7) فإن النسبة بين هذه الدالة $\pi(x)$ و $x / \ln(x)$ تقترب للواحد (تبدأ تعطي نفس النتيجة) كلما كبرت قيمة $x$، رياضياً1:

$$\lim_{x \to \infty} \frac{\pi(x)}{x / \ln(x)} = 1$$

الدالة $\pi(x)$ فرضية ولم يتم التوصل لهكذا دالة (إن كانت موجودة)، إلا أن هذه النظرية تشير إلى أن $x / \ln(x)$ تقريب جيد للدالة $\pi(x)$، فكلما كبرت قيمة $x$ فتقترب $x / \ln(x)$ إلى $\pi(x)$، ويمكن ملاحظة هذا عن طريق الرسم البياني، الكود المستخدم لتوليد الصورة باستخدام Python مع matplotlib.

دالة عد الأعداد الأولية

من هذه النظرية يمكننا استنباط فائدتين تساهم في إعطائنا تصور عن استخدام البحث العشوائي لإيجاد الأعداد الأولية الكبيرة:

  • عدد الأعداد الأولية بين 2 و $n$ يساوي تقريباً $\frac{n}{\ln(n)}$.
  • احتمال إيجادنا لعدد عدد أولي اختير عشوائياً أصغر أو يساوي $n$ يساوي تقريباُ $\frac{1}{\ln(n)}$.

عند التطبيق، فإننا نتجاهل الأعداد الزوجية ونولد عدد فردي، فكل الأعداد الأولية، عدا 2، أعداد فردية، فمع التحسين الأخير، نجد أن احتمالية أن يكون عدد فردي عشوائي بحجم $N$ بت عدداً أولياً يساوي $\frac{2}{\ln(2^N)} = \frac{2}{N\ln(2)} \approx$.

مثلاً احتمالية إيجاد عدد أولي عن طريق عدد عشوائي بحجم 512 بت، تساوي تقريباً $\frac{2}{512\ln(2)} \approx 0.00563$، أي أن واحد من بين 177 (مقلوب الرقم السابق) عدد فردي عشوائي سيكون عدد أولي.

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

خوارزمية بسيطة:

n = random odd number
while n is not prime:
    n += 2

أشرت في البداية أنه لايكمن عملياً عمل جداول للأعداد الأولية، هناك بعض الجداول الموجودة في الإنترنت ولكنها للأعداد الأولية الصغيرة، لو أردنا أن نكتشف ونخزن كافة الأعداد الأولية التي يمكن توليدها من 1024 بت، فحسب النظرية السابقة فهناك أكثر من $\frac{2^{1024}}{1024 \ln(2)} \approx 2.5 \times 10^{305}$ عدد أولي، وهذا رقم هائل، لو أردنا تخزينها، فكل عدد 1024 بت سيحتاج إلى 128 بايت، فإننا سنحتاج إلى أكثر من $3.2 \times 10^{295}$ تيرابايت لتخزينها، أعتقد أنه يمكنني القول أنه مستحيل تخزينها.

الآن تتبقى مشكلة تحديد ما إذا كان العدد أولي أم لا، وهي مشكلة ليست بالسهلة، فحتى نتأكد من أن العدد أولي، علينا التأكد من أنه لايقبل القسمة إلا على نفسه وعلى الواحد، هذه الطريقة للتحقق طريقة حتمية، وهي بطيئة وغير مجدية، حيث تتطب كمية معالجة ليست بالهينة، إلا أن الطرق المستخدمة والفعالة لتحديد أوليّة العدد في الحقيقة أساليب احتمالية، أشهرها اختبار ميلر-رابن (Miller-Rabin)، فهي لاتستطيع أن تؤكد لك أن عدد ما عدد أولي، إلا أنها تستطيع أن تخبرك أن العدد $n$ عدد أولي بنسبة تأكد عالية، لعلي أكتب عنها في وقت لاحق.


  1. بعض المراجع تستخدم $\log(x)$، هنا لوغرتيم طبيعي أي للأساس $e$ وليس للأساس 10، لذا تجنب للخلط استخدمت $\ln(x)$