Number Theory & Cryptography

الفصل الثالث: نظرية الأعداد والتشفير

الهدف: فهم حساب المود (Modulo)، خوارزمية إقليدس، وكيف يعمل تشفير RSA.
1

Modular Arithmetic (حساب المود)

التعريف الأساسي

نقول أن $a$ يطابق $b$ مود $m$ وتكتب $a \equiv b \pmod m$ إذا كان $m$ يقسم الفرق بينهما $(a-b)$.
بمعنى آخر: لهما نفس الباقي عند القسمة على $m$.

$17 \equiv 5 \pmod{12}$
(لأن 17 - 5 = 12، وهو يقبل القسمة على 12)
خصائص هامة:
  • إذا كان $a \equiv b$ و $c \equiv d$:
  • $a + c \equiv b + d \pmod m$
  • $a \cdot c \equiv b \cdot d \pmod m$
  • $a^k \equiv b^k \pmod m$
2

Primes & GCD

Euclidean Algorithm (لإيجاد GCD)

لإيجاد القاسم المشترك الأكبر لرقمين كبيرين، نكرر عملية القسمة.
$GCD(a, b) = GCD(b, a \pmod b)$

GCD(252, 105):
252 = 2 * 105 + 42
105 = 2 * 42 + 21
42 = 2 * 21 + 0
Result: 21 (آخر باقي غير صفري)

Bézout's Identity

إذا كان $d = GCD(a, b)$، فإنه توجد أعداد صحيحة $s$ و $t$ بحيث:

$s \cdot a + t \cdot b = d$

هذه المعادلة هي الأساس لإيجاد المعكوس الضربي (Modular Inverse)، وهو أهم خطوة في التشفير.

3

RSA Cryptography

كيف يعمل RSA؟

Step 1
اختر عددين أوليين كبيرين $p$ و $q$. احسب $n = p \cdot q$.
Step 2
احسب $\phi(n) = (p-1)(q-1)$.
Step 3
اختر مفتاح التشفير $e$ بحيث يكون أولي نسبياً مع $\phi(n)$. (Public Key: n, e)
Step 4
احسب مفتاح فك التشفير $d$ بحيث $d \cdot e \equiv 1 \pmod{\phi(n)}$. (Private Key: d)
Encryption $C = M^e \pmod n$
Decryption $M = C^d \pmod n$
🛡️ EXAM VAULT (خزنة الاختبار)
TRAP / فخ السالب

Negative Modulo

ما هو $-13 \pmod 5$؟
الجواب ليس $-3$ ولا $-2$.
الجواب يجب أن يكون موجباً بين 0 و 4.
$-13 = 5(-3) + \mathbf{2}$. الجواب هو 2.
(قاعدة سريعة: استمر بإضافة 5 حتى يصبح الرقم موجباً: -13 -> -8 -> -3 -> 2).

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

Fermat's Little Theorem

إذا كان $p$ عدداً أولياً، فإن لأي عدد $a$ لا يقبل القسمة على $p$:
$$ a^{p-1} \equiv 1 \pmod p $$
تستخدم لتبسيط حساب الأسس الكبيرة جداً بسرعة هائلة.

→ السابق (Ch 2) الفصل التالي (Ch 4) ←