Дәрежеге шығару алгоритмі туралы қазақша реферат
Модулярлық арифметикада дәрежеге шығару операциясын өте үлкен аралық нәтижелерді генерацияламай-ақ тиімді орындауға болады. Егер n модулі k бит ұзындықта берілсе, онда қосу, азайту және көбейту сияқты аралық нәтижелер әдетте 2k биттен аспайды. Сондықтан әр қадамда модуль бойынша келтіруді қолдану есептеуді жеңілдетеді.
Дәрежеге шығаруды жылдамдату идеясы
ax mod n мәнін есептеуді көбейтулер тізбегі ретінде қарастыруға болады. Бұл операциялар дистрибутивті болғандықтан, әр көбейтуден кейін mod n бойынша келтіріп отырсақ, аралық сандардың шамадан тыс үлкейіп кетуінен сақтанамыз. Ұзын сандармен (мысалы, 200 бит және одан жоғары) жұмыс істегенде бұл тәсілдің тиімділігі ерекше байқалады.
Мысал: a8 mod n
Примитивті тәсілмен (a·a·a·a·a·a·a) mod n түрінде есептеу үшін 7 рет көбейту керек. Оның орнына қайталап квадраттау әдісін қолданамыз:
Қадамдық жазылуы
a8 mod n = ((a2 mod n)2 mod n)2 mod n
Артықшылығы
Бар болғаны 3 көбейту және 3 рет mod n бойынша келтіру жеткілікті.
Осыған ұқсас түрде: a16 mod n = (((a2 mod n)2 mod n)2 mod n)2 mod n.
Дәреже 2-нің дәрежесі болмаған жағдай (екілік жіктеу)
Есептеу біршама күрделірек болатын жағдай — x саны 2-нің дәрежесі болмағанда. Мұнда x санының екілік жазуы ыңғайлы, өйткені ол дәрежені 2-нің дәрежелерінің қосындысы ретінде көрсетуге мүмкіндік береді.
Мысал: x = 25
Ондық жазуы
25(10)
Екілік жазуы
11001(2)
Жіктелуі
25 = 24 + 23 + 20
Онда: a25 mod n = (a · a24) mod n = (a · a8 · a16) mod n.
Қайталап квадраттау арқылы бір ықшам жазылуы: a25 mod n = ((((a2 · a)2)2)2 · a) mod n.
Көбейтулер саны (аралықта)
Бұл тәсілде аралық нәтижелер үшін шамамен 6 көбейту жеткілікті: (((((((a2 mod n)·a) mod n)2 mod n)2 mod n)2 mod n)·a) mod n.
Жалпы алғанда, бұл әдіс есептеу күрделілігін шамамен 1,5·k операция деңгейіне дейін төмендетеді, мұндағы k — бит арқылы өлшенетін сан ұзындығы.
Жылдам дәрежеге шығарудың (square-and-multiply) жалпы схемасы
Көптеген шифрлеу алгоритмдері n модулі бойынша дәрежеге шығару операциясына сүйенетіндіктен, жылдам дәрежеге шығару алгоритмін қолдану өте орынды. Есептелсін: S = aW mod n.
W дәрежесін екілік түрде жазу
W санын екілік разрядтар арқылы:
W = wg−1·2g−1 + wg−2·2g−2 + … + w2·22 + w1·21 + w0, мұндағы wi ∈ {0, 1}.
Сонда көбейту мен квадраттауды кезектестіріп, әр қадамда mod n бойынша келтіріп отырамыз:
S = (…((a2)2 … )2)wg−1 · … · (a8)w3 · (a4)w2 · (a2)w1 · aw0 (mod n)
Есептер
Мысал 1: 437 mod 26
Төменде бастапқы есептеудің мазмұны сақталып, жазылуы ықшамдалды және тыныс белгілері түзетілді.
437 mod 26 = ((42)19 · 4−1) mod 26 = (1619 · 4) mod 26 − 4 = … = 160 mod 26 = 4
Қорытынды: 437 mod 26 = 4.
Мысал 2: [(223 mod 11)39 + (411 mod 7)19] mod 11
a) (223 mod 11)39
(223 mod 11)39 = … = 839
b) (411 mod 7)19
(411 mod 7)19 = … = 219
c) Қосындыны mod 11 бойынша есептеу
839 mod 11 + 219 mod 11 = … = 13
d) Соңғы қадам
13 mod 11 = 2
Қорытынды: есеп нәтижесі 2.
Негізгі тұжырым
Дәрежеге шығаруды жылдамдатудың өзегі — қайталап квадраттау және екілік жіктеу. Әр қадамда mod n бойынша келтіру аралық нәтижелерді шағын ұстап, есептеуді айтарлықтай жылдамдатады.