### A modular inverse algorithm of Christina Doran, Shen Lu and Barry R. Smith

The underlying algorithm was published in
*New algorithms for modular inversion and representation by binary quadratic forms arising from structure in the Euclidean algorithm*, Christina Doran, Shen Lu and Barry R. Smith.

If m and n are positive integers, perform the Euclidean algorithm with n^{2} and mn + 1.

Let r be the first remainder less than n. Then either

(a) m × r ≡ 1 (mod n), in which case gcd(m,n) = 1 and r is the multiplicative inverse of m modulo n, or

(b) m × r ≢ 1 (mod n) , in which case gcd(m,n) > 1.

This is a BCMath version of the BC program **inverse**.

*Last modified 4th June 2015*

Return to main page