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

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

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)

Мысалдар:

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