5

ミラー・ラビンの素数性検定が確率論的であることは知っています。ただし、エラーの余地のないプログラミングタスクに使用したいと考えています。

long long入力数値が 64 ビット整数 (つまりC)の場合、非常に高い確率で正しいと仮定できますか?

4

5 に答える 5

1

GPU やその他の既知の結果を利用して徹底的にテストされた、GRH に依存しない64 ビット値の MR テストの効率的な決定論的バリアントがあります。

64 ビット値の素数性をテストする、私が作成した C プログラムの関連セクションをリストしました(n > 1)。累乗には gcc と clang の__int128拡張型を使用します。利用できない場合は、明示的なルーチンが必要です。多分他の人はこれが便利だと思うでしょう...

#include <inttypes.h>

/******************************************************************************/

static int sprp (uint64_t n, uint64_t a)
{
    uint64_t m = n - 1, r, y;
    unsigned int s = 1, j;

    /* assert(n > 2 && (n & 0x1) != 0); */

    while ((m & (UINT64_C(1) << s)) == 0) s++;
    r = m >> s; /* r, s s.t. 2^s * r = n - 1, r in odd. */

    if ((a %= n) == 0) /* else (0 < a < n) */
        return (1);

    {
        unsigned __int128 u = 1, w = a;

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

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

        if ((y = (uint64_t) u) == 1)
            return (1);
    }

    for (j = 1; j < s && y != m; j++)
    {
        unsigned __int128 u = y;
        u = (u * u) % n; /* (sqr-rdx) */

        if ((y = (uint64_t) u) <= 1) /* (n) is composite: */
            return (0);
    }

    return (y == m);
}

/******************************************************************************/

static int is_prime (uint64_t n)
{
    const uint32_t sprp32_base[] = /* (Jaeschke) */ {
        2, 7, 61, 0};

    const uint32_t sprp64_base[] = /* (Sinclair) */ {
        2, 325, 9375, 28178, 450775, 9780504, 1795265022, 0};

    const uint32_t *sprp_base;

    /* assert(n > 1); */

    if ((n & 0x1) == 0) /* even: */
        return (n == 2);

    sprp_base = (n <= UINT32_MAX) ? sprp32_base : sprp64_base;

    for (; *sprp_base != 0; sprp_base++)
        if (!sprp(n, *sprp_base)) return (0);

    return (1); /* prime. */
}

/******************************************************************************/

Web サイトの「備考」セクションに記載されているように、基数が候補の倍数である反復で値を渡すように、MR (sprp) テストがわずかに変更されていることに注意してください。

更新:これにはNiklas の回答よりもベース テストが少ないですが、ベース:{3, 5, 7, 11, 13, 17, 19, 23, 29}を超える候補を排除できる安価なテストを提供することに注意することが重要です: 29 * 29 = 841- 単純に GCD を使用します。

については、素数(n > 29 * 29)として偶数値を明確に排除できます。小さな素数の積:は、32 ビットの符号なし値にうまく収まります。AはMR検査よりかなり安い！結果が でない場合、小さい係数があります。(3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29} = 3234846615gcd(n, 3234846615) (1)(n) > 841

gcd(u64, u64)メルテンの (?) 定理は、この単純なテストがすべての奇数候補 (複合として) の ~ 68% を排除することを示唆しています。素数の検索に MR を使用している場合 (ランダムまたはインクリメンタル)、単なる「1 回限りの」テストではなく、これは確かに価値があります!

于 2016-03-06T09:45:46.677 に答える
-1

あなたのコンピュータは完璧ではありません。計算に不正確な結果をもたらすような方法で失敗する可能性は有限です。MR テストで偽の結果が出る確率が、他のコンピューターの故障の確率よりもはるかに低い場合は、問題ありません。MR テストを 64 回未満の反復で実行する理由はありません (2^128 分の 1 の確率でエラーが発生します)。ほとんどの例は最初の数回の反復で失敗するため、実際の素数のみを徹底的にテストします。2^256 分の 1 の確率でエラーが発生するように、128 回の反復を使用します。

于 2014-06-07T12:43:22.397 に答える