Евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу туралы қазақша реферат

Кеңейтілген Евклид алгоритмі арқылы модуль бойынша кері элементті табу

Егер Эйлердің φ(n) функциясы белгісіз болса, модуль бойынша кері элементті табу үшін кеңейтілген Евклид алгоритмін қолдануға болады. Евклид алгоритмінің алгебрада ғана емес, жалпы математикада да маңызы зор: ол екі бүтін санның ең үлкен ортақ бөлгішін (ЕҮОБ) тиімді табуға мүмкіндік береді, ал оның кеңейтілген нұсқасы кері элементті есептеуге жол ашады.

Негізгі идея

Модуль бойынша кері элемент дегеніміз: егер ab ≡ 1 (mod n) болса, онда a және b сандары n модулі бойынша біріне-бірі кері деп аталады. Бұл жағдайда a ≡ b^-1 (mod n) немесе b ≡ a^-1 (mod n) деп жазамыз.

Евклид алгоритмі және ЕҮОБ табу

Оң бүтін r₀ > r₁ > 0 сандары берілсін. Олардың ЕҮОБ-ын табу үшін қалдықпен бөлу тізбегін құрамыз:

r₀ = q₁r₁ + r₂, 0 < r₂ < r₁

r₁ = q₂r₂ + r₃, 0 < r₃ < r₂

…

r_m-2 = q_m-1r_m-1 + r_m, 0 < r_m < r_m-1

r_m-1 = q_mr_m

Негізгі нәтиже: ЕҮОБ(r₀, r₁) = ЕҮОБ(r₁, r₂) = … = ЕҮОБ(r_m-1, r_m) = r_m. Демек, Евклид алгоритмін орындау нәтижесінде ЕҮОБ(r₀, r₁) = r_m табылады.

Кеңейтілген Евклид алгоритмі: кері элементке апаратын кеңейту

Алгоритмді кеңейту үшін рекурренттік тәсілмен t₀, t₁, …, t_m тізбегін анықтаймыз: t₀ = 0, t₁ = 1, ал j ≥ 2 үшін t_j = t_j-2 − q_j-1t_j-1.

Модуль бойынша теңдік (белгілеу)

Егер a және b сандары n-ге бөлгенде бірдей қалдық берсе, онда олар n модулі бойынша тең деп аталады: a ≡ b (mod n).

Лемма 1

Жоғарыда орындалған кеңейтілген Евклид алгоритмінде пайда болатын сандар әрбір 0 ≤ j ≤ m үшін: r_j ≡ t_jr₁ (mod r₀) қатынасын қанағаттандырады.

Дәлелдеудің қысқаша сұлбасы (индукция):

j = 0 және j = 1 үшін тұжырым бірден орындалады.
i ≥ 2 болсын және r_i-2 ≡ t_i-2r₁ (mod r₀), r_i-1 ≡ t_i-1r₁ (mod r₀) деп ұйғарайық.
Онда r_i = r_i-2 − q_i-1r_i-1, сондықтан r_i ≡ (t_i-2 − q_i-1t_i-1)r₁ (mod r₀) ≡ t_ir₁ (mod r₀).

Салдар 1 (кері элементтің бар болуы)

Егер ЕҮОБ(r₀, r₁) = 1 болса (яғни, r₀ мен r₁ өзара жай), онда t_m ≡ r₁^-1 (mod r₀). Басқаша айтқанда, кеңейтілген Евклид алгоритмі r₁-дің r₀ модулі бойынша кері элементін береді.

Векторлық жазылуы және есептеу қадамдары

Кеңейтілген Евклид алгоритмін есептеулерге ыңғайлы ету үшін векторлық белгілеу қолданылады. Берілген теріс емес бүтін a және b үшін (U1, U2, U3) векторы мына теңдікті қанағаттандырады: aU1 + bU2 = U3 = ЕҮОБ(a, b). Есептеу барысында қосымша (V1, V2, V3) және (t1, t2, t3) векторлары қолданылады.

Итерация кезінде сақталатын қатынастар

a·t1 + b·t2 = t3
a·U1 + b·U2 = U3
a·V1 + b·V2 = V3

Модуль бойынша кері элементті табу шарты

a санының n модулі бойынша кері санын табу үшін b = n деп аламыз және ЕҮОБ(a, n) = 1 шарты орындалуы керек. Егер aU1 + nU2 = 1 болса, онда a^-1 (mod n) ≡ U1 (mod n).

Алгоритм қадамдары

Бастапқы қою:

(U1, U2, U3) = (0, 1, n)

(V1, V2, V3) = (1, 0, a)
Егер U3 = 1 болса, алгоритм аяқталады.
q мәнін анықтаймыз: q = div (бөлгендегі бүтін бөлігі).
Қосалқы векторды есептейміз және жаңартамыз:

(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)

Төмендегі есептеу кестесі кеңейтілген Евклид алгоритмі арқылы 5 санының 23 модулі бойынша кері элементін табуды көрсетеді.

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

Қорытынды

Евклид алгоритмі екі бүтін санның ЕҮОБ-ын табуға қолданылады.
Кеңейтілген Евклид алгоритмі жолай u₁ және u₂ бүтін сандарын есептеп, a·u₁ + b·u₂ = ЕҮОБ(a, b) теңдігін береді.
Егер ЕҮОБ(a, n) = 1 болса, онда a^-1 (mod n) кері элементі бар және оны дәл осы алгоритммен тиімді табуға болады.

Осылайша, Евклид алгоритмін үлкен практикалық мәні бар әдіс ретінде қорытуға болады: ол тек ЕҮОБ-ты ғана есептемей, модульдік арифметикадағы маңызды есептердің бірі — кері элементті табуды да қамтамасыз етеді.