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 n2 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.

Enter m:
Enter n (> 0):
Last modified 4th June 2015
Return to main page