2

14 桁 (またはそれ以上) の数の素数チェックのための最速のプログラムが必要です。複数のサイトを検索しましたが、見つけたサイトがこれほど大きな数字で機能するかどうかはわかりません.

4

4 に答える 4

6

プライムテストに関する限り、14 桁の数字はそれほど大きくありません。数に特別な構造がある場合、より高速な特殊なテストが利用できる場合がありますが (たとえば、メルセンヌ数の場合)、一般に、その範囲の数に対する最速のテストは

  1. いくつかの小さな数で試行分割を開始します。多くのチェックを行う予定がある場合は、n最小の素数のリストを作成する価値があります。これにより、試行除算が 1 回のテストで素数のみで除算され、テスト除数 (2 を除く) や 3 の倍数 ( 3)で十分です。「小さい」が何を意味するかは解釈次第であり、カットオフとして 100 から 10000 の間の選択が合理的であるように思われ、多くの (少数の) 除算が依然として迅速に行われ、圧倒的多数の合成数が検出されます。

  2. 試行分割が数を合成 (または実際にカットオフの 2 乗よりも小さい場合は素数) として決定しなかった場合は、関心のある範囲に対して決定的であることが知られている高速確率的素数テストのいずれかを使用できます。で、通常の候補は

    • Baillie/Pomerance/Selfridge/Wagstaff 検定、基数 2 の強力な Fermat 検定、正方形であることの検定、および (強い) Lucas 検定が続きます。これには 2 64未満の誤検知がないため、14 ～ 18 桁の数字に対して決定的です。
    • 考慮された範囲で決定的であることが知られている塩基のコレクションに対する強力なフェルマー検定。Chris Caldwell の素数ページによると、「n < 341,550,071,728,321が 2、3、5、7、11、13、および 17-SPRP の場合、n は素数です」。

APR-CL、ECPP、AKS などの高速な決定論的汎用プライム テストは、やや遅く、実装がかなり困難です。それらは、14桁以上の数の純粋な試行除算をすでに打ち負かしているはずですが、偶然にも範囲が正しいことが知られている確率論的テストよりもはるかに遅くなります。

ただし、ユースケースによっては、連続した範囲の数値をふるいにかけるのが最善の方法でもあります (たとえば、 10 14 -10 9と 10 14の間の素数を見つけたい場合、ふるいは数億の高速個別プライム テスト)。

于 2013-06-05T10:11:07.433 に答える
5

Daniel Fischer が指摘しているように、14 桁の数値は、素数性のテストにはそれほど大きくありません。これにより、いくつかのオプションが提供されます。1 つ目は単純な試行分割です。

function isPrime(n)
    d := 2
    while d * d <= n
        if n % d == 0
            return Composite
        d := d + 1
    return Prime

10^14 の平方根は 10^7 なので、少し時間がかかります。プライム ホイールを使用すると、多少速くなります。

struct wheel(delta[0 .. len-1], len, cycle)

w := wheel([1,2,2,4,2,4,2,4,6,2,6], 11, 3)

function isPrime(n, w)
    d := 2; next := 0
    while d * d <= n
        if n % d == 0
            return Composite
        else
            d := d + w.delta[next]
            next := next + 1
            if next == w.len
                next := w.cycle
    return Prime

これにより、ナイーブ試行分割が 2 倍または 3 倍高速化されるはずです。これで、ニーズには十分かもしれません。

より良いオプションは、おそらく Miller-Rabin 疑似素数性テスターです。強力な疑似素数テストから始めます。

function isStrongPseudoprime(n, a)
    d := n - 1; s := 0
    while d is even
        d := d / 2; s := s + 1
    t := powerMod(a, d, n)
    if t == 1 return ProbablyPrime
    while s > 0
        if t == n - 1
            return ProbablyPrime
        t := (t * t) % n
        s := s - 1
    return DefinitelyComposite

関数が返す各aProbablyPrimeは、 nの素数性の証人です。

function isPrime(n)
    for a in [2,3,5,7,11,13,17]
        if isStrongPseudoprime(n, a) == DefinitelyComposite
            return DefinitelyComposite
    return ProbablyPrime

Fischer が指摘したように、 Gerhard Jaeschkeの論文によると、 n < 10^14 の場合、これは完全に信頼できます。より大きな数の素数性をテストする場合は、25 人の証人を無作為に選択します 。関数はb ^ e (mod m ) を返します。あなたの言語がその関数を提供していない場合は、次のように効率的に計算できます。powerMod(b,e,m)

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

このテストの背後にある数学に興味がある場合は、私のブログにあるエッセイ「素数によるプログラミング」をお勧めします。

于 2013-06-05T13:47:47.347 に答える