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

١. قابلية القسمة والحساب النمطي

📌 تعريف: القسمة

ليكن a, b ∈ ℤ على شرط a ≠ 0.

a | b (نقرأ "a يقسم b") إذا وجد عدد صحيح c بحيث b = ac.

a يُسمّى عاملاً أو قاسم للعدد b
b يُسمّى مضاعفاً للعدد a
a ∤ b تعني أن a لا يقسم b

💡 أمثلة

3 | -12 صحيحة لأن -12 = 3 × (-4)
3 | 7 خاطئة (عدد أكبر ما يقسم عدد أصغر موجب)
77 | 7 خاطئة
7 | 77 صحيحة لأن 77 = 7 × 11
24 | 24 صحيحة لأن 24 = 24 × 1
0 | 24 خاطئة (فقط الصفر يقبل القسمة على 0)
24 | 0 صحيحة (الصفر يقبل القسمة على أي عدد: 0 = 24 × 0)

🎯 خصائص علاقة القسمة

لكل الأعداد الصحيحة a, b, c ∈ ℤ:

(a|b ∧ a|c) → a|(b+c)
مثال: 3|12 ∧ 3|9 → 3|(12+9) = 3|21 = 7
a|b → a|bc
مثال: 2|6 → 2|(6×3) = 2|18 = 9
(a|b ∧ b|c) → a|c
مثال: 4|8 ∧ 8|64 → 4|64 = 16

٢. الأعداد الأولية والقاسم المشترك الأكبر

🔢 الأعداد الأولية والمركبة

العدد الأولي

العدد الصحيح الموجب p > 1 يُسمّى أولي إذا كانت قواسمه الموجبة الوحيدة هي 1 و p.

أمثلة: ٢، ٣، ٥، ٧، ١١، ١٣، ١٧، ١٩، ٢٣، ٢٩ ...

العدد المركب

الأعداد الصحيحة الأكبر من ١ غير الأولية تُسمّى مركبة لأنها تنتج من ضرب عددين صحيحين أكبر من ١.

🎯 النظرية الأساسية في الحسابيات

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

أمثلة:

100 = 2·2·5·5 = 2² × 5²
13 = 13 (أولي)
1024 = 2·2·2·2·2·2·2·2·2·2 = 2¹⁰

🔍 اختبار الأولية

اختبار العدد الأولي

مبرهنة: إذا كان n عدداً مركباً، فإن له قاسماً أولياً ≤ √n

الطريقة: العدد n يكون أولياً إذا لم يقبل القسمة على أي عدد أولي ≤ √n

💡 مثال: اختبر إذا كان ١٣٩ و ١٤٣ أوليين

الخطوة ١: احسب √n

√139 ≈ ١١.٨ ، √143 ≈ ١٢.٠

الخطوة ٢: اكتب كل الأعداد الأولية ≤ √n: ٢، ٣، ٥، ٧، ١١

الخطوة ٣: افحص قابلية القسمة

١٣٩: لا يقبل القسمة على ٢، ٣، ٥، ٧، ١١ → أولي
١٤٣: باستخدام خدعة المجموع المتناوب: ١-٤+٣ = ٠ → يقبل القسمة على ١١ (١٤٣ = ١١ × ١٣) → مركب

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

تعريف

القاسم المشترك الأكبر gcd(a,b) لعددين صحيحين a و b (ليس كلاهما صفر) هو أكبر عدد صحيح موجب d يقسم كلاً من a و b.

📋 طريقتان لإيجاد GCD

الطريقة ١: سرد كل القواسم

أوجد gcd(24, 36)

قواسم ٢٤: ١، ٢، ٣، ٤، ٦، ٨، ١٢، ٢٤
قواسم ٣٦: ١، ٢، ٣، ٤، ٦، ٩، ١٢، ١٨، ٣٦
القواسم المشتركة: ١، ٢، ٣، ٤، ٦، ١٢
أكبرها = ١٢
∴ gcd(24, 36) = 12

الطريقة ٢: التحليل إلى العوامل الأولية (نأخذ الأصغر)

أوجد gcd(24, 36)

24 = 2³ × 3¹
36 = 2² × 3²
gcd(24, 36) = 2^min(3,2) × 3^min(1,2) = 2² × 3¹ = 12

أوجد gcd(98, 420)

98 = 2 × 49 = 2¹ × 7²
420 = 2 × 210 = 2 × 2 × 105 = 2² × 3 × 5 × 7
العوامل المشتركة: 2 × 7
gcd(98, 420) = 14

🔄 أولية نسبياً (Coprime)

نقول عن عددين صحيحين a و b أنهما أوليان نسبياً إذا gcd(a,b) = 1، أي ليس بينهما قواسم أولية مشتركة.

أمثلة:

gcd(11, 77) = 11 → ليسا أوليين نسبياً
gcd(33, 77) = 11 → ليسا أوليين نسبياً
gcd(24, 36) = 12 → ليسا أوليين نسبياً
gcd(24, 25) = 1 → أوليان نسبياً

📝 ملاحظة: العدد الأولي يكون أولياً نسبياً مع كل الأعداد الأخرى التي لا يقسمها.

📐 المضاعف المشترك الأصغر (LCM)

المضاعف المشترك الأصغر lcm(a,b) لعددين موجبين a و b هو أصغر عدد صحيح موجب مضاعف لكلا العددين.

باستخدام التحليل إلى العوامل الأولية (نأخذ الأكبر):
lcm(a, b) = جداء كل العوامل الأولية بالأس الأكبر

💡 أمثلة

أوجد lcm(6, 10)

6 = 2 × 3
10 = 2 × 5
lcm(6, 10) = 2 × 3 × 5 = 30

أوجد lcm(24, 36)

24 = 2³ × 3¹
36 = 2² × 3²
lcm(24, 36) = 2³ × 3² = 8 × 9 = 72

٣. خوارزمية القسمة والحساب النمطي

➗ خوارزمية القسمة

ليكن a عدداً صحيحاً و d عدداً صحيحاً موجباً. يوجد عددان صحيحان وحيدان q و r بحيث:

a = d × q + r ، حيث 0 ≤ r < d

d يُسمّى القاسم
a يُسمّى المقسوم
q هو ناتج القسمة: q = a div d
r هو الباقي: r = a mod d

💡 أمثلة

ما ناتج القسمة والباقي عند قسمة ١٠١ على ١١؟

101 = 11 × 9 + 2
q = 9 ، r = 2

ما ناتج القسمة والباقي عند قسمة -١١ على ٣؟

-11 = 3 × (-4) + 1
q = -4 ، r = 1
ملاحظة: -11 ≠ 3 × (-3) - 2 لأن r يجب أن يكون ≥ 0 (لا يمكن سالب)

🔢 دالة المود (Modulo)

دالة المود ترجع باقي قسمة عدد صحيح على عدد صحيح موجب.

a mod d = r ، حيث 0 ≤ r < d

💡 أمثلة

113 mod 24:
- 24 | 113
- 113 = 24 × 4 + 17
- 113 mod 24 = 17
-29 mod 7:
- 7 | -29
- -29 = 7 × (-5) + 6
- -29 mod 7 = 6

⏰ تطبيق عملي: حساب الوقت

💡 كم الساعة بعد ٥٠ ساعة من الساعة ١١ صباحاً؟

الطريقة ١: خطوة بخطوة

بعد ٢٤ ساعة → ١١ صباحاً
بعد ٤٨ ساعة (٢٤ أخرى) → ١١ صباحاً
بعد ٥٠ ساعة (ساعتين زيادة) → ١ ظهراً (١٣:٠٠)

الطريقة ٢: باستخدام المود

(11 + 50) mod 24 = 61 mod 24 = 13
الجواب: 13:00 (١ ظهراً)

تحويل نظام ٢٤ ساعة إلى ١٢ ساعة:

13 mod 12 = 1 (1 pm)
23 mod 12 = 11 (11 pm)

≡ تطابق نمطي (Modular Congruence)

ليكن a, b ∈ ℤ، m ∈ ℤ⁺. نقول a يطابق b نمط m، ونكتب:

a ≡ b (mod m)

إذا وفقط إذا:

a mod m = b mod m، أو
m | (a - b)، أي (a - b) mod m = 0

💡 هل ١٧ يطابق ٥ نمط ٦؟

17 mod 6 = 5 و 5 mod 6 = 5 ✓
6 | (17-5) ↔ 6 | 12 حيث 12/6 = 2 ✓
إذن: 17 ≡ 5 (mod 6)

💡 هل ٢٤ يطابق ١٤ نمط ٦؟

24 mod 6 = 0 و 14 mod 6 = 2 ✗
6 ∤ (24-14) ↔ 6 ∤ 10 ✗
إذن: 24 ≢ 14 (mod 6)

🧮 مبرهنات التطابق

ليكن a, b, c, d ∈ ℤ، m ∈ ℤ⁺. إذا كان a ≡ b (mod m) و c ≡ d (mod m)، فإن:

a + c ≡ b + d (mod m)
ac ≡ bd (mod m)

💡 مثال

ليكن 7 ≡ 2 (mod 5) و 11 ≡ 1 (mod 5)

إذن:

(7 + 11) ≡ (2 + 1) (mod 5) ↔ 18 ≡ 3 (mod 5) ✓
(7 × 11) ≡ (2 × 1) (mod 5) ↔ 77 ≡ 2 (mod 5) ✓

🔐 ٤. أساسيات التشفير

وش هو التشفير؟

التشفير هو العلم اللي يطبّق رياضيات معقدة ومنطق عشان يصمّم طرق قويّة لتعمية البيانات. هو فن وعلم في نفس الوقت ويساعد الناس يحافظون على ثقتهم في العالم الإلكتروني.

🎯 مفاهيم أساسية

النص الأصلي (Plaintext): الرسالة اللي تقدر تقرأها.
النص المشفر (Ciphertext): الرسالة بعد التعمية.
التعمية (Encryption): تحويل النص الأصلي إلى نص مشفر.
فك التعمية (Decryption): تحويل النص المشفر راجع إلى النص الأصلي.
المفتاح (Key): معلومة سرّية تستخدم في التعمية وفكها.

🏛️ تعريف نظام التشفير

نظام التشفير هو خُماسية (P, C, K, E, D)، حيث:

P مجموعة النصوص الأصلية.
C مجموعة النصوص المشفرة.
K فضاء المفاتيح (كل المفاتيح الممكنة).
E مجموعة دوال التعمية.
D مجموعة دوال فك التعمية.

D_k(E_k(p)) = p ، لكل نص أصلي p

🔑 ٥. التشفير المتماثل (مفتاح واحد)

التشفير المتماثل هو التقنية الشائعة لتأمين السرية، وفيه نفس المفتاح يُستعمل في التعمية وفك التعمية.

الخوارزميات المشهورة: DES، Triple DES، AES

📝 شروط الاستخدام الآمن

تحتاج خوارزمية تعمية قوية.
المرسل والمستقبل لازم يتحصلون على نسخ من المفتاح السري بطريقة آمنة.
يجب الحفاظ على سرية المفتاح.

🏛️ شيفرة قيصر (Caesar Cipher)

يوليوس قيصر كان يرسل رسائل سرية بإزاحة كل حرف ثلاث مرات إلى الأمام في الأبجدية (ويرسل الأحرف الثلاثة الأخيرة إلى أول ثلاثة أحرف).

مثال: B ← E ، X ← A

📋 خطوات شيفرة قيصر

استبدل كل حرف بعدد صحيح من Z₂₆ (من ٠ إلى ٢٥)، حيث العدد = ترتيب الحرف في الأبجدية ناقص ١.
- A=0, B=1, C=2, ..., Z=25
طبّق دالة التعمية: f(p) = (p + 3) mod 26
استبدل كل عدد p بالحرف ذي الترتيب p+1 في الأبجدية.

💡 مثال: عمية النص "MEET YOU IN THE PARK"

الخطوة ١: تحويل إلى أعداد

M E E T → 12 4 4 19
Y O U → 24 14 20
I N → 8 13
T H E → 19 7 4
P A R K → 15 0 17 10

الخطوة ٢: طبّق f(p) = (p + 3) mod 26

15 7 7 22 1 17 23 11 16 22 10 7 18 3 20 13

الخطوة ٣: تحويل عكسي إلى حروف

النص المشفر: "PHHW BRX LQ WKH SDUN"

🔄 شيفرات الإزاحة (Shift Ciphers)

شيفرة قيصر هي حالة خاصة من عائلة شيفرات الإزاحة، حيث تُزاح الحروف بأي عدد صحيح k.

التعمية: f(p) = (p + k) mod 26
فك التعمية: f⁻¹(p) = (p - k) mod 26

العدد k هو المفتاح.

💡 مثال: عمية "STOP GLOBAL WARMING" بالمفتاح k = 11

الخطوة ١: تحويل إلى أعداد

18 19 14 15 6 11 14 1 0 11 22 0 17 12 8 13 6

الخطوة ٢: طبّق f(p) = (p + 11) mod 26

3 4 25 0 17 22 25 12 11 22 7 11 2 23 19 24 17

الخطوة ٣: تحويل عكسي إلى حروف

النص المشفر: "DEZA RWZMLW HLCXTYR"

💡 مثال: فك تعمية "LEWLYPLUJL PZ H NYLHA ALHJOLY" بالمفتاح k = 7

الخطوة ١: تحويل إلى أعداد

11 4 22 11 24 15 11 20 9 11 15 25 7 13 24 11 7 0 0 11 7 9 14 11 24

الخطوة ٢: طبّق f⁻¹(p) = (p - 7) mod 26

4 23 15 4 17 8 4 13 2 4 8 18 0 6 17 4 0 19 19 4 0 2 7 4 17

الخطوة ٣: تحويل عكسي إلى حروف

النص المفكوك: "EXPERIENCE IS A GREAT TEACHER"

🔍 تحليل الشيفرات (Cryptanalysis)

تحليل الشيفرات (كسر الشفرة) هو عملية استرجاع النص الأصلي من النص المشفر دون معرفة طريقة التعمية والمفتاح.

🛠️ أدوات تحليل الشيفرات

التكرار النسبي للحروف في الإنجليزية:

E: 13% (الأكثر شيوعاً)
T: 9%
A, O: 8%
I, N, S: 7%
H, R: 6%

الطريقة:

احسب تكرار الحروف في النص المشفر.
افترض أن الحرف الأكثر تكرارًا يقابل E.
احسب قيمة الإزاحة k.
فك تعمية كل الرسالة.
إذا ما ضبطت، جرب T، وبعدين A، إلخ.

📊 مراسلة الحرف – العدد

الحرف	A	B	C	D	E	F	G	H	I	J	K	L	M
العدد	0	1	2	3	4	5	6	7	8	9	10	11	12

الحرف	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
العدد	13	14	15	16	17	18	19	20	21	22	23	24	25

🔓 ٦. تشفير المفتاح العام – RSA

وش هو تشفير المفتاح العام؟

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

🏆 نظام RSA

طُوِّر عام ١٩٧٦ بواسطة رونالد ريفست، عدي شامير، وليونارد أدلمان في MIT. كما اكتُشِف سابقاً بواسطة كليفورد كوكس (الحكومة البريطانية، كان سرياً).

🔑 توليد مفاتيح RSA

📋 خطوات خوارزمية RSA

اختار عددين أوليين p و q بشرط p ≠ q
- عادةً أعداد أولية كبيرة جداً (كل واحد ٢٠٠ خانة فأكثر).
احسب n = p × q
- n هو المعامل (حوالي ٤٠٠ خانة).
احسب Φ(n) = (p-1) × (q-1)
- دالة أويلر.
اختار e بحيث:
- e أولي نسبياً مع Φ(n): gcd(e, Φ(n)) = 1
- 1 < e < Φ(n)
احسب d = e⁻¹ mod Φ(n)
- أي e × d ≡ 1 (mod Φ(n))
المفتاح العام = {e, n}
المفتاح الخاص = {d, n}

التعمية: C = P^e mod n
فك التعمية: P = C^d mod n
حيث P < n

💡 أمثلة كاملة على RSA

مثال ١: p=7, q=11, e=5, النص الأصلي = 6

p = 7, q = 11
n = p × q = 7 × 11 = 119
Φ(n) = (7-1) × (11-1) = 6 × 10 = 96
المفتاح العام e = 5 (معطى)
احسب d:
- d = ((Φ(n) × i) + 1) / e
- d = (96×1+1)/5 = 19.4 ✗
- d = (96×2+1)/5 = 38.6 ✗
- d = (96×3+1)/5 = 57.8 ✗
- d = (96×4+1)/5 = 77 ✓
المفتاح العام = {5, 119} ، المفتاح الخاص = {77, 119}
التعمية: C = 6⁵ mod 119 = 7776 mod 119 = 41
فك التعمية: P = 41⁷⁷ mod 119 = 6 ✓

مثال ٢: p=5, q=7, e=11, النص الأصلي = 2

p = 5, q = 7
n = 5 × 7 = 35
Φ(n) = 4 × 6 = 24
e = 11
d = 11 (لأن 11 × 11 mod 24 = 1)
المفتاح العام = {11, 35} ، المفتاح الخاص = {11, 35}
التعمية: C = 2¹¹ mod 35 = 2048 mod 35 = 18
فك التعمية: P = 18¹¹ mod 35 = 2 ✓

مثال ٣: p=17, q=11, e=7, النص الأصلي = 5

p = 17, q = 11
n = 17 × 11 = 187
Φ(n) = 16 × 10 = 160
e = 7
d = 23 (احسب: (160×i+1)/7 حتى تحصل على عدد صحيح)
المفتاح العام = {7, 187} ، المفتاح الخاص = {23, 187}
التعمية: C = 5⁷ mod 187 = 78125 mod 187 = 146
فك التعمية: P = 146²³ mod 187 = 5 ✓

مثال ٤: p=3, q=11, e=3, النص الأصلي = (00111011)₂ = 59

p = 3, q = 11
n = 3 × 11 = 33
Φ(n) = 2 × 10 = 20
e = 3
d = 7
المفتاح العام = {3, 33} ، المفتاح الخاص = {7, 33}
التعمية: C = 59³ mod 33 = 205379 mod 33 = 20
فك التعمية: P = 20⁷ mod 33 = 1280000000 mod 33 = 26

مثال ٥: p=13, q=17, e=19, النص الأصلي = 12

p = 13, q = 17
n = 13 × 17 = 221
Φ(n) = 12 × 16 = 192
e = 19
d = 91
المفتاح العام = {19, 221} ، المفتاح الخاص = {91, 221}
التعمية: C = 12¹⁹ mod 221 = 181
فك التعمية: P = 181⁹¹ mod 221 = 12 ✓

📝 تعمية نصوص باستخدام RSA

💡 مثال: عمية "STOP" باستخدام RSA بالمفتاح (2537, 13)

معطى: n = 2537 = 43 × 59 ، e = 13

الخطوة ١: تحويل الحروف إلى أعداد

S T O P → 18 19 14 15

الخطوة ٢: تقسيم إلى كتل

بما أن 2525 < 2537 < 252525 ، نستخدم كتل من ٤ أرقام.
الكتل: 1819 ، 1415

الخطوة ٣: تعمية كل كتلة: C = M¹³ mod 2537

1819¹³ mod 2537 = 2081
1415¹³ mod 2537 = 2182

النص المشفر: 2081 2182

💡 مثال: فك تعمية "0981 0461" باستخدام n=2537, e=13

الخطوة ١: إيجاد مفتاح فك التعمية d

d هو معكوس 13 نمط (42 × 58) = 2436
d = 937

الخطوة ٢: فك تعمية كل كتلة: M = C⁹³⁷ mod 2537

0981⁹³⁷ mod 2537 = 0704
0461⁹³⁷ mod 2537 = 1115

الخطوة ٣: تحويل إلى حروف

0704 → 07 04 → H E
1115 → 11 15 → L P

النص المفكوك: HELP

⚠️ ملاحظة أمنية

RSA يشتغل كنظام مفتاح عام لأن الطريقة الوحيدة المعروفة لإيجاد d تعتمد على تحليل n إلى عوامله الأولية. حالياً ما فيه طريقة مجدية لتحليل أعداد كبيرة جداً (٤٠٠ خانة فأكثر) إلى عواملها الأولية في وقت معقول.

🔄 ٧. تبادل المفاتيح Diffie‑Hellman

وش هو Diffie‑Hellman؟

خوارزمية ديفي‑هيلمان، طوّرها ويتفيلد ديفي ومارتن هيلمان عام ١٩٧٦، تخلّي شخصين يتبادلون مفتاح سري عبر قناة غير آمنة ويقدّرون يستخدمونه بعدين في تعمية الرسائل.

🔑 خطوات خوارزمية Diffie‑Hellman

اختار q (عدد أولي) و α (جذر بدائي لـ q)
- هذي القيم عامة.
توليد مفتاح المستخدم A:
- اختار X_A بحيث X_A < q (سري).
- احسب المفتاح العام: Y_A = α^X_A mod q
- شارك Y_A مع المستخدم B.
توليد مفتاح المستخدم B:
- اختار X_B بحيث X_B < q (سري).
- احسب المفتاح العام: Y_B = α^X_B mod q
- شارك Y_B مع المستخدم A.
المستخدم A يحسب المفتاح السري:
- K = (Y_B)^X_A mod q
المستخدم B يحسب المفتاح السري:
- K = (Y_A)^X_B mod q

الطرفان يحصلان على نفس المفتاح:
K = α^X_A·X_B mod q

💡 أمثلة كاملة على Diffie‑Hellman

مثال ١: q=353, α=3, X_A=97, X_B=233

الخطوة ١: المعاملات العامة

q = 353, α = 3

الخطوة ٢: المفتاح العام للمستخدم A

X_A = 97 (سري)
Y_A = 3⁹⁷ mod 353 = 40

الخطوة ٣: المفتاح العام للمستخدم B

X_B = 233 (سري)
Y_B = 3²³³ mod 353 = 248

الخطوة ٤: A يحسب المفتاح المشترك

K = (Y_B)^X_A mod q
K = 248⁹⁷ mod 353 = 160

الخطوة ٥: B يحسب المفتاح المشترك

K = (Y_A)^X_B mod q
K = 40²³³ mod 353 = 160 ✓

المفتاح السري المشترك: K = 160

مثال ٢: q=23, α=5, X_A=6, X_B=15

q = 23, α = 5
Y_A = 5⁶ mod 23 = 8
Y_B = 5¹⁵ mod 23 = 19
K_A = 19⁶ mod 23 = 2
K_B = 8¹⁵ mod 23 = 2 ✓

المفتاح السري المشترك: K = 2

مثال ٣: q=11, α=17, X_A=8, X_B=12

q = 11, α = 17
Y_A = 17⁸ mod 11 = 4
Y_B = 17¹² mod 11 = 3
K_A = 3⁸ mod 11 = 5
K_B = 4¹² mod 11 = 5 ✓

المفتاح السري المشترك: K = 5

🔒 الأمن

لمعرفة المعلومات السرية من المعلومات العامة، يحتاج المهاجم أن يجد X_A و X_B من α^X_A mod q و α^X_B mod q على التوالي. هذه مسألة اللوغاريتم المتقطع، وتُعتبر صعبة حسابياً عندما يكون q و α كبيرين بما يكفي.

📝 بروتوكولات تشفيرية

التوقيع الرقمي

إضافة توقيع رقمي للرسالة يضمن للمستقبل أن الرسالة فعلاً من المرسل المزعوم.

الطريقة (باستخدام RSA):

علياء تحوّل الرسالة إلى معادلات عددية وتقسّمها لكتل.
تطبّق دالة فك التعمية الخاص بها D_(n,e) على الكتل.
المستقبل يطبّق دالة التعمية الخاص بعلياء لاسترجاع النص الأصلي.
بما أن فقط علياء تملك المفتاح الخاص، الكل يعرف أن الرسالة منها.

📚 خلاصة