Қазақстан республикасы білім және ғылым министрлігі павлодар мемлекеттік педагогикалық институты

 
96 
c   d (mod m) 
онда 
a + c   b + d (mod m) 
ac   bd (mod m). 
Мысалы, 13   5 (mod 8) және 11   3 (mod 8) болғандықтан, онда 13+11   5+3   0 (mod m), 
және де 13 11   5 3   7 (mod m). 
3-ші қасиет. Егер 
a   b (mod m) 
онда 
a
k
   b
k
 (mod m),  k   N. 
Мысалы, 25   4 (mod 7) болғандықтан, онда 5
2
   2
2
 (mod 7). 
4-ші қасиет. Егер 
ac   bc (mod m) 
және c  m-мен өзара жай болса, 
онда 
a   b (mod m). 
Мысалы, 1200   45 (mod 7) белгілі, ал 1200 = 15 80 және 45 = 15 3, онда 
80   3 (mod 7). 
5-ші қасиет. Егер 
ac   bc (mod mc) 
онда 
a   b (mod m). 
Мысалы, егер 44   4 (mod 4(10)) онда 11   1 (mod 10). 
 
10.5 Ферманың кіші теоремасы 
 
RSA  жүйесі  бойынша  шифрлау  алгоритмның  негізінде  XVII  ғасырдың  басында 
француз  математигі  Пьер  Ферма  (Pierre  Fermat)  тұжырымдаған  теорема  жатыр.  Оны 
«Ферманың кіші теоремасы» деп жиі атайды, және танымал «Ферманың ұлы теоремасы» 
мен  шатастырмау  керек.  Оны  да  ол  дәлелдемей  тұжырымдаған  болатын,  ал  дәлелденген 
тек  1993-94  жылдары.  Леонард  Эйлер  1760  жылы  Ферманың  кіші  теоремасын  дәлелдеп, 
оның  Ферма-Эйлер  теоремасы  деп  аталатын  жалпылауын  тапқан  болатын.  Дәл  осы 
теорема шифрлау/дешифрлау RSA алгоритмда пайдаланады.  
Ферманың кіші теоремасы келесі түрде тұжырымдалады. Егер р – жай сан, ал m – 
р-ға бөлінбейтің кез келген сан болса, онда  
m
p-1
   1 (mod р), 
яғни m
p-1
 саны р-ға бөлінгенде қалдықта 1 береді.  
Мысалы, р=11, m = 3 болсын. 3
10
 mod 11 біргі тең болама тексерейік: 
3
10
 mod 11 = 3
2
(((3
2
)
2
)
2
) mod 11 = 9(4
2
) mod 11 = 144 mod 11 = 1 
Эйлер тұжырымдаған және дәлелдеген жалпылау кез келген модуль үшін әділетті, 
бірақ  RSA  жүйеде  дербес  жағдайы  пайдаланылады  –  онда  модуль  тек  екі  түрлі  жай 
сандарының  көбейтінідісі  болып  табылады.  Сондықтан  осы  жағдайы  үшін  теореманың 
тұжырымдамасын қарастырайық. 
Ферма-Эйлер теоремасы (RSA жүйенің жағдайы үшін). Егер  p мен  q – екі  түрлі 
жай сандар, ал m – p мен q-ға бөлінбейтің кез келген сан болса, онда 
m
(p-1)(q-1)
   1 (mod рq). 
Мысалы,  р = 11, q = 5 (pq = 55), m = 3 болсын. 3
40
   1 (mod 55) біргі тең болатының 
тексерейік: 
3
40
 mod 55 = (3
5
)
4 
mod 55 = 23
4
 mod 55 = 279841 mod 55 = 1. 
 
 

 
97 
10.6 Ең үлкен ортақ бөлгіш 
 
а мен b — екі бүтін оң сандар болсын. а мен b сандардың ең үлкен ортақ бөлгіші - 
бұл а-ны да b-ны да бөлетін ең үлкен с саны: 
с = ЕҮОБ(a, b). 
Мысалы,  ЕҮОБ(25,35) = 5. 
Ең  үлкен  ортақ  бөлгішті  табу  үшін  келесі,  Евклид  алгоритмы  деп  аталатын, 
алгоритмды пайдалануға болады. 
Алгоритм NOD(бүтін a, b, c); 
Басы 
   1. a<>b болғанша орындау керек: 
         1.1. Егер a>b онда a:=a-b, әйтпесе b:=b-a; 
   2. c:=a; 
Соңы. 
 
Алгоритм орындалғаннан кейін нәтижесі с айнымалының ішінде болады.  
Евклид алгоритмы көмегімен ЕҮОБ(18,9) есептеп көрейік: 
a:    18    9 
b:     9    9 
c:     9    9 
Мұнда әрбір баған алгоритмның кезекті итерациясы болып табылады. Процесс жүргізіледі 
b    a-ға  тең  болғанша.  Сонда  с  айнымалыға  жауап  жазылады,  біздің  жағдайда  9.  Дәл  осы 
ЕҮОБ(18,9)-ң мәні.  
 
10.7 Евклидтың жалпыланған алгоритмы 
 
Көптеген  криптографиялық  жүйелер  үшін  Евклидтың  жалпыланған  алгоритмы 
актуальды, онымен келесі теорема байланысады. 
Теорема. а мен  b — екі  бүтін оң сандар болсын. Сонда  х пен у бүтін (оң емес те 
болу мүмкін) сандар бар болады, олар үшін  
ах + by = ЕҮОБ(a,b). 
Евклидтың  жалпыланған  алгоритмы  ЕҮОБ(а,  b)-ны  және  жоғары  жазылған 
теңдеуге сай келетін х, у іздеп табу үшін қызмет етеді. Үш жол енгізейік U = (u
1
,u
2
,u
3
), V = 
(v
1
,v
2
,v
3
) және T = (t
1
,t
2
,t
3
). 
Алгоритм келесі түрде жазылады (кіру параметрде шарт a b орындалу керек). 
Алгоритм ЕЖА(бүтін a, b); 
Басы 
  1. U = (a,1,0), V = (b,0,1). 
  2. v1 <> 0 болғанша орындау керек: 
    2.1. q = u1 div v1; 
    2.2. T =(u1 mod v1, u2–qv2, u3–qv3); 
    2.3. U=V, V=T. 
  3. U=(ЕҮОБ(a,b),x,y)). 
Соңы. 
 
Алгоритм аяқталғаннан кейін нәтижесі U жолында болады. Алгоритмдағы div операциясы 
– бұл бүтін сандық бөлу операция.  
Мысалы.  а  =  18,  b  =  9  болсын.  Теңдеуге  сай  келетін  х  және  у  сандарды  іздеп 
табайық 
18х + 9y = ЕҮОБ(18,9). 
 
Алгоритмды қадам бойынша орындайық: