1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
[section:mod_inverse Modular Multiplicative Inverse]
[section 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.
[endsect]
[section Synopsis]
#include <boost/integer/mod_inverse.hpp>
namespace boost { namespace integer {
template<class Z>
Z mod_inverse(Z a, Z m);
}}
[endsect]
[section 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.
[endsect]
[section References]
Wagstaff, Samuel S., ['The Joy of Factoring], Vol. 68. American Mathematical Soc., 2013.
[endsect]
[endsect]
[/
Copyright 2018 Nick Thompson.
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
https://www.boost.org/LICENSE_1_0.txt).
]
|
