3

ax = 1 mod pp素数で合同を解くアルゴリズムを考えていました。フェルマーの定理を使おうと思っていました。それを知ってから

a ^ (p-1) = 1 mod p

そしてそれ

a ^ (p-1) = a * (a ^ (p-2))

それa ^ (p-2) mod pが解決策だということです。残念ながら、この解法は数学的には正しいものの、コンピューターには適していません。大きな素数を計算する必要があるためa ^ (p-2)、通常は計算できません。

コンピュータ サイエンスに適したアルゴリズムはどれですか?

4

3 に答える 3

11

大きな素数のa ^ (p-2)場合、通常は計算できないことをしなければならないからです。

べき乗剰余が必要なため、IVlad で言及されている 2 乗によるべき乗 では、最大でサイズの数の剰余乗算のみが必要です。中間結果は によって制限されるため、大きな素数では計算できませんが、通常は制限されます。その方法は簡単に実装できます。Θ(log p)p-1p^2a^(p-2)(a ^ (p-2)) % p

unsigned long long invert_mod(unsigned long long a, unsigned long long p) {
    unsigned long long ex = p-2, result = 1;
    while (ex > 0) {
        if (ex % 2 == 1) {
            result = (result*a) % p;
        }
        a = (a*a) % p;
        ex /= 2;
    }
    return result;
}

しかし、いくつかの欠点があります。使用されている型で表現可能でなければなりません (任意精度の整数が使用されている場合は [ huge(p-1)^2を除いて] 問題ではありません)。そうしないと、オーバーフローのために無効な結果が得られ、少なくとも剰余乗算が常に使用されます。 plog (p-2)/log 2

user448810 で提案されている拡張ユークリッド アルゴリズム、または同等の連分数法は、 より大きい中間値を生成することはありませpんp。さらに、素数だけでなく、任意の 2 つの互いに素な数についても剰余逆数を計算します。

unsigned long long invert_mod(unsigned long long a, unsigned long long p) {
    unsigned long long new = 1, old = 0, q = p, r, h;
    int pos = 0;
    while (a > 0) {
        r = q%a;
        q = q/a;
        h = q*new + old;
        old = new;
        new = h;
        q = a;
        a = r;
        pos = !pos;
    }
    return pos ? old : (p - old);
}

コードは少し長くなりますが、最適化コンパイラは反復ごとに 1 つの除算のみを使用して短いループにコンパイルする必要があります。

于 2012-12-30T20:10:18.177 に答える