指定された最後の数字で大きな素数を生成する

Question

512ビット（155桁の数字）の素数をどのように生成でき、最後の5桁の数字が指定/固定されているのだろうか？

仕様書なしで単純な素数を生成する原則はかなり理解できますが、私の場合はさらに進んでいます。

少なくとも、どこから始めたらよいでしょうか？

JavaまたはC＃が適しています。

ありがとうございます！

Answer 1

私は唯一の方法はもちろん

while (!IsPrime(number)) 
    number += 100000; 

このようなもので、その後ちょうど強引number = randomnumber * 100000 + 28071を行うことによって、その背後に28071を追加し、その後、最初の150桁の乱数を生成することであろうと思います

Answer 2

数字を生成してチェックしてみましたか？私はそれが容認できるほど速くなると期待します。プライム密度は数値の対数としてしか減少しないので、素数を打つまで数百の数値を試してみることを期待しています。 ln(2^512) = 354したがって350の約1つの数字がプライムになります。

大まかに言えば、素数定理は、乱数の近くいくつかの大規模な数Nが選択された場合、それが素数であることの可能性は、LN（N）は、自然を示し、約1/LN（N）であると述べています例えば、N = 10,000付近では、9つの数字のうちの約1つが素数であり、N = 1,000,000,000の近くでは、21の数字のうち1つのみが素数である。言い換えれば、Nに近い素数との間の平均間隔はおおよそのln（N）である

（ http://en.wikipedia.org/wiki/Prime_number_theoremから）

あなただけの数が最終的な数字のために存在世話をする必要があります。しかし、私は、最後の数字が2または5で割り切れないことをチェックするのと同じくらい簡単だと思います（つまり1,3,7,9）。

this performance dataによると、あなたは、毎秒512ビットのデータに約2000 ModPow操作を行うことができ、かつシンプルなプライム・テストは1回のModPow操作で2^(p-1) mod p=1をチェックしているので、あなたは、毎秒あなたの特性をいくつかの素数を生成することができるはずです。

BigInteger FindPrimeCandidate(int lastDigits) 
{ 
    BigInteger i=Random512BitInt; 
    int remainder = i % 100000; 
    int increment = lastDigits-remainder; 
    i += increment; 
    BigInteger test = BigInteger.ModPow(2, i - 1, i); 
    if(test == 1) 
     return i; 
    else 
     return null; 
} 

を、その関数の結果に、より広範プライムのチェックを行います。

だから、（擬似コード）行うことができます。

Answer 3

standard methods for generating large primesの1つに余分な制約を加えることで、最後の5桁の10進数が正しくなければなりません。純粋に、これを余分なテストとして追加することはできますが、適切な素数を見つける時間が10^5増加します。

あまり知られていない：ランダムな512ビット数を生成し、十進数表現が必要なシーケンスで終わるように十分な下位ビットを設定します。その後、通常の素数検査を続行します。

Answer 4

brute-forceを考えてみましょう。最後のテーブルの最後のエントリを考える

• http://plus.maths.org/content/prime-number-lottery

があるが〜2.79 * 10^14個の素数少ないし、10：「素数くじ」と呼ばれるこの非常に興味深いテキストを見てみましょう^ 16。したがって、およそ35番目の数字がその範囲内のプライムです。

EDIT：CodeInChaosのコメントを参照してください。ちょうど5桁の数字が固定された数千の数字を歩いていると、すばやく見つけることができます。

Answer 5

@Doggotが言ったように、28071で終わる150桁の数字から始まり、100000 ... 0028071を意味するので、毎回100000を追加します。 here、それはいくつかのカスタマイズが必要です。戻り値がtrueの場合は、正確にチェックします。

Answer 6

特殊な条件を満たす数字だけを含むふるいを使用して、小さな素数で割り切れる数を除外することができます。

小さな素数pについては、ふるいに100000番目の数字だけが存在することを考慮して正しい出発点とステップを見つける必要があります。

ふるいに残っている数字については、BigInteger.isProbablePrime()を使用して十分な確率で素数であるかどうかを確認できます。

Answer 7

私はhttp://www.merriampark.com/bigsqrt.htmからBigSquareRootクラスの助けを借りてBigDecimal 1にint世界からブルートフォースアルゴリズムを書き直しました。 （1から1000までは正確に168の素数であると言われています）

あなたの範囲は、です。 10 -1>、あなたのコンピュータを動作させることができますし、あなたが引退したときに、あなたは結果を持っているかもしれません...それは遅いです！

しかし、このスレッドの他の回答と組み合わせて、何とかこの便利な点の一部を見つけることができます。

 

package edu.eli.test.primes; 

import java.math.BigDecimal; 

public class PrimeNumbersGenerator { 

    public static void main(String[] args) { 
// BigDecimal lowerLimit = BigDecimal.valueOf(10).pow(154); /* 155 digits */ 
// BigDecimal upperLimit = BigDecimal.valueOf(10).pow(155).subtract(BigDecimal.ONE); 

    BigDecimal lowerLimit = BigDecimal.ONE; 
    BigDecimal upperLimit = new BigDecimal("1000"); 

    BigDecimal prime = lowerLimit; 
    int i = 1; 

    /* http://www.merriampark.com/bigsqrt.htm */ 
    BigSquareRoot bsr = new BigSquareRoot(); 
    upperLimit = upperLimit.add(BigDecimal.ONE); 
    while (prime.compareTo(upperLimit) == -1) { 

     bsr.setScale(0); 
     BigDecimal roundedSqrt = bsr.get(prime); 

     boolean isPrimeNumber = false; 
     BigDecimal upper = roundedSqrt; 
     while (upper.compareTo(BigDecimal.ONE) == 1) { 

     BigDecimal div = prime.remainder(upper); 
     if ((prime.compareTo(upper) != 0) && (div.compareTo(BigDecimal.ZERO) == 0)) { 
      isPrimeNumber = false; 
      break; 
     } else if (!isPrimeNumber) { 
      isPrimeNumber = true; 
     } 

     upper = upper.subtract(BigDecimal.ONE); 
     } 

     if (isPrimeNumber) { 
     System.out.println("\n" + i + " -> " + prime + " is a prime!"); 
     i++; 
     } else { 
     System.out.print("."); 
     } 
     prime = prime.add(BigDecimal.ONE); 
    } 
    } 

} 
 

Answer 8

ABCDEは、あなたが検討しているベース10の5桁の数字にします。 Dirichlet's theorem on arithmetic progressionsに基づいて、ABCDEと100000が共起する場合、100000 * k + ABCDEの形の無限に多くの素数が存在します。素数を探しているので、2と5のどちらもABCDEを分けていないので、ABCDEと100000は共起しています。したがって、無限にあなたが考えているフォームの多くの素数があります。