مقدمة لحسابات باقي القسمة

كتبه بركات يوم الإثنين, 02 تشرين الثاني 2015

حسابات باقي القسمة modular arithmetic، جزء من نظرية الأعداد Number theory والتي تدرس الأعداد الصحيحة كالأعداد الأولية، وكذلك علاقات وخصائص الأعداد، تنتمي نظرية الأعداد لفرع أكبر من فروع الرياضيات يسمى الرياضيات البحتة، وهو القسم الذي يدرس الرياضيات لأجل الرياضيات حتى لو لم يكن لها تطبيق واضح.

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

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

حسابات باقي القسمة هي الحسابات التي تهتم بإجراء العمليات الحسابية في مجموعة منتهية من الأعداد الصحيحة $\mathbb{Z}$، أي أن عملنا محصور في مجموعة الأعداد الصحيحة $\mathbb{Z}$، ولايهمنا الأعداد الحقيقية $\mathbb{R}$ مثل 3.35 وغيرها من الأعداد والمجموعات، والمقصود بمجموعة منتهية، أننا سنجري العمليات الحسابية الأساسية كالجمع والطرح والضرب وغيرها ويكون الناتج في عدد محدود من الأعداد مثل $\mathbb{Z}_n = \{0, 1, \cdots, n - 1\}$ بدلاً من مجموعة الأعداد الصحيحة كلها, يمكنك أن تجري جميع العمليات الحسابية مثل الجمع والضرب لكن الناتج سيكون محصوراً في $\mathbb{Z}_n$، كثير من المراجع تستخدم $\mathbb{Z}/n\mathbb{Z}$ أو $\mathbb{Z}/n$ بدلاً من $\mathbb{Z}_n$، سأستخدم الرمز الأخير لأنه أبسط، لكن تذكر أن الرمز الأول والثاني يشيران لنفس الشيء.

بعض المفاهيم المهمة عند التعامل مع حسابات باقي القسمة:

قابلية القسمة

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

القاسم المشترك الأكبر

القاسم المشترك الأكبر للعددين الصحيحين $a$ و $b$ هو أكبر عدد يقسم العددين قسمة صحيحة، ويعبر عنه $\gcd(a, b)$، حيث أن $\gcd$ اختصار لعبارة القاسم المشترك الأكبر، greatest common divisor، بعض مراجع الرياضيات تستخدم $(a, b)$، لكن لتجنب الخلط بينها وبين النقطة فسنستخدم الأولى، مثلاً القاسم المشترك الأكبر للعددين 21 و 14 هو $\gcd(21, 14) = 7$.

إذا كان القاسم المشترك الأكبر للعددين الصحيحين $a$ و $b$ يساوي واحد، $\gcd(a, b) = 1$، فإننا نقول أن العددين $a$ و $b$ أوليان في مابينهما co-primes، مثلاً 52 و 35 أوليان فيما بينهما لأن $\gcd(52, 35) = 1$، لايشترط أبداً أن يكونان أوليان حتى يكونان أوليان فيما بينهما، فالعددين 35 و 52 غير أوليان.

في حال كان أحد العددين عدد أولي والعدد الآخر ليس من مضاعفات هذا العدد الأولي فالقاسم المشترك الأكبر بينهما دوماً واحد، مثل العدد الأولي 19 والعدد غير الأولي 4، $\gcd(19, 4) = 1$.

أيضاً القاسم المشترك بين العدد والعدد نفسه، هو العدد نفسه $\gcd(a, a) = a$.

يمكن إيجاد القاسم المشترك الأكبر يدوياً باستخدام خوارزمية إقليدس، مثلاً لإيجاد القاسم المشترك الأكبر بين 32 و 12، فيمكننا عملها هكذا:

$$ \begin{align} 32 &= 12 \times 2 + 8 \\ 12 &= 8 \times 1 + \underline{4} \\ 8 &= 4 \times 2 + 0 \end{align} $$

فور وصولنا للصفر نتوقف، الباقي الذي قبله هو القاسم المشترك الأكبر، $\gcd(32, 12) = 4$.

هناك عدة خوارزميات أخرى لإيجاد القاسم المشترك الأكبر مثل خوارزمية القاسم المشترك الأكبر الثنائية وغيرها، لكننا لن نتطرق لها، فعند التعامل مثلاً مع RSA، فسنتعامل مع أرقام كبيرة ونحتاج مكتبة تدعم الأرقام الكبيرة bignum والتي غالباً ماتوفر وظيفة سريعة لإيجاد القاسم المشترك الأكبر، في Java مثلاً، يمكنك حساب القاسم المشترك الأكبر باستخدام java.math.BigInteger#gcd، ايجاد $\gcd(123456^{55}, 642930^{55})$:

import java.math.BigInteger;

public class Gcd {
    public static void main(String[] args) {
        BigInteger a = new BigInteger("123456").pow(55);
        BigInteger b = new BigInteger("642930").pow(55);

        BigInteger gcd = a.gcd(b);

        System.out.printf("gcd(a, b) = %s\n", gcd);
    }
}

مع Python، هناك الدالة fractions.gcd:

>>> from fractions import gcd
>>>
>>> gcd(123456**55, 642930**55)
6285195213566005335561053533150026217291776
>>>

القسمة الصحيحة

كل عدد صحيح $a$ يمكن كتابته بالصيغة التالية $a = m \times k + r$، حيث أن حيث أن $m$ القاسم، و $k$ خارج القسمة، و $r$ باقي القسمة، وكلها أعداد صحيحة $a, r, k, m \in \mathbb{Z}$، مثلاً، لو قسمنا 33 على 5 قسمة صحيحة1 فسيعطينا $33 \setminus 5 = 6$، وخارج القسمة2 $33 \bmod 5 = 3$، يمكن اعادة كتابة 33 بالصيغة التالية:

$$\underset{a}{33} = \underset{m}{5} \times \underset{k}{6} + \underset{r}{3}$$

إذا كان $m \mid a$، فإن باقي القسمة دوماً صفر، أي $a = m \times k$، مثلاً $6 = 2 \times 3$.

مثل ما أن خارج القسمة $k$ يمكن الحصول عليه عن طريق القسمة الصحيحة $k = a \setminus m$، فإن الباقي $r$ يمكن الحصول عليه بعملية باقي القسمة $r = a \bmod m$.

باقي القسمة

إذا كتبنا $a \equiv b \pmod{m}$، فإن هذا يعني أن باقي قسمة $a$ على $m$ يساوي باقي قسمة $b$ على $m$، أي $a \bmod m = b \bmod m$، ونقرأها بقولنا أن $a$ يكافئ $b$ بالنسبة للعدد $m$.

استخدام علامة التكافؤ $\equiv$ بدل علامة المساواة $=$ عائد أن علاقة باقي القسمة $\bmod{m}$ علاقة تكافؤ، غالباً ما يستخدم الرمز $a \sim b$ أو $a \equiv b\,(\textrm{R})$ أو حتى $a \equiv_\textrm{R} b$، حيث تعني أن $a$ و $b$ متساويين وفق العلاقة $\textrm{R}$، مثلاً لو قلنا أن لدينا مجموعة $\textrm{C}$ من السيارات ولدينا سيارتين من هذه المجموعة $a, b \in \textrm{C}$ وعرفنا العلاقة $\textrm{R}$ بأنها "لها نفس اللون"، فجملة $a \equiv b\,(\textrm{R})$ تعني أن السيارة $a$ لها نفس لون السيارة $b$، لاتتوقف كثير على الرمز، فالموضوع بسيط.

غالباً مايكتب باقي القسمة كالتالي $a \equiv r \pmod{m}$ حيث أن $a = m \times k + r$، وتعني أيضاً أن $m \mid (a - r)$، فلو أعدت ترتيب المعادلة السابقة إلى $(a - r) / m = k$ ستجد أنها تعطي عدد صحيح $k$، لكن تذكر أن اهتمامنا في حسابات باقي القسمة يتمحور حول الباقي $r$ وليس حول خارج القسمة $k$.

في الصيغة $a \equiv r \pmod{m}$ العدد $a$ في اليسار، والباقي $r$ بالنسبة للعدد $m$ دوماً في اليمين، ودوماً $0 \leq r < m$، بعنى الباقي أصغر من القاسم، عادةً لايشار للعديدن $a$ و $r$ هكذا بدون الإشارة إلى $m$، بل يشار لهما هكذا $a \pmod{m}$ وكذلك $r \pmod{m}$ وذلك للتأكيد على أننا نعمل في المجموعة $\mathbb{Z}_m$.

إذا أردت التحويل من الصيغة الثنائية $r = a \bmod m$ إلى الصيغة الجديدة، فيمكنك كتابتها هكذا $a \equiv r \pmod{m}$، لكن تذكر أن المعنى الحقيقي للصيغة الثانية يكافئ $r \bmod m = a \bmod m$، لكن لأن الباقي دوماً $0 \le r < m$، إذاً فقيمة $r = r \bmod m$، مثلاً $2 = 2 \bmod 10$.

مثال على باقي القسمة، هنا $7 \equiv 2 \pmod{5}$ نقول أن $7 \pmod{5}$ تكافئ $2 \pmod{5}$ لأن $5 \mid (7 - 2)$ حيث $7 = 5 \times 1 + 2$، لكن هنا $9 \not\equiv 2 \pmod{5}$ فنقول أن $9 \pmod{5}$ لاتكافئ $2 \pmod{5}$ وذلك لأن $5 \nmid (9 - 2)$، فلا يوجد صحيح $k$ يحقق المعادلة $9 = 5 \times k + 2$.

هنا $6 \equiv 1 \pmod{5}$، وكذلك $11 \equiv 1 \pmod{5}$، وأيضاً $16 \equiv 1 \pmod{5}$، يمكننا كتابة $6 \pmod{5} \equiv 11 \pmod{5} \equiv 16 \pmod{5} \equiv 1 \pmod{5}$ أو للإختصار $6 \equiv 11 \equiv 16 \equiv 1 \pmod{5}$.

خصائص باقي القسمة

التحويل من السالب للموجب

باقي القسمة يمكن أن يكون سالب كالتالي $-a \pmod{m}$، يمكن تحويله للموجب هكذا $-a \equiv m - a \pmod{m}$، حيث أنهما متكافئان.

مثلاً $-4 \equiv 5 - 4 \equiv 1 \pmod{5}$، في حال ظهر لك رقم سالب أيضاً كما في $-13 \pmod{5}$، فنكرر هذه الخطوة حتى يذهب السالب:

$$ \begin{align} -13 &\equiv 5 - 13 \\ &\equiv -8\\ &\equiv 5 - 8 \\ &\equiv -3\\ &\equiv 5 - 3 \\ &\equiv 2 \pmod{5} \end{align} $$

سبب هذه الخاصية عائد لأنه عند القسمة على عدد سالب، مثل قسمة $-13$ على $5$، فكل التالي نواتج صحيحة للقسمة:

$$ \begin{align} a &= k \times m + r \\\\ -13 &= -3 \times 5 + 2 \\ &= -2 \times 5 + -3 \\ &= -1 \times 5+ -8 \\ \end{align} $$

فيمكنك أن تأخذ باقي القسمة الموجب أو السالب، لكنني لا أفضل السالب لأنه يربك في كثير من الأحيان.

خاصية الجمع

إذا كان $a_1 \equiv r_1 \pmod{m}$، وكان $a_2 \equiv r_2 \pmod{m}$، فإن $a_1 + a_2 \equiv r_1 + r_2 \pmod{m}$ دوماً صحيحة، مثلاً:

$$ \begin{align} 10 &\equiv 4 \pmod{6} \\ 9 &\equiv 3 \pmod{6} \\ \end{align} $$

فإن جمعهما دوماً صحيح $10 + 9 \equiv 4 + 3 \pmod{6}$ والتي تكافئ $19 \equiv 7 \equiv 1 \pmod{6}$.

خاصية الطرح

$a_1 \equiv r_1 \pmod{m}$، وكان $a_2 \equiv r_2 \pmod{m}$، فإن $a_1 - a_2 \equiv r_1 - r_2 \pmod{m}$ دوماً صحيحة مثلاً:

$$ \begin{align} 24 &\equiv 5 \pmod{19} \\ 22 &\equiv 3 \pmod{19} \\ \end{align} $$

فإن طرحمها دوماً صحيح $24 - 22 \equiv 5 - 3 \pmod{6}$، ويساوي $2 \equiv 2 \pmod{6}$.

خاصية الضرب

خاصية الضرب، إذا كان $a_1 \equiv r_1 \pmod{m}$، وكان $a_2 \equiv r_2 \pmod{m}$، فإن ضربهما $a_1\,a_2 \equiv r_1\,r_2 \pmod{m}$ دوماً صحيح، مثلاً:

$$ \begin{align} 6 &\equiv 0 \pmod{3} \\ 7 &\equiv 1 \pmod{3} \\ \end{align} $$

فإن ضربهما $6 \times 7 \equiv 1 \times 0 \pmod{3}$ أي $42 \equiv 0 \pmod{3}$.

إذا ضربت عدد ثابت صحيح $k$ في طرفي $a \equiv r \pmod{m}$ فإن $a\,k \equiv r\,k \pmod{m}$ دوماً صحيحة، مثلاً $9 \equiv 2 \pmod{7}$، ضربهما بالعدد $3$ سيعطينا $9 \times 3 \equiv 2 \times 3 \pmod{7}$، أي $27 \equiv 6 \pmod{7}$.

خاصية القسمة

القسمة ليست صحيحة دوماً، فإما أن القسمة ستعطيك عدد غير صحيح، أو تعطي نتيجة خاطئة، مثلاً هنا $4 \equiv 0 \pmod{2}$، لو قسمت الطرفين على 4 فسيعطينا $1 \not\equiv 0 \pmod{2}$، كما ترى، فالتكافؤ غير صحيح.

الحالة الوحيدة والمهمة التي تستطيع قسمة طرفي التكافؤ $a\,k \equiv r\,k \pmod{m}$ على العدد $k$ إذا كان $\gcd(k, m) = 1$، أي أنهما أوليان في مابينهما، هذه خاصية مهمة حيث سنراها كثيراً لاحقاً.

مثلاً هنا $8 \equiv 2 \pmod{3}$، نظراً لأن $\gcd(3, 2) = 1$، فإننا نستطيع قسمة الطرفين على 2 هكذا $8 \setminus 2 \equiv 2 \setminus 2 \pmod{3}$ والتي تكافئ أيضاً $4 \equiv 1 \pmod{3}$.

خاصية الرفع للأس

أيضاً خاصية مهمة هي خاصية الرفع للأس، فإذا كان $a \equiv r \pmod{m}$، فإن رفع الطرفين للأس الصحيح $e$ صحيح $a^e \equiv r^e \pmod{m}$، مثلاً $12 \equiv 2 \pmod{5}$، فإن $12^{3} \equiv 2^{3} \equiv 1728 \equiv 8 \equiv 3 \pmod{5}$.

التعامل مع الأسس الكبيرة

خاصية الرفع للأسس وخاصية الضرب مفيدة لحساب عملية باقي قسمة عدد مرفوع لأس كبير، تسمى modular exponentiation، والتي تأتي بالشكل $a^e \equiv r \pmod{m}$، حيث أن $e$ عدد كبير، مثل $43^{50} \pmod{30}$، الطريقة الأبسط لحلها، هي أن تحسب قيمة $43^{50}$ أولاً ثم تحسب باقي القسمة على 19، لكن ناتج $43^{50}$ عدد كبير من 82 رقم، تخيل أنك مع RSA ستجري عمليات على أسس بحجم 1024 بت فأكثر، أي أكثر من 300 رقم، هذا طول الأس فقط $e$ وليس $a^e$!، فطول هذا الأخير عدد هائل، أعتقد أنك ستدرك أن حساب الأس أولاً عملية غير مجدية.

الطريقة الأفضل طريقة حساب باقي القسمة مع الأس الثنائي، هنا لو حولت 50 إلى النظام الثنائي فستساوي $50_{10} = 110010_2$، أي أنه يمكننا كتابة 50 كتالي $2^5 + 2^4 + 2^1 = 32 + 16 + 2$، ستكون قيمة التكافؤ:

$$43^{50} \equiv 43^{32+16+2} \equiv 43^{32} \times 42^{16} \times 42^{2} \pmod{30}$$

سنحسب أولاً قيمة:

$$ \begin{align} 43^{32} &\equiv r_1 \pmod{30} \\ 43^{16} &\equiv r_2 \pmod{30} \\ 43^{2} &\equiv r_3 \pmod{30} \\ \end{align} $$

ثم نضرب الناتج $43^{50} \equiv r_1\,r_2\,r_3 \pmod{30}$ ببعض كي نحصل على قيمة $43^{50} \pmod{30}$، طريقة حساب $43^{50} \pmod{30}$:

$$ \begin{align} 43^{1} &\equiv 13 &\pmod{30} \\ 43^{2} &\equiv 13^{2} \equiv 169 \equiv 19 &\pmod{30} \\ 43^{4} &\equiv 19^{2} \equiv 361 \equiv 1 &\pmod{30} \\ 43^{16} &\equiv 1^{2} \equiv 1 &\pmod{30} \\ 43^{32} &\equiv 1^{2} \equiv 1 &\pmod{30} \\ \end{align} $$

في البداية نحسب $43^{1} \pmod{30}$، وستعطينا $13 \pmod{30}$، ثم نربع $43^{1} \pmod{30}$، لتصبح $43^{2} \pmod{30}$، الآن لانحسب قيمة $43^{2} \pmod{30}$، بل يمكننا باستخدام خاصية الأسس أن نربع فقط الناتج السابق $13 \pmod{30}$، وستعطينا $13^2 \equiv 169 \equiv 19 \pmod{30}$.

نكرر الخطوات حتى نصل إلى أكبر أس، 32، ونتوقف، الآن ناتج $43^{50} \pmod{30}$ سيساوي ناتج ضرب $19 \pmod{30}$ مع $1 \pmod{30}$ و $1 \pmod{30}$ وذلك حسب خاصية الضرب، أي:

$$ \begin{align} 43^{50} &\equiv 43^{32+16+2} \\ &\equiv 43^{32} \times 42^{16} \times 42^{2} \\ &\equiv 1 \times 1 \times 19 \\ &\equiv 19 \pmod{30} \end{align} $$

ستلاحظ أننا أوجدنا $43^{50} \equiv 19 \pmod{30}$ بخمسة خطوات بسيطة، في الحقيقة، عدد الخطوات يساوي تقريباً $\log_2{e}$، يميز هذه الطريقة أيضاً، زيادة على سرعتها، أننا لانحتاج ذاكرة كبيرة لحساب $a^e$.

كثير من مكتبات التعامل مع الأرقام الكبيرة توفر وظيفة مخصصة لحساب باقي القسمة بعد الرفع للأس، حيث تستخدم نفس الطريقة السابقة، مثلاً في Java هناك java.math.BigInteger#modPow:

import java.math.BigInteger;

public class PowMod {
    public static void main(String[] args) {
        BigInteger b = new BigInteger("6439932724");
        BigInteger e = new BigInteger("2147483647");
        BigInteger m = new BigInteger("8656553454");

        BigInteger r = b.modPow(e, m);

        System.out.printf("b^e = %s (mod m)\n", r);
    }
}

مع Python يمكنك استخدام pow:

>>> pow(6439932724, 2147483647, 8656553454)
7238866336
>>>

بالمناسبة، حساب $6439932724^{2147483647}$ يحتاج منك ذاكرة أكبر من 8 جيجابايت لتخزينها، فضلاً عن الوقت الازم لحسابها، لكن استخدام الطريقة السابقة يتطلب أجزاء من الثانية لحسابها.

معكوس باقي القسمة الضربي

مفهوم مهم أيضاً في RSA هو معكوس باقي القسمة الضربي، المفتاح الخاص في RSA هو المعكوس الضربي للمفتاح العام، سندع التفاصيل لوقت لاحق.

نعرف في الضرب العادي أن معكوس $a$ هو $a^{-1} = 1/a$، حيث أن ضربهما ببعض يعطي العنصر المحايد، $a\,a^{-1} = a/a = 1$، كذلك الموضوع مشابه في المصفوفات، المعكوس الضربي للمصفوفة $\textrm{A}$، إن وجد، هي المصفوفة $\textrm{A}^{-1}$ ذات نفس الحجم التي عند ضربها في المصفوفة تعطي مصفوفة الوحدة $\textrm{A} \times \textrm{A}^{-1} = \textrm{I}$، يعني مفهموم المعكوس الضربي ليس جديد، لاحظ أنه في حالات كحالة المصفوفة قد لايكون هناك معكوس ضربي.

في حساب باقي القسمة كذلك هناك معكوس في بعض الحالات، حيث يعرف معكوس باقي القسمة الضربي للعدد $a \pmod{m}$ بأنه العدد $x$ الذي يحقق التكافؤ التالي:

$$ax \equiv 1 \pmod{m}$$

هناك معكوس باقي قسمة ضربي فقط إذا كان $\gcd(a, m) = 1$، يعبر أحياناً عن المعكوس $aa^{-1} \equiv 1 \pmod{m}$ للتأكيد على أنه المعكوس.

مثلاً $12 \pmod{5}$، القاسم المشترك الأكبر هنا $\gcd(12, 5) = 1$ مما يشير إلى هناك معكوس ضربي $x$ يحقق $12x \equiv 1 \pmod{5}$، بعد تجربة عدة أعداد ستجده $x = 3$، أي $12 \times 3 \equiv 36 \equiv 1 \pmod{5}$، هنا نقول أن $12^{-1} \pmod{5}$ هو $3 \pmod{5}$.

يمكن إيجاد المعكوس باستخدام خوارزمية اقليدس المطورة، وهي خوارزمية اقليدس العادية التي تهدف لإيجاد القاسم المشترك الأكبر $\gcd(a, b)$ للعددين $a$ و $b$، والجزء الإضافي أنها تهدف لإيجاد العددين $x$ و $y$ الذين يحققان متطابقة بوزو التالية:

$$ax + by = \gcd(a, b)$$

حيث أن $x$ و $y$ يسميان معاملا بوزو، هنا $x$ يمثل المعكوس الضربي.

لدينا $ax \equiv 1 \pmod{m}$ حيث أن $ax = mk + 1$، راجع جزئية القسمة الصحيحة وباقي القسمة، سنعيد ترتيبها بنفس ترتيب متطابقة بوزو كي نستطيع استخدام خوارزمية إقليدس المطورة سنجدها $ax - mk = 1$، حتى يكون هناك معكوس ضربي $a^{-1} \pmod{m}$، وهو $x$ في تلك المتطابقة، لابد أن يكون القاسم المشترك الأكبر بين $\gcd(a, m) = 1$.

لنأخذ المثال $9x \equiv 1 \pmod{22}$، حولها لمتطابقة بوزو لتصبح $9x - 22k = 1$، الآن نجري جزئية إيجاد القاسم المشترك الأكبر عن طريق خوارزمية إقليدس:

$$ \begin{align} 22 &= 9 \times 2 + 4 \tag 1\\ 9 &= 4 \times 2 + \underline{1} \tag 2\\ 4 &= 1 \times 4 + 0 \end{align} $$

هنا وجدنا فقط القاسم المشترك الأكبر $\gcd(22, 9) = 1$، إذا ظهر لك غيره فهذا يعني أنه لايوجد هناك معكوس ضربي.

الإضافة الجديدة أننا سنعمل من الأسفل للأعلى حتى نصل لمعادلة بالشكل التالي $9x - 22k = 1$، حيث سنبدأ من المعادلة $(2)$ قبل الأخيرة وسنضع 1 في طرف المعادلة:

$$ \begin{align} 1 &= 9 - \overline{4} \times 2 \\ &= 9 - (22 - 9 \times 2) \times 2 &&\text{From (1)}\\ &= 9 - (22 \times 2 - 9 \times 4) &&\text{Multiply by 2}\\ &= 9 - 22 \times 2 + 9 \times 4 &&\text{Multiply by -1}\\ &= 9 \times (1 + 4) - 22 \times 2 &&\text{Common factor 9}\\ &= 9 \times 5 - 22 \times 2 \end{align} $$

احتمال الخطأ في حسابها يدوياً كبير، لذا تأكد أن الطرف الأيمن يساوي 1 بعد كل خطوة وتجنب حساب القيم التي تحتوي 9 أو 22، الآن بمقارنة المعادلة الأخيرة مع $9x - 22k = 1$ ستجد أن $x = 5$، إذاً فالمعكوس الضربي $5 \pmod{22}$.

مثال آخر، $7x \equiv 1 \pmod{40}$، حولها لمتطابقة بوزو $7x - 40k = 1$، نوجد القاسم المشترك الأكبر:

$$ \begin{align} 40 &= 7 \times 5 + 5 \tag 1\\ 7 &= 5 \times 1 + 2 \tag 2\\ 5 &= 2 \times 2 + 1 \tag 3\\ 2 &= 2 \times 1 + 0 \end{align} $$

كون القاسم المشترك الأكبر $\gcd(40, 7) = 1$ إذاً فهناك معكوس ضربي، الآن نعوض من الأسفل للأعلى بدءً من الخطوة قبل الأخيرة:

$$ \begin{align} 1 &= 5 - \overline{2} \times 2\\ &= 5 - (7 - 5) \times 2 &&\text{From (2)}\\ &= 5 - 7 \times 2 + 5 \times 2 \\ &= \overline{5} \times 3 - 7 \times 2\\ &= (40 - 7\times 5) \times 3 - 7 \times 2 &&\text{From (1)}\\ &= 40 \times 3 - 7 \times 15 - 7 \times 2 \\ &= 40 \times 3 - 7 \times 17 \end{align} $$

الآن بمقارنة المعادلة الأخيرة مع $7x - 40k = 1$ ستجد إشارة المعكوس الضربي سالبة $-17 \pmod{40}$، هي صحيحة لكن شكلها غير مريح، لنحولها للموجب $-17 \equiv 40 - 17 \equiv 23 \pmod{40}$، الآن معكوسنا الضربي $23 \pmod{40}$، حيث أن $7 \times 23 \equiv 161 \equiv 1 \pmod{40}$.

هذه خوارزمية لإيجاد المعكوس فقط، وهو فعلاً مايهمنا:

function inverse(a, n)
    t := 0;     newt := 1;
    r := n;     newr := a;
    while newr ≠ 0
        quotient := r div newr
        (t, newt) := (newt, t - quotient * newt) 
        (r, newr) := (newr, r - quotient * newr)
    if r > 1 then return "a is not invertible"
    if t < 0 then t := t + n
    return t

عداد ونظرية أويلر

مفهوم مهم أيضاً في RSA هي عداد ونظرية أويلر، عداد أويلر3، ويكتب $\phi(n)$، وهو دالة بسيطة تعطي عدد الأعداد الموجبة الأصغر من $n$ والأولية فيما بينها وبين $n$، أي أن القاسم المشترك الأكبر بينها وبين $n$ هو واحد، مثلاً $\phi(10) = 4$ وذلك لأن هناك أربعة أرقام أولية بالنسبة للعدد 10 وهي $\{1, 3, 7, 9\}$، لاتهم الأعداد نفسها بل المهم عددها.

هناك خصائص مهمة لعداد أويلر:

  • قيمة $\phi(n)$ للصفر والأعداد السالبة صفر
  • قيمة $\phi(1) = 1$
  • ضرب عددين $a$ و$b$ يعطي $\phi(ab) = \phi(a)\,\phi(b)$
  • إذا كانت $p$ عدد أولي، $\phi(p) = p - 1$

الخاصية الأخيرة تعود لأن جميع الأعداد الأصغر من العدد الأولي يستحيل أن تتشارك بقاسم مشترك، وإلا فهذا العدد ليس أولي، باستثناء الواحد، طبعاً إذا كان $p$ و $q$ عددين أوليين فإن $\phi(pq) = (p - 1)(q - 1)$ وذلك باستخدام الخاصيتين الأخيرة.

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

$$a^{\phi(n)} \equiv 1 \pmod{n}$$

هذه النظرية الأساسية التي تعتمد عليها دالة التشفير وفك التشفير في RSA.

هناك خاصية جميلة بهذه النظرية وهي قدرتها على تبسيط الأسس الكبيرة، مثلاً لو قيل لك أوجد $4^{199} \pmod{13}$، سترى أن 4 و 13 أوليان فيما بينهما، وهنا $\phi(13) = 12$، يمكننا قسمة 199 على 12 وتعديل التكافؤ قليلاً كي نحسب فقط باقي قسمة 199 على 12 هكذا:

$$ \begin{align} 4^{199} &\equiv 4^{12 \times 16 + 7} \\ &\equiv 4^{12 \times 16} \times 4^{7} \\ &\equiv (4^{12})^{16} \times 4^{7} \\ &\equiv (1)^{16} \times 4^{7} \\ &\equiv 4^7 \\ &\equiv 4 \pmod{13} \end{align} $$

لو قيل لك بسط $x^{ab} \pmod{n}$ حيث أن $ab \equiv 1 \pmod{\phi(n)}$، أي $a \pmod{\phi(n)}$ و $b \pmod{\phi(n)}$ هما المعكوسان الضربيان لبعض.

بمعلومية $ab \equiv 1 \pmod{\phi(n)}$، نعلم أن $ab = \phi(n)\,k + 1$، عوض $ab$ في $x^{ab} \pmod{n}$، ستجد:

$$ \begin{align} x^{ab} &\equiv x^{\phi(n)\,k + 1} \\ &\equiv (x^{\phi(n)})^{k} \times x^1\\ &\equiv 1^k\times x \\ &\equiv x \pmod{n} \end{align} $$

إذا فهمت هذه النقطة، فستفهم بسهولة النظرية الأساسية خلف RSA.

نظرية فيرما الصغرى

نظرية فيرما الصغرى مهمة في اختبارات أوليّة العدد الإحصائية، بعض المراجع تثبت صحة RSA باستخدام نظرية فيرما رغم أن الإثبات باستخدام نظرية أويلر هو الإثبات المباشر والأسهل.

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

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

مثلاً $3^5 \equiv 3 \pmod{5}$ وذلك لأن 5 عدد أولي و 3 ليست من مضاعفاتها، ماذا عن $12^7 \equiv 5 \pmod{7}$، تذكر المعنى الحقيقي للتكافؤ $12 \equiv 5 \pmod{7}$.

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

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

الآن سترى أنها فعلاً حالة خاصة من نظرية أويلر، حيث أن $\phi(p) = p - 1$ بما أن $p$ عدد أولي و $\gcd(a, p) = 1$.

النظرية الأساسية للحساب

النظرية الأساسية للحساب مهمة للغاية، وبسيطة في نفس الوقت، حيث ترتبط بالأعداد الأولية، وتنص على أن كل عدد $n$ أكبر من الواحد إما أن يكون عدد أولي، أو عدد مركب يمكن كتابته كحاصل ضرب أعداد أولية بتكرار فريد، مثلاً $12 = 2^2 \times 3$، وكذلك $100 = 2^2 \times 5^2$، وهكذا.

النظرية بسيطة للغاية، لكن هناك شيء مهم يجب أن تعرفه، إذا قيل لك أن هناك عدد $n$ نتج من ضرب عددين أوليين $p$ و $q$، أي $n = pq$، فلا يوجد عوامل أوليه لهذا العدد $n$ سوى $p$ و $q$.

هذه النظرية هي السبب الذي جعل العدد واحد يستثنى من قائمة الأعداد الأولية رغم أن ينطبق عليه تعريف العدد الأولي، وذلك بسبب عبارة "تكرار فريد" في هذه النظرية، لأنه لو اعتبرنا الواحد عدد أولي، فهناك عدد لانهائي من الترتيبات لأي عدد، مثلاً $12 = 2^2 \times 3 \times 1$ وكذلك $12 = 2^2 \times 3 \times 1^5$ وكذلك $12 = 2^2 \times 3 \times 1^{100}$، لذا استثني الواحد بدل عمل استثناء للواحد في النظرية، خصوصاً أن هناك العديد من النظريات التي بنيت فوق هذه النظرية، استثاء الواحد مع كل نظرية عملية مزعجة.

من هذه النظرية يمكننا استنتاج أن الأعداد الأولية غير منتهية، لأنها لو كانت منتهية فهذا يعني أن الأعداد التي يمكننا تشكيلها من الأعداد الأولية منتهية أيضاً.

الخاتمة

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


  1. يشار للقسمة الصحيحة للعدين $a$ و $b$ بالرمز $a \setminus b$، حيث أن الناتج دوماً عدد صحيح بدون كسور، عكس القسمة العادية $a / b$، مثلاً $7 / 2 = 3.5$ بينما $7 \setminus 2 = 3$، فقط تجاهل الجزء العشري. 

  2. استخدام $\bmod$ كمعامل ثنائي، $a \bmod b$، ليس شائع في كتب الرياضيات، بل شائع أكثر في علوم الحاسب. 

  3. هناك دالة أخرى تشبه عداد أويلر لحد قريب وهي عداد الأعداد الأولية، حيث يشار لها $\pi(n)$ وتعطي عدد الأعداد الأولية الأصغر من $n$