Дәрежеге шығару алгоритмі туралы қазақша реферат
К биттi ұзындықты n модулiнiң қосу, алу немесе көбейту сияқты аралық нәтижелері 2к биттен ұзын болмайды. Сондықтан модулярлық арифметикада дәрежеге шығаруды өте үлкен аралық нәтижелердің генерациясынсыз орындауға болады.
n модулi бойынша а санының дәрежесiн есептеудi ax mod n kөбейту мен бөлудiң қатары ретiнде орындауға болады. Бұны тездету үшiн неше түрлi әдiстерi бар. Бұл операциялар дистрибутивтi болғандықтан, модуль бойынша келтiрудi әркез орындай отырып, көбейту қатары ретiнде дәрежеге шығаруды тездетiп орындау. Егер ұзын сандармен (200 бит және одан да көп) жұмыс жасаса, бұл ерекше белгiлi болады.
Мысалы, егер a8 mod n –дi есептеу керек болса, жетi рет қайта көбейту мен модуль бойынша үлкен санды бiреуге келтiруге (a*a*a*a*a*a*a) mod n примитивтi жақындау қолданып керегi жоқ.
Бұның орнына 3 кiшi көбейту мен 3 кiшi модуль бойынша келтiру орындалады:
((a2 mod n)2 mod n)2 mod n
Осы әдiспен a16 mod n = (((a2 mod n)2 mod n)2 mod n)2 mod n есептелiнедi.
Есептеу бiраз ғана қиынырақ: ax mod n (4), мұндағы x 2-дәрежелі болып табылмайды. x cанының екiлiк жазуы x санын 2-дәрежелердiң қосындысы ретiнде келтiрудi қолдайды:
x = 25(10) → 1 1 0 0 1(2), сондықтан 25 = 24 + 23 + 20 тең болады.
Онда a25 mod n = (a*a24) mod n = (a*a8*a16) mod n = a*((a2)2)2*(((a2)2)2)2 mod n = ((((a2*a)2)2)2*a) mod n деп аламыз.
Аралық нәтижелерде алты ғана көбейту амалы керек болады:
(((((((a2 mod n)*a) mod n)2 mod n)2 mod n)2 mod n)*a) mod n
Бұл әдiс 1,5хк операциясына дейiн есептеуде қиындықты жеңiлдетедi, мұндағы к – бит негiзiндегі сандар ұзындығы.
Көптеген шифрлеу алгоритмi n модулi бойынша дәрежеге шығаруға негiзделген болғандықтан, тез дәрежеге шығару алгоритмiн қолдану орынды.
S = aW mod n мағынасын есептеу керек болсын. W дәрежесін 2 санын дәрежеге үлестіру түрінде келтіреміз:
W = wg-12g-1 + wg-22g-2 + … + w222 + w121 + w0
мұндағы wi 0 немесе 1сандары.
S = aW mod n – ді келесі түрде келтірейік:
S = aw mod n = aWg-12 + Wg-22 + … + W22 + W12 + W0 mod n = (a2)Wg-12 + Wg-22 + … + W22 + W12*aw0 mod n = ((a2)2) Wg-12 + Wg-22 + … + W22*(a2)W1*aW0 mod n = ( …((a2)2 … )2)Wg-1* … *(a8)W3*(a4)W2*(a2)W1*aW0 mod n.
Мысалдар:
1) 437mod 26 = ((42)19 – 4) mod 26 = [(16 mod 26)19 — 4] mod 26 = (162)9*4 mod 26 — 4 = (256 mod 26)9*4 mod 26 — 4 = 229*4 mod 26 — 4= (222)4*22*4 mod 26 – 4 = (484 mod 26)4*22*4 mod 26 = (16)4*22*4 mod 26 = (162)2*22*4 mod 26 = 222*22*4 mod 26 = 16*22*4 mod 26 = 16*88 mod 26 = 16*10 mod 26 = 160 mod 26 = 4.
2) [(223 mod 11)39 + (411 mod 7)19] mod 11
a) (223 mod 11)39 = ((24)5*23 mod 11)39 = (55*23 mod 11)39 = ((52)2*5*23 mod 11)39 = (32*5*23 mod 11)39 = (45*23 mod 11)39 = 839
b) (411 mod 7)19 = ((42)5*4 mod 7)19 = (25*4 mod 7)19 = (23*22*4 mod 7)19 = (16 mod 7)19 = 219
c) 839 mod 11 + 219 mod 11 = (82)19*8 mod 11 + (24)4*23 mod 11 = (9)19*8 mod 11 + 54*23 mod 11 = (92)9*9*8 mod 11 + (52)2*23 mod 11 = 49*9*8 mod 11+32*23 mod 11 = (42)4*4*9*8 mod 11 + 32*23 mod 11 = (52)2*4*9*8 mod 11 + 6 = 32*4*9*8 mod 11 + 6 = 3*9*8 mod 11 + 6 = 5*8 mod 11 + 6 = 7+6 = 13
d) 13 mod 11 = 2.