Cで膨大な数を処理する方法

Question

私はRSA暗号化アルゴリズムをC言語で書いています。どこにでも置くことを計画していないので、主に暗号化の理解を広げることができます。

RSAが生成する膨大な数値はどうやって処理するのですか？ 103のような比較的小さな秘密鍵で復号化を行って、私はまだこのようなものを扱うの問題が発生した場合でも：

67^103のmod 143 =（×10^188 1.21816096336830017301951805581）のmod 143

そのサイズの番号を保存する最も良い方法は何ですか？標準ライブラリを使ってそれを行う方法はありますか？ 。

Answer 1

誤ったアプローチ。 67^103 mod 143は、最初に67^103を計算する必要はありません。

ループでmoduloを指数の1ビットずつ計算します。

uint32_t powmod(uint32_t base, uint32_t expo, uint32_t mod) { 

    // % mod need only for the cases expo==0, mod<=1 
    uint32_t y = 1u % mod; 

    while (expo) { 
    if (expo & 1u) { 
     y = ((uint64_t) base * y) % mod; 
    } 
    expo >>= 1u; 
    base = ((uint64_t) base * base) % mod; 
    } 

    return y; 
} 

int main(void) { 
    printf("%lu",(unsigned long) powmod(67, 103, 143)); 
} 

出力

89