Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

Modular Multiplicative Inverse

Introduction
Synopsis
Usage
References

The modular multiplicative inverse of a number a is that number x which satisfies ax = 1 mod p. A fast algorithm for computing modular multiplicative inverses based on the extended Euclidean algorithm exists and is provided by Boost.

#include <boost/integer/mod_inverse.hpp>

namespace boost { namespace integer {

template<class Z>
Z mod_inverse(Z a, Z m);

}}
int x = mod_inverse(2, 5);
// prints x = 3:
std::cout << "x = " << x << "\n";

int y = mod_inverse(2, 4);
if (y == 0)
{
    std::cout << "There is no inverse of 2 mod 4\n";
}

Multiplicative modular inverses exist if and only if a and m are coprime. If a and m share a common factor, then mod_inverse(a, m) returns zero.

Wagstaff, Samuel S., The Joy of Factoring, Vol. 68. American Mathematical Soc., 2013.


PrevUpHomeNext