• 
  Мұндай детерминирленген әдістерден айырмашылығы, біріншілікті тексерудің ықтималдық әдістері де бар. Зерттелетін сан үшін кездейсоқ сандармен байланысты кейбір шарттардың орындалуы тексеріледі. Егер осы шарттардың біреуі орындалмаса, онда N құрама сан болады. Егер барлық шарттар орындалса, онда кейбір ықтималдықпен N жай сан екенін дәлелдей аламыз. Бұл ықтималдық неғұрлым жақын болса, соғұрлым кездейсоқ сандарды тексереміз. Әдетте бұл шарттар Ферманың кіші теоремасына негізделеді, ол кез келген оң b саны үшін p қандай да бір жай саннан аспайтын,
  

б^(p–1) 1(mod p).
Мысалы, 2⁶64 63 + 1 1 (мод 7). Егер сіз r бүтін санының жай екенін анықтағыңыз келсе, онда r-ден кіші кез келген оң бүтін b санын таңдап, теңдігі бар-жоғын тексеруге болады.
б^(r–1) 1(modr).

622-БӨЛІМ



Егер теңдік орындалмаса, Ферма теоремасы негізінде r жай сан емес екеніне толық сенімді болуға болады. Егер теңдік орындалса, онда біз тек r жай сан деп есептей аламыз, сондықтан оны b негізінде жалған жай сан деп атаймыз. Құрама х санының кездейсоқ жалған негізгі болуының P(x) ықтималдығы х өскен сайын азаяды.

• 
  Өкінішке орай, Кармайкл сандары бар -
  

қасиеті бар тіркелген сандар

б^(r–1)1(mod r) [1, r] аралығынан r-ге тең болатын барлық b үшін.
Кармайкл санының мысалы 561 3 11 17. Сандар теориясының классикалық нәтижесі Чебышев теоремасы,
кейбір бүтін m санынан кіші натурал сандардың бөлігі және жай болу 1/(ln m)-ге жақын екенін көрсетеді. Мысалы, 10-нан кіші бүтін сандардың үлесі¹⁰⁰және қарапайым болу жақын

• 
  1/(журнал 10¹⁰⁰) 1/230. Осылайша, егер біз кездейсоқ түрде үлкен бүтін оң тақ санды таңдасақ және x, x + 1, x + 2, … сандарының жайлығын дәйекті түрде тексеретін болсақ, онда орташа есеппен қадамда жай сан бірінші рет кездеседі. ln x саны.
  

№5 Зертхана
АСИММЕТРИЯЛЫҚ ШИФРЛАУ ЖҮЙЕЛЕРІНДЕ ҚОЛДАНЫЛАТЫН ЖАҢАЙ САНДАРДЫ ТҰРУ
Жұмыс мақсаты:ашық кілтті шифрлау жүйелерінде қолданылатын жай сандарды генерациялау әдістерін зерттеу.
Зертханалық жұмыстың сипаттамасы.Зертхананы аяқтау үшін L_PROST.exe бағдарламасын іске қосу керек. Дисплей экранында мәтіндік редакторы бар терезе пайда болады (бағдарлама орындайтын әрекеттер туралы ақпаратты көрсету үшін), негізгі мәзір терезенің жоғарғы жолында орналасқан, негізгі мәзірдің дәл астында құралдар тақтасы (жылдам команданы басқару үшін) орналасқан. түймелері және басқа «ыстық» басқару элементтері) және терезенің ең төменгі жағында сынақ редакторының астында кеңестер мен қосымша ақпаратты беретін күй жолағы орналасқан. Құралдар тақтасының пернелері ыңғайлы болу үшін құралдар кеңестерімен қамтамасыз етілген.

---

Негізгі мәзірге өту үшін F10 пернесін басу керек. Негізгі мәзір арқылы жылжу курсор пернелері арқылы жүзеге асырылады. Мәзір элементіне қоңырау шалу үшін ENTER пернесін басу керек, ESC - негізгі мәзірден шығу.
Ыңғайлы болу үшін бағдарлама тінтуірмен жұмысты қамтамасыз етеді. Бұл жағдайда меңзер негізгі мәзірдің қажетті пунктіне жылжиды немесе

• 
  құралдар тақтасындағы қажетті түйме және тінтуірдің сол жақ түймесі басылады, бас тарту үшін ESC пернесін басу жеткілікті.
  

Негізгі мәзірдің негізгі функцияларынан басқа (Қарапайым Р құру, Іздеу аралығы, Бастапқылықты тексеру және т.б.) құралдар тақтасында басқан кезде бағдарлама туралы ақпаратты көрсететін перне бар.
Қарапайым P буыны.Жай санды құру мүмкіндігі; құрылған санның цифрларының санын пайдаланушы белгілейді (1-ден 5-ке дейін).
Аралықта іздеу.Берілген аралықта жай сандарды іздеу мүмкіндігі. Пайдаланушы интервалдың басын - x мәнін, аралық ұзындығын - L мәнін белгілейді. Іздеу (x, x + L) аралықта жүзеге асырылады.
Интервалдағы әрбір санның жайлығын тексеру кезінде алдымен бірінші жай сандарды ретімен бөлу сынағы, содан кейін Ферма сынағы орындалады. Бастылықты тексеру әдістерін орнату үшін тінтуірдің сол жақ түймешігімен құсбелгіні қойыңыз

642-БӨЛІМ



қалаған әдіс атауының жанында, содан кейін іздеуді бастау үшін барлық қажетті деректерді көрсетіңіз.

• 
  сынақтық бөлу әдісі, бастапқы деректер бөлуге арналған бірінші жай сандар саны болып табылады, ал Ферма тестінде сіз негіздердің санын және олардың мәндерін көрсетуіңіз керек.
  

Есептеу аяқталғаннан кейін экранда табылған жай сандар мен олардың саны көрсетіледі. Жұмыс нәтижелерінің толық суретін Шығару нәтижелері мәзір тармағында көруге болады.
Қарапайымдылықты тексеру.Кез келген санның жайлығын тексеру мүмкіндігі. Сан мен есептеу параметрлерін аралықтағы іздеуге ұқсас енгізу керек.
Нәтижелерді шығару.Соңғы өңдеудің барлық нәтижелерін көру мүмкіндігі. Бағдарламаға кіру кезінде, әлі есептеулер жасалмаған кезде, сынақ бөлімдерінің сынағы үшін пайдаланылған бірінші жай сандардың бастапқы файлын көруге болады.
Бағдарлама туралы қосымша ақпарат
1. Жай санды генерациялауға, аралықта іздеуге және қарапайымдылықты тексеруге арналған утилиталарды іске қосу кезінде пайдаланушыдан таңдалған әдістің жұмысқа жарамдылығын растау сұралады.

---

2. Ұзақ орындалатын процедуралардың жұмысы кезінде процестің барысы іске қосылады және мәтіндік редактордың терезесі өшеді. Орындау жолағында алгоритмнің шамамен жылдамдығын және ағымдағы процестің аяқталу уақытын байқауға және бағалауға болады.
3. сияқты жұмыс параметрлерін орнатқанда абай болыңыз

• 
  Есептеу процесінде бұл параметрлерді жұмыс барысында өзгерту мүмкін емес.
  

4. 
   «Ыстық» пернелердің сипаттамасы: Ctrl+F1 – қарапайым Р генерациясы; Ctrl+F2 – аралықта іздеу; Ctrl+F3 – қарапайымдылықты тексеру; Ctrl+F4 – нәтижелерді көрсету; Ctrl+X – бағдарламадан шығу.
   

4. 
   Зертханалық жұмыста санау уақытының ұзақ болуына байланысты бес цифрдан аспайтын сандарды пайдалану және 500-ден аспайтын интервал ұзындығын, ал Ферма сынағы үшін 5-тен көп емес негіздерді таңдау ұсынылады.
   

4. 
   Бағдарламаның дұрыс жұмыс істеуі үшін жұмыс каталогында (l_prost.exe файлымен бірге) болуы керек.
   

Зертхана №565



prost.txt және work.txt файлдарын жүріңіз. Бұл мәтіндік файлдарға қандай да бір өзгертулер енгізу ұсынылмайды, әйтпесе салдары күтпеген болуы мүмкін.
Жаттығу

1. 
   Кем дегенде 5 биттен тұратын екі ерікті бүтін санның бастапқылығын тексеріңіз.
   

2. 
   Жай сандарды бөлу.
   

2.1. [x, x + L] түріндегі интервал берілген. Интервалдағы P(x, L) жай сандар санын есептеңіз және L / ln(x) мәнімен салыстырыңыз. Қандай жағдайларда P(x, L)/L берілген x 2000, L 500, 5-15-ке бөлу үшін жай сандар саны, 1-2 негіздері үшін 1/ln(x) шамасына жақын болады?
2.2. (1000, 1000 + 300) аралықта барлық жай сандарды табыңыз. Көршілес екі жай санның айырмасы L(i) болсын. L(i) үшін гистограмма құру. Сіз есептеңіз -

Бораждық орташа L_орт.. ln(x) параметрімен салыстырыңыз, мұндағы x интервалдың ортасы. Берілген: үшін жай сандар саны
бөлімдер 5-20, негіз саны 1-3.
2.3. Берілген {k} сандар жиыны үшін k-ші жай санның формуласының салыстырмалы қатесін бағалаңыз:

б(k) k/log(k), k {10, 15, 20, 30, 35}.
3. Жай сандарды құру әдістері.
3.1. (500, 500 + 200) аралықта «Эратосфен елеуішінен» өтетін натурал сандардың салыстырмалы санының графигін тұрғызыңыз, яғни. бірінші k жай сандарға бөлінбейді.

Есептеу барлық k < үшін жасалады 10.
3.2. Аралық үшін (1500, 1500 + 300):

а) П-ның нақты мөлшерін есептеңіз₀аралықтағы жай сандар

білік, яғни. тексеру кезінде бөлінгіштікке арналған тестті ғана көрсетіңіз. Бірлескен
бірінші бөлінетін жай сандар саны анықталады

---

есептеуден, бөлуге арналған максималды сан квадратқа тең
интервалдың ең үлкен мәнінің түбірі;
б) Ферма тестінде сынақ бөлімдерінің аз саны және бір базасы бар тест жасаңыз. P мөлшерін есептеңіз₁осы сынақтан өткен ықтимал жай сандар;
в) алдыңғы жағдайдағыдан көп, сынақ бөлімшелерінің саны және екі немесе үш базасы бар сынақ жасау -

662-БӨЛІМ



Ферма сынағында mi. P санын есептеңіз₂бұл сынақты қанағаттандыратын жай сандар болуы мүмкін. Алынған мәліметтерді талдаңыз.
3.3. Берілген интервалда Кармайкл сандары бар екені белгілі. Оларды табыңыз.
Интервал опциялары: (1050, 1050 + 100);
(1700, 1700 + 100);
(2400, 2400 + 100).

4. 
   Есептегі бақылау сұрақтарына нұсқаның нөміріне сәйкес жауап беру (2.1-кесте).
   

	2.1-кесте
Сан	Бақылау сұрақтары
опция
1, 5, 7, 3,	Неліктен сынақтардағы бірінші база ретінде
9, 18, 28	Өте үлкен біріншілікті тексеру үшін ферма сынағы
	сандар 2 санын қолданған дұрыс па?
2, 4, 6, 8, 20,	Кездейсоқ алынған тақ санның P(x) ықтималдығы қандай?
22, 24, 26, 30	x-тен аспайтын үлкен сан жай сан болады?
11, 13, 15,	Есептеу:
10, 17, 19, 27	1812 (мод 13), 127 (мод 7)
12, 14, 16	Қарапайымдылық үшін тесттің мәнін тұжырымдаңыз
21, 23, 25, 29	сынақ бөлімдерін пайдалану

№6 зертхана

---

ЭЛЕКТРОНДЫҚ САНДЫҚ ҚОЛ
Жұмыс мақсаты:телекоммуникация желілерінде қауіпсіз электрондық құжат айналымы қағидаттарымен және электрондық қолтаңбаны орнату алгоритмдерімен танысу.
Зертханалық жұмыстың сипаттамасы.Электрондық құжаттарды телекоммуникация желілері арқылы алмасу құжаттарды өңдеу және сақтау құнын айтарлықтай төмендетеді, оларды іздеуді жылдамдатады, бірақ бұл түпнұсқалық растама мәселесін, яғни автордың түпнұсқалығын анықтау және алынған құжатта өзгерістердің болмауын тудырады.
Құжаттарды электронды түрде өңдеу кезінде қолмен қойылған қолтаңба және қағаз құжаттағы мөр арқылы аутентификацияның дәстүрлі әдістері жарамсыз, бұл жерде электронды қолтаңба принципті жаңа шешім болып табылады.
Электрондық қолтаңба- электрондық нысандағы басқа ақпаратқа (қол қойылған ақпарат) қоса берілетін немесе осындай ақпаратпен басқаша байланысты және ақпаратқа қол қойған тұлғаны сәйкестендіру үшін пайдаланылатын электрондық нысандағы ақпарат1.
Алғашқы электрондық цифрлық қолтаңба (ЭСҚ) схемасы2- RSA сонау 1970-ші жылдардың соңында әзірленді, бірақ авторлық растау мәселесінің өзектілігі соншалық, 1990-жылдары стандартты құру қажет болды. Оған жаһандық интернеттің кең таралуы және электронды коммерция мен қызмет көрсетудің жаппай таралуы себеп болды. Дәл осы себепті ЭСҚ стандарттары

• 
  Ресей мен Америка Құрама Штаттары дерлік бір уақытта, 1994 жылы қабылданды.
  

Криптологтар ұсынған ЭСҚ схемаларының ішінде ең сәттісі
Біз RSA және ElGamal схемасын аяқтадық. Олардың біріншісі АҚШ-та және басқа да бірқатар елдерде патенттелген (RSA патентінің мерзімі жақында бітті). Екінші схемада мүмкін болатын модификациялардың үлкен саны бар және олардың барлығын патенттеу өте қиын. Дәл осы себепті ЭльГамалдың EDS схемасы негізінен патенттерден бос қалды. Сонымен қатар, бұл схеманың белгілі практикалық артықшылықтары бар: алгоритмдер жұмыс істейтін блоктардың өлшемі және сәйкесінше ондағы ЭЦҚ өлшемі.

• 
  «Электрондық цифрлық қолтаңба туралы» 2002 жылғы 10 қаңтардағы бұрын күшіне енген Федералдық заңның орнына қабылданған 2011 жылғы 6 сәуірдегі № 63-ФЗ «Электрондық қолтаңба туралы» Федералдық заң.
  

²Аталған № 63 Федералдық заңға сәйкес «электрондық қолтаңба» және «электрондық цифрлық қолтаңба» ұғымдары синонимдер болып саналады.

---

Смотрите также файлы

• Волейбол. Нападающий удар.docx

• Бланк выполнения лабораторной работы 1.docx

• Условия и факторы необходимые человеку для сохранения своего психологического здоровья.docx

• Период Основной ресурс.docx

• Білім беру йымыны атауы 2 Ертіс жоббм.docx