1[section:mod_inverse Modular Multiplicative Inverse]
2
3[section Introduction]
4
5The modular multiplicative inverse of a number /a/ is that number /x/ which satisfies /ax/ = 1 mod /p/.
6A fast algorithm for computing modular multiplicative inverses based on the extended Euclidean algorithm exists and is provided by Boost.
7
8[endsect]
9
10[section Synopsis]
11
12    #include <boost/integer/mod_inverse.hpp>
13
14    namespace boost { namespace integer {
15
16    template<class Z>
17    Z mod_inverse(Z a, Z m);
18
19    }}
20
21[endsect]
22
23[section Usage]
24
25    int x = mod_inverse(2, 5);
26    // prints x = 3:
27    std::cout << "x = " << x << "\n";
28
29    int y = mod_inverse(2, 4);
30    if (y == 0)
31    {
32        std::cout << "There is no inverse of 2 mod 4\n";
33    }
34
35Multiplicative modular inverses exist if and only if /a/ and /m/ are coprime.
36If /a/ and /m/ share a common factor, then `mod_inverse(a, m)` returns zero.
37
38[endsect]
39
40[section References]
41Wagstaff, Samuel S., ['The Joy of Factoring], Vol. 68. American Mathematical Soc., 2013.
42
43[endsect]
44[endsect]
45[/
46Copyright 2018 Nick Thompson.
47Distributed under the Boost Software License, Version 1.0.
48(See accompanying file LICENSE_1_0.txt or copy at
49https://www.boost.org/LICENSE_1_0.txt).
50]
51