1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 |
- [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
- http://www.boost.org/LICENSE_1_0.txt).
- ]
|