使用C++計算大數的乘法倒數

-1

我想要計算大數mod的乘法倒數另一個大數。例如，我想計算6003722857 mod 77695236973的乘法逆。我編寫了一些C++代碼來執行此操作。它適用於像a = 1891和n = 3797這樣的小數字，但是一旦我嘗試了非常大的數字，該程序就無法工作。沒有錯誤。看起來它正在計算一些東西，但程序剛剛結束。使用C++計算大數的乘法倒數

任何意見，將不勝感激。謝謝！

#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; 
}

來源

2014-05-19 A. Wong

你可能溢出變量。嘗試使用諸如[GMP]之類的「bignum」庫（https://gmplib.org/）。 –

你如何運行程序？（並且你在編譯什麼？）「僅僅結束」似乎是一個令人驚訝的結果。對我來說（使用VS2013），它會掛起，正如在爬過如此巨大的搜索空間時所預期的那樣。 – Rook

如果程序「剛剛結束」，是否可能是c> = n？如果預計不會發生這種情況，可能就像@JoachimPileborg所建議的那樣。 –

這裏，它是在超快速的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; 
}

來源

2014-05-19 19:48:55

只是意識到temp_t的定義是不必要的。 –

謝謝你。我確實有我自己的擴展歐幾里德算法，儘管不像你的那麼幹淨。 –

最差情況下的一組數字是兩個最大的斐波那契數字：<2^63 a = 4660046610375530309，n = 7540113804746346429，這將需要90個循環。在這種情況下，（1/a mod n）== a。最大的素數<2^63是2^63-25 = 9223372036854775783，對於每個數字1到9223372036854775782將會有一個反數。 – rcgldr

您可以使用擴展歐幾里德算法來做到這一點：

Wiki - extended Euclidean algorithm - modular integers

來源

2014-05-19 19:38:52 rcgldr

使用C++計算大數的乘法倒數

回答

相關問題