Computation Modular multiplicative inverse

a modular multiplicative inverse of modulo m can found using extended euclidean algorithm.

the euclidean algorithm determines greatest common divisor (gcd) of 2 integers, , m. if has multiplicative inverse modulo m, gcd must 1. last of several equations produced algorithm may solved gcd. then, using method called substitution , expression connecting original parameters , gcd can obtained. in other words, integers x , y can found satisfy bézout s identity,

a
x
+
m
y
=
gcd
(
a
,
m
)
=
1.


{\displaystyle ax+my=\gcd(a,m)=1.}

rewritten, is

a
x
−
1
=
(
−
y
)
m
,


{\displaystyle ax-1=(-y)m,}

that is,

a
x
≡
1


(
mod

m
)

,


{\displaystyle ax\equiv 1{\pmod {m}},}

so, modular multiplicative inverse of has been calculated. more efficient version of algorithm extended euclidean algorithm, which, using auxiliary equations, reduces 2 passes through algorithm (back substitution can thought of passing through algorithm in reverse) one.

in big o notation, algorithm runs in time o(log(m)), assuming |a| < m, , considered fast , more efficient alternative, exponentiation.

using euler s theorem

as alternative extended euclidean algorithm, euler s theorem may used compute modular inverses.

according euler s theorem, if coprime m, is, gcd(a, m) = 1, then

a

ϕ
(
m
)


≡
1


(
mod

m
)

,


{\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},}

where



ϕ


{\displaystyle \phi }

euler s totient function. follows fact belongs multiplicative group



(

z


/

m

z

)


{\displaystyle (\mathbb {z} /m\mathbb {z} )}

if , if coprime m. therefore, modular multiplicative inverse can found directly:

a

ϕ
(
m
)
−
1


≡

a

−
1




(
mod

m
)

.


{\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.}

in special case m prime,



ϕ
(
m
)
=
m
−
1


{\displaystyle \phi (m)=m-1}

, modular inverse given by

a

−
1


≡

a

m
−
2




(
mod

m
)

.


{\displaystyle a^{-1}\equiv a^{m-2}{\pmod {m}}.}

this method slower extended euclidean algorithm, used when implementation modular exponentiation available. disadvantages of method include:

the value



ϕ
(
m
)


{\displaystyle \phi (m)}

must known , efficient known computation requires m s factorization. factorization believed computationally hard problem. however, calculating



ϕ
(
m
)


{\displaystyle \phi (m)}

straightforward when prime factorization of m known.
the relative cost of exponentiation. though can implemented more efficiently using modular exponentiation, when large values of m involved efficiently computed montgomery reduction method. algorithm requires modular inverse mod m, calculated in first place. without montgomery method, standard binary exponentiation, requires division mod m @ every step, slow operation when m large.




^ thomas koshy. elementary number theory applications, 2nd edition. isbn 978-0-12-372487-8. p. 346.