3

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 :

b = pow(a, -1, m)

pow is built-in in . Is there something like this in ?

Zhiltsoff Igor
  • 1,812
  • 8
  • 24
  • 1
    does this help you? https://stackoverflow.com/questions/53821181/what-can-i-do-on-c-to-do-an-inverse-of-a-number – Coder Jan 10 '21 at 12:29
  • 1
    Does this answer your question? [What can I do on c++ to do an inverse of a number?](https://stackoverflow.com/questions/53821181/what-can-i-do-on-c-to-do-an-inverse-of-a-number) – Coder Jan 10 '21 at 12:29
  • 1
    see also this: [Modular Exponentiation for high numbers in C++](https://stackoverflow.com/questions/2207006/modular-exponentiation-for-high-numbers-in-c) – bolov Jan 10 '21 at 12:30
  • 1
    and to answer your question: no, afaik there is no such function in the standard library (ofc there is `std::pow` but it takes only 2 arguments, doesn't do modulo) – bolov Jan 10 '21 at 12:31
  • 1
    @JohnD, thank you, those posts help me, yet they do not answer my question - I stressed the **built-in** nature in my question. – Zhiltsoff Igor Jan 10 '21 at 12:36
  • 1
    @bolov, well, I guess, your **No** answers my question :). Alas. Yet, thank you. – Zhiltsoff Igor Jan 10 '21 at 12:37
  • 1
    ok ill resolve this then – Coder Jan 10 '21 at 12:59

2 Answers2

1

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

Coder
  • 1,175
  • 1
  • 12
  • 32
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:

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.

Stef
  • 13,242
  • 2
  • 17
  • 28