Эйлер функциясы көмегімен кері шамаларды есептеу туралы қазақша реферат

Эйлер функциясы көмегімен кері шамаларды есептеу туралы қазақша реферат

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-ке тең.