مثالان: التحليل إلى العوامل والقواسم المشتركة الكبرى

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

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

لنوضح ذلك أكثر، دعنا نتعرف على مشكلة تحليل الأعداد الصحيحة إلى عواملها الأولية.

تحليل الأعداد الصحيحة إلى عواملها الأولية

المدخل: عدد صحيح $N\geq 2$
المخرج: التحليل الأولي لـ$N$

بـالتحليل الأولي لـ$N$ نعني قائمة بالعوامل الأولية لـ$N$ والأسس التي يجب رفعها إليها للحصول على $N$ بالضرب. مثلاً، العوامل الأولية لـ$12$ هي $2$ و$3$، وللحصول على $12$ نأخذ حاصل ضرب $2$ مرفوعاً للأس $2$ في $3$ مرفوعاً للأس $1$.

$$12 = 2^2 \cdot 3$$

بغض النظر عن ترتيب العوامل الأولية، يوجد تحليل أولي واحد فقط لكل عدد صحيح موجب $N\geq 2$، وهذه حقيقة تُعرف بـالنظرية الأساسية في الحساب.

بعض العروض التوضيحية البسيطة بلغة Python ستكون مفيدة لمزيد من الشرح حول التحليل الأولي ومفاهيم أخرى ذات صلة. تحتاج إلى الاستيرادات التالية لهذه العروض.

# Added by doQumentation — required packages for this notebook
!pip install -q sympy

import math
from sympy.ntheory import factorint

دالة factorint من حزمة SymPy للرياضيات الرمزية في Python تحل مشكلة التحليل الأولي لأي مدخل $N$ نختاره. مثلاً، يمكننا الحصول على التحليل الأولي لـ12، وهو بالطبع يتوافق مع التحليل أعلاه.

N = 12
print(factorint(N))

{2: 2, 3: 1}

تحليل الأعداد الصغيرة كـ$12$ أمر سهل، لكن حين يكبر العدد $N$ المراد تحليله تصبح المشكلة أصعب. مثلاً، تشغيل factorint على عدد أكبر بكثير يُسبِّب تأخيراً قصيراً لكنه ملحوظ على حاسوب شخصي اعتيادي.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

{3: 2, 74519450661011221: 1, 5073729280707932631243580787: 1}

لقيم $N$ أكبر من ذلك، تصبح الأمور مستحيلة عملياً على حد علمنا. على سبيل المثال، أطلقت مختبرات RSA تحدي RSA Factoring Challenge بين عامَي 1991 و2007، وعرضت جائزة نقدية قدرها 100,000 دولار لتحليل الرقم التالي الذي يتكون من 309 رقماً عشرياً (أو 1024 بت بالنظام الثنائي). لم تُستلَم الجائزة قط وعوامله الأولية لا تزال مجهولة.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

لا داعي لتشغيل factorint على RSA1024، فلن يُنهي العملية في حياتنا.

أسرع خوارزمية معروفة لتحليل الأعداد الصحيحة الكبيرة تُعرف بـمنخل حقل الأعداد. كمثال على استخدام هذه الخوارزمية، جرى تحليل رقم التحدي RSA250 الذي يتكون من 250 رقماً عشرياً (أو 829 بت بالنظام الثنائي) باستخدام منخل حقل الأعداد عام 2020. تطلّبت العملية آلاف السنوات-المعالج، موزَّعة على عشرات الآلاف من الأجهزة حول العالم. يمكننا هنا أن نُقدِّر هذا الجهد بالتحقق من الحل.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

يعتمد أمان نظام التشفير بالمفتاح العام RSA على الصعوبة الحسابية لتحليل الأعداد الصحيحة، بمعنى أن خوارزمية فعّالة للتحليل الأولي ستكسر هذا النظام.

الآن دعنا ننظر في مشكلة مترابطة لكنها مختلفة تماماً، وهي حساب القاسم المشترك الأكبر (GCD) لعددين صحيحين.

القاسم المشترك الأكبر (GCD)

المدخل: عددان صحيحان غير سالبَين $N$ و$M$، أحدهما على الأقل موجب
المخرج: القاسم المشترك الأكبر لـ$N$ و$M$

القاسم المشترك الأكبر لعددين هو أكبر عدد صحيح يقسم كليهما بالتساوي.

هذه المشكلة سهلة الحل بالحاسوب — تكلفتها الحسابية تقريباً مشابهة لتكلفة ضرب العددَين معاً. دالة gcd من موديول math في Python تحسب القاسم المشترك الأكبر لأعداد أكبر بكثير من RSA1024 في لمحة بصر. (في الواقع، RSA1024 هو القاسم المشترك الأكبر للعددين في هذا المثال.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

هذا ممكن لأن لدينا خوارزميات فعّالة جداً لحساب القواسم المشتركة الكبرى، أشهرها خوارزمية إقليدس التي اكتُشفت منذ أكثر من 2,000 عام.

هل يمكن أن توجد خوارزمية سريعة للتحليل الأولي لم نكتشفها بعد، تتيح تحليل أعداد كبيرة كـRSA1024 في لمحة بصر؟ الجواب نعم. رغم أننا قد نتوقع أن خوارزمية فعّالة للتحليل بسيطة وأنيقة كخوارزمية إقليدس لحساب القواسم المشتركة الكبرى كان يجب اكتشافها بحلول الآن، لا شيء يستبعد وجود خوارزمية كلاسيكية سريعة جداً للتحليل الأولي، سوى أننا فشلنا في إيجادها حتى الآن. قد تُكتشف غداً — لكن لا تحبس أنفاسك. أجيال من علماء الرياضيات وعلوم الحوسبة بحثوا، وتحليل أعداد كـRSA1024 لا يزال خارج متناولنا.