Эйлер функциясы көмегімен кері шамаларды есептеу туралы қазақша реферат
Эйлер функциясы көмегімен кері шамаларды есептеу
Егер Эйлердің φ(n) функциясы белгілі болса, онда модуль бойынша кері шаманы (мультипликативтік кері элементті) табуға болады. Ол үшін дәрежеге тез шығару (жылдам дәрежелеу) алгоритмі қолданылады.
Негізгі формула
Егер gcd(a, n) = 1 (яғни a және n өзара жай) болса, онда:
a-1 (mod n) ≡ aφ(n) − 1 (mod n)
Ал егер a мен n өзара жай болмаса, онда a-1 (mod n) кері шамасы жоқ.
φ(n) мәнін табуға арналған жиі кездесетін жағдайлар
| Модуль n | φ(n) | Ескерту |
|---|---|---|
| n = p | φ(n) = p − 1 | p — жай сан |
| n = pr | φ(n) = pr−1(p − 1) | p — жай сан, r ≥ 1 |
| n = p · q | φ(n) = (p − 1)(q − 1) | p және q — әртүрлі жай сандар |
| n = n1 · n2, gcd(n1, n2) = 1 | φ(n) = φ(n1) · φ(n2) | Көбейтінді қасиеті (өзара жай көбейткіштер үшін) |
Мысал: 5 санының 7 модулі бойынша кері шамасын табу
Берілгені
n = 7
Берілгені
a = 5
Табу керек
x = a−1 (mod n)
7 — жай сан, сондықтан: φ(7) = 7 − 1 = 6. Формула бойынша: a−1 ≡ aφ(n)−1 (mod n), яғни 5−1 ≡ 55 (mod 7).
Есептейік:
55 mod 7 = 3125 mod 7
52 = 25 ≡ 4 (mod 7)
54 ≡ 42 = 16 ≡ 2 (mod 7)
55 ≡ 54·5 ≡ 2·5 = 10 ≡ 3 (mod 7)
Қорытынды: 5−1 (mod 7) = 3, өйткені 5·3 = 15 ≡ 1 (mod 7).