Эйлер функциясы көмегімен кері шамаларды есептеу туралы қазақша реферат
Eгер Эйлер φ(n) функциясы белгiлi болса, онда дәрежеге тез шығару алгоритмiн қолдана отырып a-1 (mod n) ≡ aφ(n) – 1 (mod n)табуға болады.
Кесте 1 Эйлер функциясы көмегімен кері шамаларды есептеу
|
Модуль n |
Функция φ(n) |
|
n n2 nr |
n-1 r(n-1) nr-1(n-1) |
|
n = p*q |
(p-1)(q-1) |
Егер а және n өзара жай сандар болса, a-1 x(mod n) салыстырылуы бір ғана есептеуін қажет етеді. Егер а және n өзара жай сандар болмаса, онда бұл салыстыру есептеуді қажет етпейді.
Егер Эйлер функциясы белгілі болса, онда кері шаманы есептеуге болады:
а-1 (mod n) = aφ(n-1) (mod n)
Мысалдар:
- a-1 (mod n) –дi табу керек, егер Эйлер φ(n) функциясы белгiлi болса.
n = 7, ал a= 5 болсын. x = a-1 (mod n) = 5-1 (mod 7 )–нi табу керек.
n = 7 модулi – жай сан. Сондықтан Эйлер функциясы φ(n) = φ(7) = n-1 =6.
Керi шама 5-тен 7 – ге дейiнгі аралықты қамтиды.
a-1 (mod n) = aφ(n) – 1 (mod n) = 56-1 mod 7 = 55 mod 7 = (52 mod 7)(53 mod 7) mod 7 = (25 mod 7)(125 mod 7) mod 7 = (4*6) mod 7 = 24 mod 7 = 3.
Нәтижесі x = 5-1 (mod 7) = 3-ке тең.