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++?

does this help you? stackoverflow.com/questions/53821181/… — Coder
– Coder, Commented Jan 10, 2021 at 12:29
Does this answer your question? What can I do on c++ to do an inverse of a number? — Coder
– Coder, Commented Jan 10, 2021 at 12:29
see also this: Modular Exponentiation for high numbers in C++ — bolov
– bolov, Commented Jan 10, 2021 at 12:30
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
– bolov, Commented Jan 10, 2021 at 12:31
@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
– Zhiltsoff Igor, Commented Jan 10, 2021 at 12:36

Coder · Accepted Answer · 2021-01-10 12:59:27Z

1

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

answered Jan 10, 2021 at 12:59

Coder

1,2641 gold badge15 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Stef · Accepted Answer · 2023-01-17 15:08:18Z

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.

Collectives™ on Stack Overflow

Modular Inverse Built-In, C++

2 Answers 2

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Linked

Related