Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу туралы қазақша реферат
Егер Эйлер φ(n) функциясы белгiлi болмаса, кеңейтiлген Евклид алгоритмiн қолдануға болады.
Евклид алгоритмнің алгебрада, тіпті жалпы математикада атқаратын ролі өте үлкен. Оң бүтін r0>r1>0 сандары берілсін. Олардың ең үлкен ортақ бөлгішін (ЕҮОБ) табу үшін төмендегі қалдықпен бөлу тізбегін іске асырамыз:
r0 = q1r1 + r2, 0<r2<r1
r1 = q2r2 + r3, 0<r3<r2
rm-2 = qm-1rm-1 + rm, 0<rm<rm-1
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 Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу
|
q |
U1 |
U2 |
U3 |
V1 |
V2 |
V3 |
|
— |
0 |
1 |
23 |
1 |
0 |
5 |
|
4 |
1 |
0 |
5 |
-4 |
1 |
3 |
|
1 |
-4 |
1 |
3 |
5 |
-1 |
2 |
|
1 |
5 |
-1 |
2 |
-9 |
2 |
1 |
|
2 |
-9 |
2 |
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леулер қолданса.