اختبار فيرما لأولية العدد

كتبه بركات يوم الثلاثاء, 05 تـمـوز 2016

تحدثنا في مقال سابق عن أحد الطرق الحتمية للتحقق من أولية العدد وهي اختبار القسمة، حيث تخبرك أن العدد $n$ عدد أولي أم لا، ورأينا أن هذه الطريقة غير مجدية، نظراً لتعقيدها الأسي، حيث تكافئ محاولة تحليل العدد لعوامله الأولية.

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

الإختبارات الإحصائية لا تستطيع أن تؤكد لك أن العدد $n$ عدد أولي، لكنها تخبرك أن العدد $n$ عدد أولي بنسبة احتمال عالية جداً تقترب جداً للواحد1، إذا فعلاً لم يكن عدد أولي فحظك أسوأ من حظ شخص يمشي في الطريق وسقط على رأسه نيزك عرضه 10 كم :)، لذا فالإحتمالية عالية جداً لدرجة تسمح لنا في استخدام الاختبارات الإحصائية في أهم التطبيقات الأمنية، هذا بالإضافة لسرعة تلك الاختبارات.

اختبار فيرما

يعتمد اختبار فيرما على نظرية فيرما الصغرى، حيث تنص على أنه لو كان لدينا عدد أولي $n$ ولم تكن $a$ من مضاعفات هذا العدد، بصيغة أخرى $\gcd(a, n) = 1$ أو $n \not\mid a$، فإن:

$$a^n \equiv a \pmod{n}$$

بما أن $\gcd(a, n) = 1$ فإنه يمكننا قسمة كلا الطرفين على $a$ يصبح شكل التكافؤ:

$$a^{n - 1} \equiv 1 \pmod{n}$$

لاحظ أن هذا التكافؤ يجب أن يتحقق إذا كانت $n$ عدد أولي.

مثلاً مع 7، سنجد أن النتيجة دوماً $1 \pmod{7}$:

$$ \begin{matrix} a & \mid & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline a^{7-1}\pmod{7} & \mid & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} $$ لو جربنا 8، سنجد:

$$ \begin{matrix} a & \mid & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline a^{8-1}\pmod{8} & \mid & 1 & 0 & 3 & 0 & 5 & 0 & 7 \end{matrix} $$

في اختبار فيرما، لدينا عدد $n$، ونختار عدد عشوائي $1 < a < n$، ونحسب $a^{n - 1} \pmod{n}$، في حال كانت $a^{n - 1} \not\equiv 1 \pmod{n}$، فلا يمكن أن يكون العدد $n$ عدد أولي، ويسمى العدد $a$ شاهد فيرما على أن العدد $n$ مركب، في حال كان $a^{n - 1} \equiv 1 \pmod{n}$، فاحتمال أن يكون العدد عدد مركب وأن يخطئ الإختبار، غالباً، أقل من $1/2$، إذا كانت $a^{n - 1} \not\equiv 1 \pmod{n}$، ولم يكن $n$ عدد أولي، فإن $a$ يسمى كاذب فيرما.

في هذا الإختبار نكرر التجربة باختبار $a$ آخر $i$ مرة، ليصبح احتمال الخطأ بأن يكون $n$ عدد مركب أقل من $(1/2)^i$، لو أجريت الإختبار 100 مرة، فسيكون قرابة $7.89 \times 10^{-31}$، احتمال صغير للغاية.

مثال باستخدام Python (هنا pow(a, n - 1, n) تعني $a^{n - 1} \pmod{n}$):

import random

def fermat_test(n, a):
    return pow(a, n - 1, n) == 1

def is_probable_prime(n, rounds=100):
    for _ in range(rounds):
        a = random.randint(2, n - 1)
        if not fermat_test(n, a):
            return False
    return True

ليصبح مولد الأعداد الأولية:

import random

def fermat_test(n, a):
    return pow(a, n - 1, n) == 1

def is_probable_prime(n, rounds=100):
    for _ in range(rounds):
        a = random.randint(2, n - 1)
        if not fermat_test(n, a):
            return False
    return True

def newprime(bits):
    p = random.getrandbits(bits) | 1 # odd number
    while not is_probable_prime(p):
        p += 2
    return p

تجربة توليد أعداد أولية عشوائية (لاحظ السرعة في توليد الأعداد):

>>> newprime(128)
107172316217927044889086758619061220019
>>> newprime(256)
60545300825547251219589655560052863700774363949472696785276354076153335006737
>>> newprime(512)
9201893249374241367608950287470623063915495658497660782699255697898079348906866413055707151496009054714010315424450692371015325578512381016273219237180151
>>>

اختبار فيرما كاد ليكون الاختبار المثالي نظراً لسهولة فهمه وإجراءه، إلا أن هناك مشكلة معه ومع مجموعة معينة من الأعداد تسمى أعداد كارميكائيل، هذه الأعداد أعداد مركبة وليست أولية، لها على الأقل ثلاثة عوامل أولية، وتحقق العلاقة:

$$a^{n - 1} \equiv 1 \pmod{n}$$

لكل عدد كارميكائيل $1 < a < n$ أولي فيما بينه وبين $n$، أي $\gcd(a, n) = 1$، أول هذه الأعداد العدد المركب $561 = 3 \times 11 \times 17$، هنا قائمة لأوائل هذه الأعداد.

لاتخلط بين نظرية فيرما واختبار فيرما، قبل أن نوضح مشكلة اختبار فيرما مع أعداد كارميكائيل هناك شيئين يجب أن تفهمهما:

  • نظرية فيرما الصغري ليست خطأ، بل تخبر أن تلك العلاقة صحيحة دوماً مع الأعداد الأولية، لكنها لاتدعي أنها تنطبق على الأعداد الأولية فقط، فقد تنطبق على أعداد غير أولية، وهي أعداد كارميكائيل، لكن ان كان العدد عدد أولي فيجب أن تنطبق.
  • ففي اختبار فيرما نحن لانتجاهل $\gcd(a, n) \ne 1$، لذا لو أجرينا اختبار فيرما وصادفنا أحد عوامل عداد كارميكائيل الأولية، أو عدد مضروب بأحد عوامله فسيكتشف الإختبار أنه عدد غير أولي.

مشكلة اختبار فيرما أنه لو كان $n$ عدد كارميكائيل ونحن نجري عدد $i$ محدود من المحاولات كمئة محاولة، فاحتمال قليل أن نجد $a$ بحيث تكون أحد عوامل عدد كارميكائيل الأولية أو من مضاعفات هذا العامل الأولي.

هذه قائمة لأول أعداد كارميكائيل، قارن بين عدد الشواهد لأول خمسة أعداد كارميكائيل، وبين عدد الشواهد لأعداد مركبة عادية:

4609    99.89%
1858    99.89%
6776    99.91%
8922    99.98%
8799    99.90%

عدد الشواهد كثير جداً، بينما مع أعداد كارميكائيل، المركبة، عدد الشواهد منخفض للغاية:

561     42.78%
1105    30.41%
1729    24.99%
2465    27.26%
2821    23.40%

خذ مثلاً العدد $410041 = 41 \times 73 \times 137$، والذي له أقل عدد من الشواهد، 4.48%، في تلك القائمة، لو جربته مع الخوارزمية السابقة:

>>> i = 0
>>> while not is_probable_prime(410041):
...     i += 1
...
>>> i
167
>>>

أي أنه في المحاولة رقم 167 فشل الاختبار في اكتشاف أنه عدد مركب، في أحد تجاربي فشل بعد المحاولة 21، بمعنى أن احتمال الخطأ يكبر بكثير إذا كانت $n$ عدد كارميكائيل.

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

اختبار ميلر-رابن هو الإختبار القياسي المستخدم حالياً في معظم مكتبات التشفير، حيث يدمج نظرية فيرما مع باقي القسمة التربيعية quadratic residue للعدد الأولي بطريقة ذكية تتجاوز مشكلة أعداد كارميكائيل، لن أتحدث عنه هنا كما قلت، لكن سأتركه لوقت لاحق.


  1. أي 100%، حيث أن $1.0 \times 100 = 100\%$