c++ - 最小の非負残基: 多数

Question

モジュラー合同を解決できる C++ プログラムを構築しようとしています。

n^p = x (mod q ),

ここで、n は小さな数で、p と q は非常に大きな任意の素数です。これを何度も試みましたが、常にメモリ オーバーフローの問題が発生します。どんな助けでも大歓迎です。

Answer 1

b ^ e (mod m )の簡単なアルゴリズムがあります。

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
        b := (b * b) % m
        e := e // 2 # integer division
    return x

中間の数が膨大になるため、b ^ eを計算してから剰余演算を実行しないでください。必要な大きな数値を格納するのに適したデータ型を使用して、好みの言語に翻訳することはあなたに任せます。このアルゴリズムについては、ブログで説明しています。