modular multiplication inverse of large numbers in c+++
Answers
I am trying to calculate the multiplicative inverse of a large number mod another large number. For example, I want to calculate the multiplicative inverse of 6003722857 mod 77695236973. I wrote some C++ code to do this. It works fine for small numbers like a = 1891 and n = 3797 but once I try very large numbers, the program doesn't work. There is no error. It looks like it is calculating something but then the program just ends.
Any advice would be appreciated. Thanks!
#include <iostream>
using namespace std;
int main ()
{
long long int a = 0, n = 0;
cout << "Enter a: ";
cin >> a;
cout << "Enter n: ";
cin >> n;
for (long long int c = 1; c < n; c++) {
long long int num = a*c - 1;
if (num%n == 0) {
cout << "The multiplicative inverse is " << c << "." << endl;
break;
}
}
return 0;
5
You're probably overflowing the variables. Try using a "bignum" library such as GMP. – Some programmer dude May 19 '14 at 19:21
How are you running the program? (and what are you compiling it with?) "just ends" seems like a surprising outcome. For me (using VS2013), it just hangs, as might be expected when crawling over such a huge search space. – Rook May 19 '14 at 19:21
If the program "just ends", could it be that c >= n? If that wasn't expected to happen, it may be as @JoachimPileborg suggests. – Scott Hunter May 19 '14 at 19:23
It works, but it is very slow. Is there no way to run the problem in multiple threads? Which input did you use which caused the problem? – Flovdis May 19 '14 at 19:25
Works so far for 56757656857555855678 as input! Define 'very large numbers' more clearly please! – πάντα ῥεῖ May 19 '14 at 19:25
show 4 more comments
2 Answers
active oldest votes
up vote
1
down vote
accepted
And here it is in super-fast c++:
#include <iostream>
#include <utility>
#include <exception>
#include <tuple>
using namespace std;
using temp_t = std::tuple<long long, long long>;
long long calcInverse(long long a, long long n)
{
long long t = 0, newt = 1;
long long r = n, newr = a;
while (newr != 0) {
auto quotient = r /newr;
tie(t, newt) = make_tuple(newt, t- quotient * newt);
tie(r, newr) = make_tuple(newr, r - quotient * newr);
}
if (r > 1)
throw runtime_error("a is not invertible");
if (t < 0)
t += n;
return t;
}
int main ()
{
long long int a = 6003722857 , n = 77695236973;
/*
cout << "Enter a: ";
cin >> a;
cout << "Enter n: ";
cin >> n;
*/
try {
auto inverse = calcInverse(a, n);
cout << "The multiplicative inverse is " << inverse << endl;
}
catch(exception& e) {
cout << e.what() << endl;
}
return 0;
}
HOPE THIS HELPS..................
PLS MARK IT AS BRAINLIEST!!!!