А. Ж. Асамбаев криптография негіздері

 
89 
Құжатты қалпына келтіруімен цифрлық қол қоюды пайдаланғанда барлық хабарға 
қол қойылады, яғни ол шифрланады. Бірақ, қазір тәжірибеде олай істемейді. Ашық кілті 
бар шифрлау алгоритмдер баяу, одан әрі хабардың бүтіндігін растау үшін көп жад көлемі 
қажет  болады.  Және  де  ЭЦҚ  есептейтің  алгоритмдердің  барлығы  есеп  үшін  алдын  ала 
стандартты ұзындығы берілген хабарларды пайдаланады. Мысалы, ресей ГОСТ Р34.10-94 
алгоритмда  бұл  мөлшері  32  байтқа  тең.  Сондықтан,  уақытты  және  есептеу  ресурстарды 
үнемдеу  үшін,  ассиметриялық  алгоритм  әдетте  бір  бағытталған  хеш-функциямен  бірге 
пайдаланады. Мұнда басында хеш-функция көмегімен кез келген ұзындығы бар хабардан 
керекті мөлшері бар хеш-код есептеледі, сосын ЭЦҚ есептеу үшін алдында алынған хеш-
код шифрланады.  
Құжаттын хеш-коды бойынша есептелген ЭЦҚ қосылатын цифрлық қол қоюлар 
деп  аталады.  Осындай  цифрлық  қолдар  кейбір  сандық  коды  болып  табылады  және  оны 
қол  қойылатын  құжатқа  тіркеу  қажет.  Хабардың  өзі  бұл  жағдайда  шифрланбайды  және 
ашық түрде цифрлық қолмен бірге жіберіледі.  
Егер пайдаланушы А пайдаланушы Б-ға қосылған цифрлық қолмен толықтырылған 
хабар  М  жібергісі  келсе,  онда  қол  қоюды  жасау  және  тексеру  процедурасы  келесі 
қадамнан тұрады:  
1.  Пайдаланушы  А  пайдаланушы  Б-ға  өзінің  ашық  кілтің  U  кез  келген  байланыс 
арна арқылы жібереді, мысалы электронды поштамен. 
2. Пайдаланушы А сенімді хеш-функциясы Н көмегімен өз хабарының хеш-кодын  
h = H(M) есептейді.  
3.  Сосын  пайдаланушы  А  хабардың  хеш-кодын  h  өзінің  жабық  R  кілтімен 
шифрлайды және цифрлық қолды С алады. 
4. Бастапқы хабар М цифрлық қолмен С бірге пайдаланушы Б-ға жіберіледі. 
5.  Пайдаланушы  Б  алынған  хабардың  М  хеш-кодын  h  есептейді,  сосын 
пайдаланушы А-ның ашық кілтің пайдаланып цифрлық қолды С тексереді.  
Бұл протоколды схема түрінде көрсетуге болады (сур. 9.3). 
 
 
 
Сурет 9.3. Цифрлық қол қоюды жасау және тексеру схеманың екінші варианты 
 
Хеш-функция  ЭЦҚ-ң  алгоритмнын  құрамына  кірмейді,  сондықтан  схемада  кез 
келген сенімді хеш-функция пайдалану мүмкін. 

 
90 
Суреттелген  қол  қоюды  жасау  процесі  конфиденциалдықты  қамтамасыз  етпейді. 
Яғни  осы  тәсілмен  жіберілген  хабарды  өзгертуге  болмайды,  бірақ  жіберушінің  ашық 
кілтің пайдаланып оқуға болады.  
Көп  жағдайда  келтірілген  цифрлық  қолды  жасау  және  пайдалану  схемасы  әбден 
жеткілікті.  Бірақ  пайдаланушы  Б  алаяқтық  жасау  жағдайлары  да  болады.  Мысалы, 
жіберілген  құжат  А  пайдаланушының  чегі  болсын  (қызмет  еткен  үшін).  Пайдаланушы  Б 
цифрлық  қолдың  дұрыстығын  анықтап  оны  ақша  алу  үшін  пайдаланды.  Бірақ, 
пайдаланушы Б қол қойылған құжаттан бір не бірнеше көшірме жасап алып, анда-санда 
банкіге барып ақша алу мүмкін.   
Осындай  алаяқтықты  болдырмау  үшін  цифрлық  қолдарға  жиі  қосады  уақыт 
белгісін. Құжатқа қол қойлған дата мен уақытты хабарға қосып құжатпен бірге қол қояды. 
Чек арқылы төлем жасағанда уақыт белгісін банк байқап деректер қорына енгізу мүмкін. 
Енді чекты қайтадан пайдаланатын болса, бұл көрініп қалады.  
 Цифрлық  қол  қоюдын  өзге  түрі  мойындамайтың  цифрлық  қол.  ЭЦҚ-дан  оның 
айырмашылығы – қол қойған адам рұқсат бермесе қолды тексеруге болмайды. Сонымен, 
құжатты алушы хабарға қол қойған адамның рұқсатын алмай қол қоюды көрсете алмайды 
(немесе қолдың дұрыстығын дәлелдей алмайды). 
 
9.5 Ассиметриялық алгоритмдерді пайдаланып құпиялы кілтті құрастыру 
 
Тәжірибеде  ашық  кілті  бар  алгоритмдер  хабарларды  тікелей  шифрлау  үшін  сирек 
пайдаланады. Бұған әсер етеді үлкен дерекетер көлемін шифрлау мен дешифрлау кезінде 
ассиметриялық  алгоритмдердің  аса  үлкен  емес  жылдамдығы.  Өйткені,  ашық  кілті  бар 
жүйелерде  негізгі  операция  500-1000  битты  сандарды  үлкен  модулі  бойынша  дәрежеге 
көтеру.  Бірақ,  қысқа  деректер  блогын  өңдегенде,  мысалы  белгілі  ұзындығы  бар  кілттер, 
бұл алгоритмдер жеткілікті тиімді болу мүмкін. Сондықтан, келесі құрамды схеманы жиі 
пайдаланады:  ассиметриялық  алгоритм  сессияның  кілтің  келісілу  үшін  қолданылады,  ал 
сосын  бұл  кілт  хабарларды  симетриялық  алгоритмымен  шифрлау  үшін  құпиялы  кілт 
ретінде шығады.  
Сессияның құпиялы кілтті құрастырудың қарапайым протоколы келесі түрде болу 
мүмкін  (егер  кейбір  байланыс  жүйенің  пайдаланушылары  кілттерді  үлестіру 
орталығындағы ашық кілттер деректер базасына рұқсат алып отырса, олар одан бір бірінің 
ашық кілттерің алып отырар еді): 
1.  Пайдаланушы  А  пайдаланушы  Б-ның  ашық  кілтің  кілттерді  үлестіру 
орталығынан алады немесе тура пайдаланушы Б-ның өзінен.  
2. Пайдаланушы А кездейсоқ сеанстық кілтті генерациялайды және алынған ашық 
кілтпен оны шифрлайды. 
3. Шифрланған сеанстық кілт пайдаланушы Б-ға жіберіледі.  
4. Пайдаланушы Б алынған пакетті өзінің жабық кілтімен ашып оқиды. 
5. Пайдаланушылар А және Б келісілген сеанстық кілтті шифрланған хабарлармен 
алмасу үшін пайдаланады. 
А  және  Б  қос  пайдаланушылардың  шифрлау  –  дешифрлау  үшін  ортақ  құпиялы 
кілтті К құрастыру схемасын келесі түрде көрсетуге болады (сур. 9.4). 
 

 
91 
 
 
Сурет 9.4. Ортақ құпиялы кілтті құрастыру схемасы 
 
Бұл  схема  9.1  суреттегі  схемаға  ұқсайды,  өйткені  онда  да  ашық  кілтпен  шифрлау 
тәртібі  пайдаланады.  Айырмашылығы  тек  нені  шифрлауда.  9.4  суреттегі  схемада  аса 
үлкен  емес  сеанстық  кілт  шифрланады,  ол  әрі  қарай  симметриялық  шифрлауда  құпиялы 
кілт  ретінде  пайдаланады.  Үлкен  емес  деректер  блоктың  шифрлауы  жеткілікті  тез 
орындалады  және  мындаған  пайдаланушылары  бар  жүйедегі  телекоммуникациялық 
процестерді тежелемейді.  
 
9.6 Ашық кілті бар шифрлау алгоритмге қойылатын талаптар 
 
Ашық  кілті  бар  шифрлау  алгоритмның  негізгі  қолданылу  тәсілдерін  қарастырып, 
Диффи  мен  Хеллманның  пікір  бойынша  ашық  кілті  бар  шифрлау  алгоритмы 
қанағаттандырылатын талаптарды зерттейік. Бұл талаптар келесі: 
1. Есептеу жағынан оңай қостарды (ашық кілт, жабық кілт) жасау. 
2. Есептеу жағынан оңай ашық кілтпен хабарды шифрлау. 
3. Жабық кілтті пайдаланып есептеу жағынан хабарды оңай дешифрлау. 
4. Ашық кілтті біліп сәйкес жабық кілтті есептеу жағынан анықтау мүмкін емес. 
5.  Ашық  кілтті  және  шифрланған  хабарды  ғана  біле  тұрып  бастапқы  хабарды 
есептеу жағынан қалпына келтіру мүмкін емес. 
Осы  жалпы  талаптардан  көрініп  тұр,  ашық  кілті  бар  нақты  алгоритмды  жүзеге 
асыруы сәйкес бір жақты функцияға тәуелді. 
Біз  қарастырамыз  ашық  кілті  бар  төрт  алгоритмды,  олардың  үшеуі  тәжірибеде 
бұрынғыдан  қолданылады,  ал  төртіншісі  ақпаратты  қорғау  жүйелерде  жақында  ғана 
пайдалана  басталды.  Бұл  алгоритмдер  әдетте  түрлі  мақсаттар  үшін  пайдаланады  (9.1 
кестені қараңыз). 
 
Кесте 9.1. Ашық кілті бар алгоритмдер 
Алгоритмның аты 
Пайдалану мүмкіндігі 
Деректерді шифрлау 
/ дешифрлау 
Цифрлық 
қол қою 
Кілтті келісу 
немесе құрастыру 
RSA 
Иә 
Иә 
Иә 
Диффи-Хеллман алгоритмы 
Жоқ  
Жоқ  
Иә 
Эль-Гамаль алгоритмы 
Иә 
Иә 
Иә 
Эллиптикалық қисықтарды 
пайдаланатын алгоритмдер  
Иә 
Иә 
Иә 

 
92 
 
Тағы айта кетейік, барлық ассиметриялық алгоритмдер белгілі бір математикалық 
функцияларға  негізделген.  Олардың  жұмыс  істеуінің  дәлелдеуі  күрделі  болу  мүмкін, 
сондықтан  біз  тек  жұмысының  негізгі  принциптерін  ғана  зерттейміз.  Криптографиялық 
алгоритмдердің  көбі  классикалық  сандар  теориясына  негізделеді.  Бұл  теорияның 
негіздерімен біз төменірек таңысамыз.  
 
 
Негізгі терминдер 
 
Ашық 
кілті 
бар 
шифрлау 
алгоритмы 
(немесе 
ассиметриялық 
криптоалгоритмы)  –  шифрлау  мен  ашып  оқу  үшін  әртүрлі  кілттерді  пайдаланатын 
криптографиялық алгоритм. 
Жабық кілт - ассиметриялық криптографиялық алгоритмдерде пайдаланатын кілт, 
ол жасырыну түрде сақталыну керек.  
Бір  жақты  функция  –  есептеуге  оңай,  бірақ  функцияның  мәні  бойынша  оған 
сәйкес  аргументты  табуы  қиын  математикалық  функция.  Яғни  х  біле  отырып  f(x)-ты 
есептеуге оңай, бірақ белгілі f(x) бойынша сәйкес келетің  х мәнің табу қиын.  
Люкы бар (немесе құпиясы бар) бір жақты функция – бұл кейбір құпиясы (люк) 
бар  бір  жақты  функциялардың  ерекше  түрі,  ол  функцияның  кері  мәнің  жеткілікті  тез 
есептеуге мүмкіндік береді. 
Ашық кілт - ассиметриялық криптографиялық алгоритмдерде пайдаланатын кілт, 
оны жасырыну түрде сақтамасада болады. 
Қосылатын цифрлық қол қоюлар – құжаттың хеш-коды бойынша есептелген қол 
қоюлар. Осындай қол қоюлар кейбір сандық коды түрінде болады және оны қол қоятың 
құжатқа  тіркеу  керек.  Мұнда  хабардың  өзі  шифрланбайды  және  ашық  түрде  цифрлық 
қолмен бірге жіберіледі. 
Цифрлық  (электронды)  қол  қою  (digital  signature)  –  берілетің  ақпараттың 
авторлығын тексере алатын, оған бірегей сандық қосымшасы. Электронды (цифрлық) қол 
қою (ЭЦҚ) тіркелген ұзындығы бар биттер тізбегі  болып табылады, ол белгілі  бір түрде 
ақпараттың ішіндегісі мен және құпиялы кілт көмегімен есептеледі. 
Құжатты  қалпына  келтіруімен  цифрлық  қол  қою  –  мұнда  құжат  қолдың 
құрамына кіретіндей болады: қолды тексеру барысында автоматты түрде құжат денесі де 
есептеледі.  Егер  ашып  оқыған  кезде  хабар  дұрыс  қалпына  келсе,  онда  қойылған  қол  да 
дұрыс деп саналады. 
 
 
Сұрақтар 
 
1. Ассиметриялық шифрлау алгоритмның симметриялықтан айырмашылығы неде? 
2.  Ашық  кілті  бар  шифрлау  алгоритмдер  тәжірибеде  қандай  есептерді  шешуге 
қолданылу мүмкін? 
3.  Қандай  математикалық  функциялар  бір  жақты  деп  аталады?  Криптографияда 
олар не үшін қолданылу мүмкін? 
4. Цифрлық қол қою деген не? 
5.  Ашық  кілті  бар  шифрлау  алгоритмдерді  пайдаланғанда  цифрлық  қол  қоюды 
құрастыру алгоритмы қандай болады? 
6. Пайдаланушылар тобында ортақ құпиялы кілтті құрастыру үшін ашық кілті бар 
шифрлау алгоритмдер қай түрде пайдалану мүмкін? 
7. Ассиметриялық алгоритмдерге қойылатын талаптар қандай? 
 
 

 
93 
10 АШЫҚ КІЛТІ БАР КРИПТОГРАФИЯДА ПАЙДАЛАНАТЫН 
 
САНДАР ТЕОРИЯСЫНЫҢ НЕГІЗГІ ҚАҒИДАЛАРЫ
 
 
Ашық  кілті  бар  шифрлау  алгоритмдар  симметриялық  шифрлау  алгоритмдарға 
қарағанда  математикалық  функциялар  қасиеттеріне  көбірек  негізделген,  сондықтан  бұл 
бөлімде негізгі математикалық ұғымдары мен фактілер тұжырымдалған: жай және құрама 
сандар;  арифметиканың  негізгі  теоремасы;  өзара  жай  сандар  және  Эйлер  функциясы; 
қалдықтар  арифметиканың  негіздері  және  салыстыру  теориясы;  Ферманың  кіші 
теоремасы;  ең  үлкен  ортақ  бөлгіш  және  Евклидтың  жалпыланған  алгоритмы;  модулі  m 
бойынша инверсия.  
Бөлім  мақсаты:  ашық  кілті  бар  криптографияда  пайдаланылатын  сандар 
теориясының негізгі қағидаларын баяндау. 
  
10.1 Жай және құрама сандар 
 
Әрбір бірден үлкен натурал сан ең азы екі санға бөлінеді: 1-ге және өз өзіне. Егер 
санның өзінен және бірден басқа бөлгіші болмаса, оны жай сан деп атайды, ал егер санда 
тағы  бөлгіштері  болса,  онда  құрама  деп  атайды.  Бірді  не  жай  не  құрама  деп  атамайды. 
Мысалы, 7, 29 сандар — жай; 9, 15 сандар — құрама (тоғыз 3-ке бөлінеді, он бес 3 пен 5-
ке бөлінеді). 
Қызықты  факт:  егер  екі  жай  сандардың  айырмашылығы  2-ге  тең  болса,  онда 
оларды «егіз»-сандар деп атайды. «Егіз»-сандар аса көп емес. Мысалы, 5 пен 7, 29 бен 31, 
149  бен  151  «егіздер»,  және  де  242  206  083*2
38  880
±1  (қазіргі  уақытқа  дейін  табылған  ең 
үлкен «егіз» жұбы). 
Сан  жай  ма  немесе  құрама  ма  -  тұра  айту  оңай  емес.  Егер  сан  жүзден  кем  болса, 
осындай  сұраққа  жауапты  табу  қиын  емес.  Бірақ  үлкен  сандарды  анықтау  күрделілен 
болады.  Мысалы,  2009  санды  алайық.  Ол  жай  немесе  құрама  ма?  Осы  санның  мүмкін 
бөлгіштерін  алғашқы  жай  сандар  арасынан  іздеп  табайық.  2009  әрине  2-ге  бөлінбейді 
(өйткені  ол  тақ),  3-ке  бөлінбейді  (өйткені  оның  цифрлер  қосындысы  2+9=11  3-ке 
бөлінбейді),  5-ке  де  бөлінбейді.  Ал  2009-ды  7-ге  бөлетін  болсақ,  нәтижесінде  –  287 
аламыз. Сонымен, жауап: 2009 саны – құрама. Мұнда жауап тез табылды. Бірақ, өте үлкен 
бүтін сандарды жайлыққа тексеру көп  уақыт  алады, және ол үшін арнайы компьютерлік 
программалар пайдаланады.  
Үлкен  жай  сандарды  іздеу  математикадан  басқа  криптографияға  да  өте  маңызды, 
олар  ашық  кілті  бар  шифрлау  алгоритмдарда  пайдаланылады.  Шифрлаудың  сенімділігін 
қамтамасыз ету үшін онда ұзындығы 1024 битке дейін жай сандар пайдаланады. 
Екі  санды  көбейту  қиын  емес,  әсіресе  калькулятор  бар  болғанда  және  сандар  аса 
үлкен  болмаса.  Кері  есеп  те  бар  –  факторизациялау  есебі  –  көбейткенде  берілген  санды 
беретін екі не одан көп санды табу. Бұл есеп көбейтуден өте күрделі. Мысалы, егер бізге 
67-ң 113-ке көбейтуі керек болса, онда нәтижесін 7571 бір минуттан тез табуға болады. Ал 
егер бізге көбейтіндісі 7571-ге тең екі санды тап десе, оған анағұрлым көп уақыт кетеді.   
n санның көбейткіштерін іздестіруін  n-ге дейін барлық жай сандарды іріктеп алып 
жүргізуге болады, мысалы 2009 сан сияқты. Бірақ, егер көбейткіштер – үлкен жай сандар 
болса, онда оларды іздеуге көп уақыт кетеді. 
Сонымен,  үлкен  санды  факторизациялау  едәуір  уақыт  қажет  етеді  (бұл  сан  екі 
үлкен жай сандардың көбейтіндісі белгілі болғанда да).  
Факторизациялау  есебінің  күрделілігі  кейбір  криптографиялық  алгоритмда 
пайдаланылады, мысалы, RSA шифрлау жүйесінде. 
 
 
 
 

 
94 
10.2 Арифметиканың негізгі теоремасы 
 
Кез  келген  құрама  санды  көбейту  көмегімен  кейбір  жай  сандардан  құрастыруға 
болады. Мысалы, 2009 құрама санды былай табуға болады: 
2009 = 7   7   41 
Математикада  арифметиканың  негізгі  теоремасы  қарастырылады,  ол  бойынша 
кез  келген  натурал  сан  (n>1)  не  өзі  жай  болады,  не  жай  бөлгіштердің  көбейтіндісіне 
жалғыз ғана тәсілмен жіктелу мүмкін (көбейткіштердің жол ретін еске алмағанда). 
Дәреже  белгіні  қолданып  2009  санды  жай  көбейткіштерге  жіктелуі  былай 
жазылады: 
2009 = 7
2
   41 
Көбейткіштерге  жіктеу  канондық  деп  аталады,  егер  барлық  көбейткіштер  жай 
болып өсу ретінде жазылатын болса.  
Мысалы, 150 санның көбейткіштерге канондық жіктелуін жазайық:  
150 = 2   3   5
2
 
 
10.3 Өзара жай сандар және Эйлер функциясы 
 
Екі сан өзара жай деп аталады, егер олардың бірден басқа ешқандай ортақ бөлгіші 
болмаса.  
Мысалы, 11 мен 12 сандар өзара жай (оларда бірден басқа ортақ бөлгіші жоқ),  30 
және 35 сандар — өзара жай емес (оларда ортақ бөлгіші 5 бар). 
Бүтін  сандармен  байланысты  заңдылықтарды  көп  зерттеген  болатын  швейцар 
математигі Леонард Эйлер (Leonard Euler). Олардың арасындығы: n-ды аспайтын және n-
мен  өзара  жай  болатын  қанша  натурал  сандар  бар?  Бұл  сұраққа  жауапты  Эйлер  1763 
жылы  тапты  және  осы  жауап  n  санның  жай  көбейткіштерге  канондық  жіктелуіне 
байланысты.  
Егер  
an
n
a
a
p
p
p
n
...
2
2
1
1
, 
мұндағы p
1
, p
2
,..., p
n
 – әртүрлі жай көбейткіштер, 
болса,  онда  n-нан  аспайтын  және  n-мен  өзара  жай  болатын    натурал  сандарды  былай 
табуға болады: 
n
p
p
p
n
n
1
1
...
1
1
1
1
)
(
2
1
 
n-нан  аспайтын  және  n-мен  өзара  жай  болатын  натурал  сандардың  саны  Эйлер 
функциясы деп аталады және белгіленеді  (n).  
Мысалы,  12-ден  аспайтын  және  12-мен  өзара  жай  болатын  натурал  сандар  саның 
табайық. Натурал сан қатарынан 
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 
12-мен  өзара  жай  болатын  тек  1,  5,  7,  11  сандар.  Олардың  саны  төртке  тең.  Сонымен 
(12)=4. 
Енді  (12)  Эйлер  формуласы  бойынша  есептеп  көрейік.  Ол  үшін  алдымен  12 
санның канондық жіктеуін жазамыз: 
12 = 2
2
 * 3. 
Эйлер функциясын  (12) есептейік:  
4
3
2
2
1
3
4
3
1
1
2
1
1
12
)
12
(
. 
Өзара  жай  сандарды  қарапайым  іріктеп  алудан  және  Эйлер  формула  бойынша 
есептелген мәндер сәйкес келеді.  

 
95 
Эйлер  формуласын  үлкен  n  үшін  пайдалану  ыңғайлы,  егер  n  санның  жай 
көбейткіштеріне  жіктеуі  белгілі  болса.  Криптографияда  Эйлер  формуласының 
маңыздылығы  –  жай  және  кейбір  басқа  сандар  үшін  (n)  санды  оңай  табу  мүмкіндігі. 
Криптографияда Эйлер формуласының келесі екі салдары пайдаланылады. 
1-ші салдары. Егер  p – жай сан, онда   (p) = p - 1. 
Шынында, егер  p – жай сан, онда оның канондық жіктеуі тек өзінен ғана тұрады. 
Сонда  
1
)
1
(
1
1
)
(
p
p
p
p
p
p
p
. 
2-ші салдары. р мен q — екі әртүрлі (р   q) жай сан болсын. Онда  
(p q) = (p – 1)(q – 1). 
Бұл формула келесі түрде түсіндіріледі. р q = N, мұнда р мен q — екі әртүрлі (р   q) жай 
сан болсын. Сонда 
)
1
(
)
1
(
)
1
(
)
1
(
1
1
1
1
)
(
)
(
q
p
q
p
q
p
q
p
q
p
N
N
q
p
. 
Эйлер формуласы пайдалануының бірнеше мысалдарын қарап шығайық. 
Мысал  1.    (13)  табайық.  13  –  жай  сан,  сондықтан,  1-ші  салдарды  пайдаланып 
(13)  =  13-1  =  12.    Өзімізді  (және  Эйлерді)  тексерейік,  ол  үшін  13-тен  кем  барлық 
сандарды жазып: 
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 
олармен өзара жай барлық сандарды санайық. Шынында олар 12. 
Мысал 2.    (35) табайық. 35 – құрама сан, демек бірінші салдары бізге келмейді. 
Бірақ  35  екі  жай  санның  көбейтіндісі:  35  =  5 7.    2-ші  салдарды  пайдаланып,  есептейміз 
(35):    
(35) = (5-1) (7-1) = 4 6 = 24. 
35 тен кем және онымен ортақ бөлгіштері жоқ барлық сандарды жазып тексереміз: 
1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 
27, 29, 31, 32, 33, 34. 
Шынында олардың саны 24.  
Соңғы  мысалдан  көрініп  тұр  –  көп  сандарды  қарастырғанша,  Эйлер  формуласын 
пайдалану ыңғайлы.  
 
10.4 Қалдықтар арифметикасы және салыстыру теориясы 
 
Неміс математигі Карл Фридрих Гаусс екі a мен b саны үшін 
a   b (mod m) 
жазуды  ұсынған  болатын,  егер  оларда  m-ға  бөлуден  бірдей  қалдықтары  бар  болса  (a 
модулі m бойынша b-мен салыстырлу деп оқылады). Мысалы, 
1997   1 (mod 4), 
7k + 1   1 (mod 7), мұндағы k – кез келген бүтін сан. 
Салыстыруларда  математиктар  мен  криптографтарға  пайдалы  қасиеттер  бар,  олар 
көбінесе теңдіктер қасиеттеріне ұқсайды. Бұл қасиеттер арифметикалық есептеулерді тым 
оңайлатады,  егер  бізге  тек  кейбір  m  санға  бөлудін  қалдығы  керек  болса.  Мысалы, 
салыстыру қасиеттер ашық кілті бар шифрлау алгоритмдағы есептеуде пайдалы.  
Салыстырулардың қарапайым қасиеттері келесі. 
1-ші қасиет. Егер a-b  m-ға бөлінсе, онда  a   b (mod m). 
Мысалы, 15   1 (mod 7), өйткені 15-1 = 14, ал 14  7-ге еселі. 
2-ші қасиет. Егер 
a   b (mod m) 
және 

 
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). 

жүктеу/скачать 2,01 Mb.

Достарыңызбен бөлісу: