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 a snapshot of the develop branch, built from commit 42f6ea1194.

Modular Multiplicative Inverse

Introduction
Synopsis
Usage
References

Introduction

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.

Synopsis

#include <boost/integer/mod_inverse.hpp>

namespace boost { namespace integer {

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

}}

Usage

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.

References

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