Эйлер функциясы көмегімен кері шамаларды есептеу туралы қазақша реферат
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-ке тең.