Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу туралы қазақша реферат
жүктеу/скачать 17,71 Kb.
|
а
- Бұл бет үшін навигация:
- Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу туралы қазақша реферат
|
Стандарттар ГОСТ 28147-89 Ресми аталуы: «Криптографиялық өрнектеу алгоритмі ГОСТ 28147-89». 1989 жылы КСРО –да қабылданды. Блокті шифр, Фейстел схемасы бойынша құрылған шифрлеудің 32 циклі. Ақпараттық блоктың ұзындығы – 64 битаКілттің ұзындығы– 256 битAES (Rijndael)2001 жылы АҚШ-та қабылданды.Итерациялық блокты шифр, «Квадрат»архитектурасы бар Кілттің ұзындығы: 128, 192 или 256 битБлоктың ұзындығы: 128, 192 или 256 бит Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу туралы қазақша реферат Егер Эйлер φ(n) функциясы белгiлi болмаса, кеңейтiлген Евклид алгоритмiн қолдануға болады. Евклид алгоритмнің алгебрада, тіпті жалпы математикада атқаратын ролі өте үлкен. Оң бүтін r0>r1>0 сандары берілсін. Олардың ең үлкен ортақ бөлгішін (ЕҮОБ) табу үшін төмендегі қалдықпен бөлу тізбегін іске асырамыз: r0 = q1r1 + r2, 0 r1 = q2r2 + r3, 0 rm-2 = qm-1rm-1 + rm, 0 rm-1 = qmrm. Енді негізгі нәтижені дәлелдеу қиын емес: ЕҮОБ(r0, r1) = ЕҮОБ(r1, r2) = … = ЕҮОБ(rm-1, rm) = rm яғни, Евклид алгоритмін орындау нәтижесінде берілген сандардың ең үлкен ортақ бөлгішін табамыз: ЕҮОБ(r0, r1) = rm Енді бұл алгоритмді былай кеңейтейік. Рекурренттік әдіспен төмендегідей t0, t1, …, tm сандар тізбегін анықтаймыз: t0 = 0, t1 = 1, және j≥2 үшін tj = tj-2 – qj-1tj-1 деп ұйғарамыз. Бұл тізбектің пайдасын келесі леммадан көреміз. Алдымен бір белгілеу енгізейік: егер а, b сандары n-ге бөлгенде бірдей қалдық берсе, онда а, b сандары n модулі бойынша тең дейміз және бұл қатынасты а ≡ b (mod n) деп жазып көрсетеміз. Лемма 1 Жоғарыда іске асырылған кеңейтілген Евклид алгоритмінде пайда болатын сандар әрбір 0≤j≤m үшін ri ≡ tjr1 (mod r0) қатынасын қанағаттандырады. Дәлелдеуі: j бойынша индукция қолданамыз. Біріншіден, бастапқы мәндер j = 0 және j = 1 үшін лемманың дұрыстығы айдан анық. Леммадағы қатынас j = i — 1 және j = i – 2 үшін дұрыс деп ұйғарып (мұнда, әрине 2 ≤ i), оны і үшін дәлелдейік. Сонымен, индукцияның ұйғарымы бойынша ri-2 ≡ ti-2r1 (mod r0) және ri-1 ≡ ti-1r1 (mod r0) болады. Ал енді ri –ді есептесек, алатынымыз: ri = ri-2 – qi-1ri-1 ≡ ti-2r1 – qi-1ti-1r1 (mod r0) ≡ (ti-2 – qi-1ti-1)r1 (mod r0) ≡ tir1 (mod r0). Лемма дәлелденді. Егер ab ≡ 1(mod n) болса, онда a,b сандары n модулі бойынша біріне-бірі кері дейміз және a ≡ b-1 (mod n) немесе b ≡ a-1 (mod n) деп жазамыз. Салдар 1 Егер ЕҮОБ(r0, r1) = 1 болса (бұл жағдайда r0, r1 сандары өзара жай деп аталады), онда tm ≡ r1-1 (mod r0) деп аламыз. Бұл алгоритм бойынша берілген теріс емес а, b бүтін сандары (U1, U2, U3) векторларын анықтайды, ол келесі теңдікті қанағаттандыру тиіс. aU1 + bU2 = U3 = EYOБ (a, b) Есептеу барысында қосымша (V1, V2, V3), (t1, t2, t3) векторлары қолданылады. Есептеу үрдісінде келесі қатынастар орындалып отырады. аt1+bt2 = t3 aU1 + bU2 = U3 aV1 + bV2 = V3 a-1 (mod n) а санының n бойынша кері саның тапқанда, Евклид алгоритмі келесі жағдайда орындалады: b = n, ЕҮОБ (a, n) = 1 тиіс және U3 = 1 егер aU1 + nU2 = ЕҮОБ (a, n) = 1, басқаша айтқанда а теріс шамасы: a-1 (mod n) ≡ U1 (mod n)-ге тең. Алгоритмнің негізгі қадамдары: 1) Бастапқы қойылым (U1, U2, U3) векторы анықталады; (U1, U2, U3) = (0, 1, n) (V1, V2, V3) = (1, 0, a) 2) U3 = 1 орындалса, алгоритмнің соңы; 3) q анықталады. q = div бөлгендегі бүтін бөлігі; 4) Қосалқы векторларды есептейді (t1, t2, t3). (t1, t2, t3) = (U1, U2, U3) — q(V1, V2, V3) (U1, U2, U3) = (V1, V2, V3) (V1, V2, V3) = (t1, t2, t3). Алгоритм аяқталды. Мысал.n = 23, a = 5 5-1 (mod 23)
Кесте 1 Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу a-1 (mod n) ≡ U1 (mod n) 5-1 (mod 23) ≡ -9 (mod 23) = 14 Тексеру: (5*14) mod 23 = 70 mod 23 = 1. Нәтижені қорытатын болсақ: Евклид алгоритмі бүтін сандардың ең үлкен ортақ бөлгішін табуға қолданылады, ал кеңейтілген Евклид алгоритмі модуль бойынша кері элеметті есептеп табуға (бар болса!) қолданылады Керi a-1 (mod n) шамасын кеңейтiлген Евкид алгоритiмiнiн көмегiмен табамыз. Евклид алгоритмiн үлкен практикалық мәнi бар әдiспен қорытуға болады. Бұл әдiсте ЕҮОБ(a, b) есептеуi кезiнде жолай u1 және u2 бүтiн сандарын есептеуге болады, бұл a* u1 + b* u2 = ЕҮОБ(a, b) Бұл кеңейтiлген Евклид алгоритмiнiнiң қорытуын тиiмдi болады, егер векторлық белгiлеулер қолданса. жүктеу/скачать 17,71 Kb. Достарыңызбен бөлісу:
|