Classical Cryptography - Arabic Book التشفير الكلاسيكى 2
Classical Cryptography - Arabic Book التشفير الكلاسيكى 2
ھﻞ 101 ﯾﻘﺒﻞ اﻟﻘﺴﻤﺔ ﻋﻠﻰ . 2 ﻻ
ھﻞ 101 ﯾﻘﺒﻞ اﻟﻘﺴﻤﺔ ﻋﻠﻰ 3 ، ﻻ
ھﻞ 101ﯾﻘﺒﻞ اﻟﻘﺴﻤﺔ ﻋﻠﻰ 4 و5و 6و 7و8 و . 9إﻟﻰ أن ﻧﺼﻞ إﻟﻰ 10 ، وأﯾﻀﺎ ﻻ ﯾﻘﺒﻞ ، اذا اﻟﻨﺘﯿﺠﺔ أن اﻟﻌﺪد 101 ھﻮ ﻋﺪد أوﻟﻲ .
ھﺬه اﻟﻄﺮﯾﻘﮫ ﻓﻲ اﻟﺒﺤﺚ ﻟﯿﺴﺖ ﻣﻦ أﻓﻀﻞ اﻟﻄﺮق ﻓﻲ اﺧﺘﺒﺎر أوﻟﯿﮫ اﻟﻌﺪد ، وھﻨﺎك اﻟﻜﺜﯿﺮ ﻣﻦ اﻟﻄﺮق أﻓﻀﻞ ﻣﻨﮭﺎ ، وھﻲ ﺗﺴﻤﻰ ﻃﺮﯾﻘﮫ . Trial Division
ﻣﺜﻼ ﻟﺪﯾﻨﺎ ﻋﺪد ﺿﺨﻢ ﯾﺘﻜﻮن ﻣﻦ 500ﺧﺎﻧﮫ ، ﺑﻌﺪ أﺧﺬ اﻟﺠﺬر اﻟﺘﺮﺑﯿﻌﻲ أﺻﺒﺢ ﯾﺘﻜﻮن ﻣﻦ 250 ﺧﺎﻧﮫ
، اﻵن ﻃﺮﯾﻘﮫ Trial Division ﺳﻮف ﺗﻜﻮن ﻣﻀﯿﻌﮫ ﻟﻠﻮﻗﺖ واﻟﺠﮭﺪ ﻷﻧﮭﺎ ﺳﻮف ﺗﺨﺘﺒﺮ ﻣﻦ اﻟﺒﺪاﯾﺔ وﺣﺘﻰ ذﻟﻚ اﻟﻌﺪد اﻟﺬي ﯾﺘﻜﻮن ﻣﻦ 250 ﺧﺎﻧﮫ ، ﻟﺬﻟﻚ ﻟﻠﺘﻌﺎﻣﻞ ﻣﻊ اﻷﻋﺪاد اﻟﻀﺨﻤﺔ (ﻛﻤﺎ ھﻮ اﻟﺤﺎل ﻓﻲ اﻟﺸﻔﺮات اﻟﺤﺪﯾﺜﺔ) ﯾﺠﺐ اﻟﺒﺤﺚ ﻋﻦ ﺣﻞ أﻛﺜﺮ ﻛﻔﺎﺋﮫ .
وھﻨﺎك اﻟﻜﺜﯿﺮ ﻣﻦ اﻟﻄﺮق ﻟﮭﺬا اﻷﻣﺮ ، وﺳﻮف ﻧﺘﻨﺎوﻟﮭﺎ ﻓﻲ اﻟﻨﺴﺨﺔ اﻟﻨﮭﺎﺋﯿﺔ ﻣﻦ اﻟﻜﺘﯿﺐ ﺑﺈذن اﷲ ﺑﺎﻟﺘﻔﺼﯿﻞ ، وﻟﻜﻦ ﯾﻤﻜﻦ ﻟﺘﺴﺮﯾﻊ اﻷﻣﺮ اﺧﺘﺒﺎر اﻷﻋﺪاد اﻟﻔﺮدﯾﺔ ﻓﻘﻂ ﻓﻲ ﻃﺮﯾﻘﮫ . Trial Division
أﯾﻀﺎ ھﻨﺎك ﻃﺮﯾﻘﮫ Sieve of Eratosthenes ، وھﻲ ﺗﻌﺘﻤﺪ ﻋﻠﻰ ﻋﻤﻞ إﻟﻐﺎء ﺟﻤﯿﻊ ﻣﻀﺎﻋﻔﺎت اﻷﻋﺪاد 2 و 3و5 و7ﻣﻦ ﻣﺪى اﻷﻋﺪاد اﻟﻤﺮاد اﻟﺒﺤﺚ .
ﻣﺜﺎل ﻟﻠﺘﻮﺿﯿﺢ ، ﻧﺮﯾﺪ ﻣﻌﺮﻓﮫ اﻷﻋﺪاد اﻷوﻟﯿﺔ ﺑﯿﻦ 2 إﻟﻰ 99، ﻧﻘﻮم ﺑﻌﻤﻞ ﺟﺪول ﻓﯿﮫ ﺟﻤﯿﻊ ﺗﻠﻚ اﻷﻋﺪاد (ﻓﻲ اﻟﻐﺎﻟﺐ ﯾﻜﻮن ﻓﻲ ﻣﺼﻔﻮﻓﺔ) ، ﺑﻌﺪھﺎ ﻧﻘﻮم ﺑﺸﻄﺐ ﻣﻀﺎﻋﻔﺎت اﻟﻌﺪد 2 ﻣﻦ اﻟﺠﺪول ، وﻣﻀﺎﻋﻔﺎت اﻟﻌﺪد 3 ﻣﻦ اﻟﺠﺪول وھﻜﺬا ،
وھﻮ اﻵن ﯾﺤﺘﻮي ﻋﻠﻰ ﺟﻤﯿﻊ اﻷﻋﺪاد اﻷوﻟﯿﺔ ﻣﻦ 2 إﻟﻰ 99، ﻋﻠﻰ اﻟﻌﻤﻮم وﻛﻤﺎ ﻻﺣﻈﺖ أﻧﮭﺎ ﺳﻮف ﺗﺴﺘﻐﺮق ﻣﺴﺎﺣﮫ ﻛﺒﯿﺮة ﻓﻲ ﺣﺎﻟﮫ اﻟﻌﺪد اﻟﻤﺮاد اﺧﺘﺒﺎره ﻛﺒﯿﺮ ، ذﻟﻚ ھﻲ ﻏﯿﺮ ﻣﺴﺘﺨﺪﻣﮫ ﺑﻜﺜﺮة
.
ﺍﻟﻘﺎﺳﻢ ﺍﻟﻤﺸﺘﺮﻙ ﺍﻷﻋﻈﻢ Greatest Common Divisor (ﺍﺧﺘﺼﺎﺭﺍ اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﻌﺪدﯾﻦ ھﻮ أﻛﺒﺮ ﻋﺪد ﺻﺤﯿﺢ ﯾﻘﺒﻞ اﻟﻘﺴﻤﺔ ﻋﻠﻰ اﻟﻌﺪدﯾﻦ .
ﻣﺜﻼ ﻧﺮﯾﺪ ﻣﻌﺮﻓﮫ اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻛﺒﺮ ﻟﻠﻌﺪدﯾﻦ 30 ، . 18ﻧﻘﻮم ﺑﻤﻌﺮﻓﮫ ﺟﻤﯿﻊ ﻗﻮاﺳﻢ اﻟﻌﺪدﯾﻦ ، وﻧﺄﺧﺬ اﻟﻌﺪد اﻷﻛﺒﺮ ﻣﻦ ھﺬه اﻟﻘﻮاﺳﻢ :
30ﯾﻘﺒﻞاﻟﻘﺴﻤﺔﻋﻠﻰ1و2و3و5و6و10و15و30
18ﯾﻘﺒﻞاﻟﻘﺴﻤﺔﻋﻠﻰ1و2و3و6و9و18
ﻧﻼﺣﻆ ﻓﻲ اﻷﻋﺪاد اﻟﺴﺎﺑﻘﺔ أﻛﺒﺮ ﻗﺎﺳﻢ ﯾﻘﺒﻞ اﻟﻘﺴﻤﺔ ﻋﻠﻰ اﻟﻌﺪدﯾﻦ وھﻮ . 6
GCD(30,18) = 6
ﯾﻘﺎل ﻋﻦ ﻋﺪدﯾﻦ "أوﻟﯿﺎن ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ" Relatively Prime اذا ﻛﺎن اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﮭﻢھﻮ.1
اﻷزواج اﻟﺘﺎﻟﯿﺔ ﻣﻦ اﻷﻋﺪاد أوﻟﯿﻨﺎ ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ : Relatively Prime
اﻷزواج اﻟﺘﺎﻟﯿﺔ ﻣﻦ اﻷﻋﺪاد أوﻟﯿﻨﺎ ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ : Relatively Prime
8 و 9 ، ﻷن اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﮭﻢ ھﻮ . 1
23و44
27و55
اﻻﺷﺎره اﻟﺴﺎﻟﺒﺔ ﻻ ﺗﺆﺛﺮ ﻓﻲ ﺣﺴﺎب اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ:
GCD(x,y) = GCD(x,-y) = GCD(-x,y) = GCD(-x,-y) = GCD(|x|,|y|)
ﻣﺜﺎل
GCD(18,-54) = GCD(18,54) = 9
ﻷﺧﺬ اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﻤﺠﻤﻮﻋﮫ ﻣﻦ اﻷﻋﺪاد ﻧﻘﻮم ﺑﺄﺧﺬ اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﻌﺪدﯾﻦ ﻣﻨﮭﻢ ، واﻟﻨﺎﺗﺞ ﻧﺄﺧﺬه ﻣﻊ اﻟﻌﺪد اﻟﺜﺎﻟﺚ وھﻜﺬا .
ﻣﺜﺎل : اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ل 20: و 30 و 15 ھﻮ 5 وذﻟﻚ :
GCD(20,30) = 10
CGD(10,15) = 5
اذا ﻛﺎن اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﻤﺠﻤﻮﻋﮫ ﻣﻦ اﻷﻋﺪاد 1 = ، وﻛﺎن ھﻨﺎك زوج ﻣﻦ ھﺬه اﻷﻋﺪاد (أي ﻋﺪدﯾﻦ) اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ھﻮ ﻏﯿﺮ ) 1أي ﻟﯿﺲ أوﻟﯿﺎن ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ) ، ﻓﺄﻧﮭﺎ ﺗﺴﻤﻰ mutually relatively prime، أﻣﺎ ﻓﻲ ﺣﺎﻟﺔ ﻛﺎن ﺟﻤﯿﻊ اﻷزواج ﻣﻊ ﺑﻌﻀﮭﺎ ﯾﻜﻮن اﻟﻘﺎﺳﻢ ﯾﺴﺎوي واﺣﺪ ﻓﺈﻧﮭﺎ ﺗﺴﻤﻰ . pairwise relatively prime
ﻣﺜﺎل : ﻟﺤﺴﺎب اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﻸﻋﺪاد 28 و 126 و 21 و : 10
= ( (28,126) , 21 , 10)
= (14 , 21 , 10)
= ( (14,21) , 10)
= (7,10)
= 1
ﻻﺣﻆ اﻟﻨﺘﯿﺠﺔ ھﻲ واﺣﺪ ، ﺑﺎﻟﺮﻏﻢ ﻣﻦ أن ھﻨﺎك زوج ﻣﻦ اﻷﻋﺪاد ﻏﯿﺮ أوﻟﯿﺎن ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ ، . 7 = (28,126)
وﻓﻲ ھﺬه اﻟﺤﺎﻟﺔ ﺗﺴﻤﻰ ﻣﺠﻤﻮﻋﮫ اﻷﻋﺪاد . mutually relatively prime أﻣﺎ ﻓﻲ ﺣﺎﻟﮫ ﻛﺎن ﺟﻤﯿﻊ اﻷزواج ﻣﻦ اﻷﻋﺪاد أوﻟﯿﺎن ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ ﻓﺘﺴﻤﻰ ﻣﺠﻤﻮﻋﮫ اﻷﻋﺪاد ﺑـ pairwise relatively . prime
ﻣﺜﺎل :اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك ﻟﻸﻋﺪاد 18 و 9 و 25 ھﻮ 1 ، وﻣﻊ ذﻟﻚ ﻓﮭﻲ mutually relatively prime، ﻻن اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ل 18,9 ھﻮ 9(أي ھﻤﺎ ﻟﯿﺴﺎ أوﻟﯿﺎن ﻓﯿﻤﺎ ﺑﯿﻨﮭﻤﺎ) .
ﺧﻮﺍﺭﺯﻣﻴﺔ ﺃﻗﻠﻴﺪﺱ Euclidean Algorithm
اذا ﻛﺎن ﻟﺪﯾﻨﺎ ﻋﺪدﯾﻦ c,q ﺑﺤﯿﺚ c = q*d + r ، اذا . GCD(d,r) = GCD(c,q )
اﻟﻘﺎﻋﺪة اﻟﺴﺎﺑﻘﺔ ﻣﮭﻤﺔ ﺟﺪا ، وﻧﺴﺘﻄﯿﻊ ﻣﻦ ﺧﻼﻟﮭﺎ إﯾﺠﺎد اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ﻟﻠﻌﺪدﯾﻦ ﺑﺴﺮﻋﺔ .
ﻣﺜﺎل : أوﺟﺪ اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ 132 و 55 ﺑﺎﺳﺘﺨﺪام ﺧﻮارزﻣﯿﺔ أﻗﻠﯿﺪس :
132=55*2+22
55 =22*2+11
22 =11*2+0
ﻧﺘﻮﻗﻒ ﻋﻨﺪ اﻟﻮﺻﻮل إﻟﻰ اﻟﺼﻔﺮ ، وﯾﻜﻮن اﻟﻘﺎﺳﻢ اﻟﻤﺸﺘﺮك اﻷﻋﻈﻢ ھﻮ 11 وذﻟﻚ :
GCD(132,55) = GCD(55,22) = GCD(22,11) = GCD(11,0) = 11
ﻣﺜﺎل أﺧﺮ : أوﺟﺪ GCD(252,198) ﺑﺎﺳﺘﺨﺪام ﺧﻮارزﻣﯿﺔ أﻗﻠﯿﺪس ؟
252=198*1+54
198=54 *3+36
54 =36 *1+18
36 =18 *2+0
تعليقات
إرسال تعليق