| [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). |
| ] |