7

私は暗号化の演習に取り組んでおり、(2 n -1)mod p を計算しようとしています。ここで、p は素数です。

これを行うための最良のアプローチは何ですか？私はCで作業しているので、nが大きいと2 n -1が大きくなりすぎて保持できません

方程式 (a*b)modp=(a(bmodp))modp に出くわしましたが、2 n -1 が素数である可能性があるため (または因数分解の方法がわからないため)、これがこの場合に当てはまるかどうかはわかりませんこれ）

大変助かります。

4

7 に答える 7

1

nコメントで、とpは 9 桁か 10 桁か何かであると述べています。それらを 32 ビット ( ) の値に制限すると、単純な (2 進数の) べき乗剰余でunsigned long見つけることができます。2^n mod p

unsigned long long u = 1, w = 2;

while (n != 0)
{
    if ((n & 0x1) != 0)
        u = (u * w) % p; /* (mul-rdx) */

    if ((n >>= 1) != 0)
        w = (w * w) % p; /* (sqr-rdx) */
}

r = (unsigned long) u;

そして、以来(2^n - 1) mod p = r - 1 mod p：

r = (r == 0) ? (p - 1) : (r - 1);

If 2^n mod p = 0- これは if が素数の場合には実際には発生しませんがp > 2、一般的なケース - then を検討することもでき(2^n - 1) mod p = -1 mod pます。

「共通剰余」または「剰余」(mod p)は にあるため、この範囲になるように[0, p - 1]の倍数を追加します。p

2^n mod pそれ以外の場合、 wasの結果はで[1, p - 1]あり、減算1はすでにこの範囲内になります。おそらく次のように表現したほうがよいでしょう。

if (r == 0)
    r = p - 1; /* -1 mod p */
else
    r = r - 1;
于 2013-11-04T09:33:49.113 に答える
0

2^n - 1 mod p を計算するには、(a^{p-1} = 1 mod p であるため) n から (p - 1) の任意の倍数を最初に削除した後、2 乗して累乗を使用できます。擬似コード:

n = n % (p - 1)
result = 1
pow = 2
while n {
    if n % 2 {
        result = (result * pow) % p
    }
    pow = (pow * pow) % p
    n /= 2
}
result = (result + p - 1) % p
于 2013-11-04T08:02:18.630 に答える
-1

最後にいつでも 1 を引くことができるため、最初に 2 n mod pに注目します。

2 のべき乗を考えてみましょう。これは、2 を繰り返し乗算することによって生成される一連の数値です。

モジュロ演算を考えてみましょう。数値が基数 p で書かれている場合は、最後の桁を取得しているだけです。上位桁は捨てることができます。

したがって、シーケンスのある時点で、2 桁の数字 (p の場所に 1) が表示されます。実際には、最初の数字を取り除く (p を引く) だけです。

概念的にここで停止すると、ブルート フォース アプローチは次のようになります。

uint64_t exp2modp( uint64_t n, uint64_t p ) {
    uint64_t ret = 1;
    uint64_t limit = p / 2;
    n %= p; // Apply Fermat's Little Theorem.

    while ( n -- ) {
        if ( ret >= limit ) {
            ret *= 2;
            ret -= p;
        } else {
            ret *= 2;
        }
    }
    return ret;
}

残念なことに、これは大きな n と p に対しては永遠にかかります。

オーバーフローせずに (p-1)^2 を計算できる乗算機能がある場合は、各二乗演算の後にモジュロを使用して二乗を繰り返し使用する類似のアルゴリズムを使用し、一連の二乗残差の積を再度取得できます。各乗算の後にモジュロを使用します。

于 2013-11-04T08:07:12.747 に答える
-2

ステップ 1. x= 1 を n 回シフトしてから 1 を引く

ステップ 2.result = x と p の論理演算

于 2013-11-04T07:45:46.557 に答える