الطريقة الحتمية للتحقق من أولية العدد

كتبه بركات يوم الثلاثاء, 18 آب 2015

تحدثت في المقال السابق عن فكرة البحث العشوائي عن الأعداد الأوليّة، كما ذكرنا أنه يمكننا البحث عشوائياً في الأعداد الفردية حتى نجد عدد أولي مصادفة، حيث أن احتمال أن نجد عدداً أولياً بحجم 1024 بت يساوي $\frac{2}{1024\ln(2)} \approx 0.00282$، أي أن واحد من بين $\frac{1}{0.00282} \approx 355$ عددا نختبره يفترض أن يكون عدد أولي، قد يزيد أو ينقص، وهذا بسيط على الكمبيوترات الحديثة. لنراجع الخوارزمية السابقة:

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

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

جميع الأعداد الطبيعية الكلية إما أعداد أولية أو مركبة1، العدد الأولي هو الذي لايقبل القسمة إلا على نفسه وعلى الواحد، بينما العدد المركب يمكن تحليله إلى عوامله الأولية، مثلاً:

  • العدد 6 عدد مركب يمكن تحليله إلى عوامل أولية $6 = 3 \times 2$، معاملاته 2 و 3.
  • العدد 102 عدد مركب $102 = 2 \times 3 \times 17$، معاملاته 2 و 3 و 17.
  • العدد 1020 عدد مركب $1020 = 2^2 \times 3 \times 5 \times 17$، معاملاته 2 و 3 و 5 و 17.

إذا كان العدد $a$ يقبل القسمة على $b$ فيعبر عنها $b \mid a$ حيث تقرأ $b$ يقسم $a$، أي أن $a$ يقبل القسمة على $b$، وليس دوماً العكس، فهنا $3 \mid 6$ صحيحة لأن 3 يقسم 6، ولكن 6 لايقسم 3، يعبر عنها $6 \nmid 3$، أيضاً هذا التعبير يفيد أن $b$ يمكن ضربها بعدد المرات $c$ لنحصل على $a$، هكذا $a = bc$.

يمكن أيضاً التعبير عن قابلية القسمة، $a \equiv 0\ \pmod b$ وتفيد أن باقي قسمة $a$ على $b$ تساوي باقي قسمة $0$ على $b$، أي صفر، طريقتين مختلفة تفيد نفس الشيء، كون عددما عدد مركب، يعني أنه يقبل القسمة على أحد عوامله الأولية، بينما العدد الأولي ليس له عوامل أولية لأنه عدد أولي.

أحد أبسط الأساليب للتحقق من أوليّة العدد هي التأكد أن جميع الأعداد التي تسبق هذا العدد بدءً من 2 لاتقبل القسمة عليه، حيث تعتمد هذه الطريقة على "اختبار القسمة" (trial division)، مثلاً الأعداد قبل 5 هي 2، 3، 4 وجميعها لاتقبل القسمة عليه، لذا فهو عدد أولي، بينما 6 قبلها 2، 3، 4، 5، سنجد أن 2 و 3 تقبل القسمة على 6، لذا فهي عدد مركب، يكفي أن نجد عدد واحد، باستثناء الواحد والعدد نفسه، يقبل القسمة على هذا العدد، فهو حتمياً عدد مركب، إذا لم نجد هكذا عدد فهو حتمياً عدد أولي.

نسخة أولية لخوارزمية اختبار القسمة:

def isprime(n):
    if n <= 1:
        return False
    i = 2
    while i < n:
        if n % i == 0:
            return False
        i += 1
    return True

هذه الخوارزمية بسيط وسهلة، لكنها قليلة الكفاءة عند استخدامها للأعداد الكبيرة، فلو كان $n$ فعلاً عدد أولي، فهذه الخوارزمية تحتاج وقت طويل لتتأكد من ذلك، فهي ستجرب أن تقسم $n$ على الأعداد من $2 \dots n-1$.

لكن لو لاحظت أي عدد مركب، فهناك على الأقل عددين يمكن ضربها ببعض لنحصل على هذا العدد، فمثلاً $6 = 3 \times 2$ و $102 = 52 \times 2$، أي أنه يمكن كتابته بالشكل $n = pq$، أحد هذين العددين على الأقل يجب أن يكون أقل من $\sqrt{n}$، ويستحال أن يكون كلاهما أكبر من $\sqrt{n}$، فلو كان هناك عددين $p$ و $q$ أكبر من $\sqrt{n}$، فضربهما أكبر من $n$، تذكر أن $\sqrt{n} \times \sqrt{n} = n$، لذا فنحن فعلاً لسنا بحاجة لتجربة الأعداد حتى $n - 1$، فيمكننا أن نتحقق من الأعداد حتى $\sqrt{n}$، لأنه لو كان هناك أعداد تقسم العدد $n$ فأحدها على الأقل يجب أن يكون أقل أو يساوي $\sqrt{n}$، وإذا لم نجد قاسم للعدد $n$، فهنا $n$ حتماً عدد أولي، اختصرنا عدد كبير من الخطوات، فلتجربة أوليّة العدد 313، وهو عدد أولي، فبدلاً من تجربة 310 أرقام، يمكننا التأكد من أوليته بتجربة $\left \lfloor \sqrt{313} \right \rfloor - 1 = 16$2 رقم.

from math import sqrt, floor

def isprime(n):
    i = 2
    if n <= 1:
        return False
    limit = floor(sqrt(n))
    while i < limit:
        if n % i == 0:
            return False
        i += 1
    return True

يمكن أيضاً تحسين هذه الخوارزمية عن طريق تقليل عدد الأعداد التي يلزمنا تجربتها للنصف، فالأعداد الأولية كلها أعداد فردية باستثناء العدد 2، يمكننا أن نستثني الأعداد الزوجية عن طريق محاولة حساب باقي قسمة العدد على 2 حتى نستثني الأعداد الزوجية بين $3 \dots \sqrt{n}$، ثم نجرب أن نقسمة بعدها على الأعداد الفردية الباقية، فقط بدل i += 1 بـi += 2، فكل عدد فردي يليه عدد زوجي ثم عدد فردي:

from math import sqrt, floor

def isprime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False
    limit = floor(sqrt(n))
    i = 3
    while i <= limit:
        if n % i == 0:
            return False
        i += 2
    return True

الآن يمكننا تطبيق خوارزمية توليد الأعداد الأولية:

from math import sqrt, floor
from random import getrandbits

def isprime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False
    limit = floor(sqrt(n))
    i = 3
    while i <= limit:
        if n % i == 0:
            return False
        i += 2
    return True

def newprime(bits):
    p = getrandbits(bits) | 1   # or'ing with 1 to make it odd
    while not isprime(p):
        p += 2
    return p

تجربتها، فقط استدع newprime ومرر لها عدد البتات التي تريدها:

>>> newprime(8)
37
>>> newprime(8)
163
>>> newprime(16)
6709
>>> newprime(16)
53917
>>> newprime(32)
3695844689
>>> newprime(32)
1380647717
>>>

ربما تبدو هذه خوارزمية isprime فعالة لاختبار الأعداد الأولية الصغيرة، 3695844689 يعتبر صغير بالمناسبة، لكن جرب توليد رقم أولي بحجم 64 بت أو أكثر، ستجده أنها تستغرق وقت طويل جداً، يصل حتى لقرون، وهذه المشكلة مع الخوارزميات الحتمية، فتعقيد الخوارزمية السابقة $\mathrm{O}(\sqrt{n})$ ولو عبرنا بـ$n$ بعدد البتات $\alpha = \left \lceil \log_2{n} \right \rceil $ وحلننا المعادلة بالنسبة لـ$n$ (سنتجاهل دالة السقف لتبسيط الحساب):

$$\begin{align} \log_2{n} &= \alpha \\ 2^{\log_2{n}} &= 2^{\alpha} \\ n &= 2^{\alpha} \end{align}$$

عوض $2^{\alpha}$ في $\mathrm{O}(\sqrt{n})$ ستجد أنها تساوي:

$$ \begin{align} \mathrm{O}(\sqrt{n}) &= \mathrm{O}(\sqrt{2^{\alpha}}) \\ &= \mathrm{O}((2^{\alpha})^{\frac{1}{2}}) \\ &= \mathrm{O}(2^{\frac{\alpha}{2}}) \end{align} $$

تعقيد هذه الخوارزمية بالنسبة لعدد البتات $\mathrm{O}(2^{\frac{\alpha}{2}})$، أي أنها ذات تعقيد أسي، وهو أسواء أنواع الخوارزميات، فالزمن الازم لتعطي هذه الخوارزمية نتيجة في أسواء الحلات، ينمو بسرعة أسرع من السرعة التي تتطور بها قدراتنا الحاسوبية، المشاكل التي لاتحلها إلا خوارزميات أسية تندرج تحت التعقيد NP، لو كان تعقيدها مثلاً يمثل بكثيرة حدود، فرضاً $\mathrm{O}(n^{12})$، هنا تعقيدها كبير إلا أنها تضل تحت التعقيد P، فالمسألة مسألة زمن حتى تصل قدرتنا الحاسوبية إلى حلها بسرعة مهما كان حلها بطئياً حالياً3.

حتى 2002، كان الإختبار الحتمي لأسية العدد يندرج تحت التعقيد NP، حتى اكتشفت الخوارزمية AKS وأثبتت أن اختبار أوليّة العدد مشكلة من نوع P، تعقيد هذه الخوارزمية $\mathrm{O}(\ln^{12+\epsilon}{p})$ وحُسّن إلى $\mathrm{O}(\ln^{6+\epsilon}{p})$، إلا أن تعقيدها يبقى عالي، فهناك اختبارات احصائية أسهل للفهم وتخبرك أن العدد أولي باحتمالية عالية تكفي لأن تستخدم في التطبيقات العملية.


  1. الواحد بالمناسبة ليس عدد أولي وليس عدد مركب أيضاً، حيث كان يعد عدداً أولياً ثم اتفق لاحقاً على إزالته من مجموعة الأعداد الأولية نظراً للمشاكل التي تترتب على إضافته، اطلع على النظرية الأساسية للحساب

  2. الرمز $\left \lfloor n \right \rfloor$ يعني دالة الجزء الصحيح floor من $n$ وهو أول عدد صحيح أصغر أو يساوي $n$، فمثلاً $\left \lfloor 3 \right \rfloor = 3$ و $\left \lfloor 3.4 \right \rfloor = 3$ و $\left \lfloor 3.6 \right \rfloor = 3$، وقريبتها دالة سقف العدد أو ceil ويرمز لها $\left \lceil n \right \rceil$ وتعطي أول عدد صحيح أكبر أو يساوي $n$، مثلاً $\left \lceil 3 \right \rceil = 3$ و $\left \lceil 3.4 \right \rceil = 4$ و$\left \lceil 3.6 \right \rceil = 4$، لاتخلط بينهما وين التقريب. 

  3. واحدة من مسائل الألفية التي طرحها معهد كيلاي للرياضيات تسمى P vs NP، حيث كانت هناك مشاكل من نوع NP وجد لها حلول في P، ومسائل أخرى من نوع NP لم يوجد بعد لها حل في P، السؤال هو هل يمكن الإثبات أن جميع المشاكل في NP لها حلول في P، أو حتى النفي، بمعنى أنه ليس شرطاً، فبعض المشاكل في NP ليس لها حل في P؟.