Modular Inverse Built-In, C++

Question

There is a very nice way to find a modular inverse (that is, such b that ab ≡ 1 (mod m) for given a and m) in python-3.8:

b = pow(a, -1, m)

pow is built-in in python-3.8. Is there something like this in c++?

Answer 1

Yes, the relatively standard library boost has function boost::integer::mod_inverse:

#include <boost/integer/mod_inverse.hpp>
#include <iostream>

using boost::integer::mod_inverse;

int main(void)
{
  int x = 3;
  int m = 5;

  int y = mod_inverse(x, m);

  std::cout << x << " ^-1 (mod " << m << ") = " << y << std::endl;;

  return 0;
}

Output:

3 ^-1 (mod 5) = 2

References:

• Source code for boost::integer::mod_inverse;
• Documentation for boost::integer::mod_inverse.

Please note that mod_inverse(x, m) returns 0 if a and m are not coprime, whereas python's pow(x, -1, m) raises ValueError: base is not invertible for the given modulus.

Answer 2

No there is no built-in function in C++ (to answer your question :) ).