簡化模冪運算C++

我正在嘗試爲RSA加密系統編寫解密函數，似乎一切正常，對於非常很小的數字，但是有時輸出不正確（我認爲原因可能是是浮點錯誤還是某種堆棧溢出）。簡化模冪運算C++

引起我的問題的過程可以簡化爲（11^23）mod 187，但我將包括完整的代碼，以防有人想看到它。我知道答案應該是88，因爲這是Simon Singh博士的「The Code Book」附錄J中使用的例子（我也使用Wolfram Alpha進行了檢查）。但是，我得到了149的結果。但是，數字越小，它就與Wolfram Alpha一致。

我的想法是，我需要使用知識來簡化模冪運算是：

一個^ B = A^C * A^d [其中c + d = B]

然而，我如果這是這個問題，我仍然不能100％確定，這是我的第一次堆棧溢出嗎？（我仍然不是100％確定這意味着什麼）。在有人問我之前，不，這不是一種功課，如果這個問題看起來微不足道，我很抱歉。如果每個人都認爲這樣做太難了，我很樂意使用gmp.h，但如果我完全誠實，我寧願不願意。我的代碼在下面（前半部分是計算私鑰，我認爲這與我遇到的問題無關，但我已經包含了它以防萬一我錯了），我真的希望你們能幫忙，謝謝你非常提前。

#include <iostream> 
#include <math.h> 

using namespace std; 

unsigned int modinv(unsigned int u, unsigned int v) 
{ 
    unsigned int inv, u1, u3, v1, v3, t1, t3, q; 
    int iter; 

    u1 = 1; 
    u3 = u; 
    v1 = 0; 
    v3 = v; 

    iter = 1; 

    while (v3 != 0) 
    { 

     q = u3/v3; 
     t3 = u3 % v3; 
     t1 = u1 + q * v1; 

     u1 = v1; v1 = t1; u3 = v3; v3 = t3; 
     iter = -iter; 
    } 

    if (u3 != 1) 
     return 0; 
    if (iter < 0) 
     inv = v - u1; 
    else 
     inv = u1; 
    return inv; 
} 

int main() 
{ long unsigned int p = 17; 
long unsigned int q = 11; 
long unsigned int phi = (p-1)*(q-1); 
long unsigned int e = 7; 
long unsigned int c = 11; 
long unsigned int n = p*q; 
long unsigned int d = modinv (e,phi); 
    { 
     cout << fmod (pow (c, d), n); 
    } 
    return 0; 
}

來源

2014-02-26 Michael

也許11^n mod 187是一個壞例子，因爲11是主要因素之一（187 = 11 x 17）？因此對於n> = 1，對於11^n mod 187，只有16個值，按重複模式：11 121 22 55 44 110 88 33 176 66 165 132 143 77 99 154 || 11 121 ...。所以11^n mod 187 = 11 ^（1 +（（n-1）mod 16））mod 187. – rcgldr

我已經對它進行了排序:) pow函數使用的是浮點數而不是自然數，寫我自己的模塊冪運算出很好，謝謝 – Michael

11^23約爲2^80。只有達到2^53的整數可以完全表示爲雙浮點數。因此fmod（pow（c，d），n））返回一個近似值。這在密碼學中不適用。

ADDED您可以使用重複平方進行模冪運算。檢查Wikipedia上關於文章「冪的平方」

來源

2014-02-26 22:45:10 user515430

什麼將是一個合適的替代？ – Michael

實現您自己的模數求冪函數。這是相當直接的，比你的modinv需要更少的線。 – user515430

所以沒有辦法做到這一點，我將不得不寫我自己的？對不起，如果這看起來像一個愚蠢的問題。 – Michael

有關RSA這個wiki文章節應該有所幫助：

RSA decryption worked example

注意文章包含一個鏈接到中國剩餘算法，其中包含一個鏈接到歐幾里德算法：給定兩個素數p和q，找到兩個整數a和b，這樣ap + bq = 1，這也意味着（ap）mod q == 1和（bq）mod p == 1.什麼不明確是a或b將是負數，負值將用於剩餘算法的第一部分（本文聲明使用來自Euclid算法的值）。例如，如果a是負數，則（ap）mod q == 1，但（（a + q）p）mod q也== 1，所以a和a + q都可以被認爲是p以數學爲模q。

來源

2014-02-27 03:03:25 rcgldr

簡化模冪運算C++

回答

相關問題