Extended Euclidean algorithm 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.