4.2 жүйені іске асыру үшін алгоритмдер
Бұдан әрі бағдарлама кодын жазу кезінде тікелей қолданылған алгоритмдерді
келтіреміз.
АD (MOD m)
1.А 0=а салайық, әрбір келесі ас мына формула бойынша есептейміз
ai=ai-
2.Және = d кезінде А d(mоd m) ізделетін мәнін аламыз.
НСД (А, b) іздеудің Евклид алгоритмі.
1.R - А-ға бөлуден қалған қалдықтарды (ортақтықты бұзбай, а b деп санауға
болады) есептейміз.
2. Егер r=0 болса, онда b ізделетін Сан бар.
Егер r 0 болса,буды (а,B) (B, r) ауыстырамыз және алдымен қайталаймыз.
Қарапайым сандар генераторы
Мұнда өте үлкен қарапайым сандарды таңдау бағдарламасы бар. Оның әрекет
принципі келесі теоремаға негізделеді.
Теорема2. 1 n, S-тақ табиғи сандар болсын, N-1=S * R, және q санының
қарапайым бөлгішінің ұяшығы s және табиғи А:
.
Сонда р санының қарапайым бөлгіші р =1(mоd 2S) қанағаттандырады.
Салдары. Егер теорема шарттары орындалса және R≤4S+2, Онда N -
қарапайым Сан.
Иеміз келесі алгоритмі:
1.S - кейбір қарапайым санды және S≤R≤4S+2 аралығынан R - жұп санды
таңдаймыз.
2.N=RS+1 санын тексереміз: егер n жай болмаса, онда қарапайым санды
тапқанға дейін басқа R таңдаңыз. Осылайша салынған N S2, демек-екі есе үлкен
дәреже бар.
3.Қажет болған жағдайда бастапқы жай сан ретінде N аламыз және табылған
жай Сан жеткілікті үлкен болғанша алгоритмді қайталаймыз.
Бұл әдіс өте қарапайым және дербес компьютерде 1010 қарапайым сандар
алуға мүмкіндік береді.
Достарыңызбен бөлісу: | 
