3

素数を生成するためのふるいを作成しました。私は、プログラミングを含む RSA に関する学校のプロジェクトを行っています。素数を RSA システムに使用しますが、これは私のエッセイのためなので、セキュリティはそれほど重要ではありません。ただし、大きな素数ははるかに挑戦的であり、私はそれが好きです。私が使用するコード：

def Zeef(a):
    import math
    upperBound = a
    upperBoundSquareRoot = int(math.sqrt(upperBound))
    isPrime = [1 for m in range (0,upperBound+1)]
    for m in range(2,upperBoundSquareRoot+1):
        if (isPrime[m]==1):
            for k in range(m*m,upperBound+1,m):
                isPrime[k] = 0;
    print("Priemgetallen : ")
    numberofPrimes = 0
    for m in range(2,upperBound+1):
        if (isPrime[m] ==1):
            print(m)
            numberofPrimes = numberofPrimes+1
    print("Aantal = " , numberofPrimes);
a=input("Alle priemgetallen tot: ")
aa=int(a)
Priemen = Zeef(aa)

素数を生成するためのより高速な方法があると確信していますが、今のところコードを改善することにあまり興味がありません。

この関数を実行すると、最大 7 桁の素数を生成するのに問題なく動作しますが、それ以上の数が必要な場合は非常に遅くなります。私のコンピュータ (8 GB RAM) は、十分なメモリがないというメッセージを表示します。別のツールである Processing でも同じアルゴリズムを使用しました。処理は非常に高速ですが、10 桁以上は認識しません。また、コンピューターが計算できる素数を生成しているときに、印刷が遅いことに気付きました。

インターネットで検索を始めたところ、プログラムをコンパイルすると進行が速くなることがわかりましたが、計算と印刷の部分が速くなるのか、解釈の部分だけが速くなるのかはわかりません。また、配列に関する numpy について何かを見つけましたが、これが私の機能を著しく高速化するかどうかはわかりません。

素数をより速く見つけるにはどうすればよいですか?

4

3 に答える 3

2

これは、numpy を使用した最適化されていないバージョンのエラトステネスのふるいです。Python (2.7) と Numpy (1.7) の 64 ビット バージョンを実行している私の 8GB ラップトップでは、最大 10^9 までの素因数を 1 分以内に計算します。

import numpy as np

def sieve(a):
    upper_bound = np.int(np.sqrt(a))
    is_prime = np.ones((a+1,), dtype=np.bool)
    for m in xrange(2, upper_bound+1):
        if is_prime[m]:
            is_prime[m*m::m] = False
    return np.where(is_prime)[0][2:]

>>> sieve(100)
array([ 2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
       61, 67, 71, 73, 79, 83, 89, 97], dtype=int64)

そして、ここに私のタイミングがあります：

%timeit sieve(10**9)
1 loops, best of 3: 33.4 s per loop

%timeit sieve(10**8)
1 loops, best of 3: 2.47 s per loop

%timeit sieve(10**7)
1 loops, best of 3: 207 ms per loop

%timeit sieve(10**6)
100 loops, best of 3: 7.47 ms per loop

%timeit sieve(10**5)
1000 loops, best of 3: 716 us per loop

ふるいからすべての偶数を削除することで約 2 倍の速度で実行できますが、それと世界中のすべてのメモリを使用しても、10^10 までのすべての素数を取得するのにまだ数分かかります。

于 2013-09-16T17:46:52.240 に答える
1

RSA アルゴリズムに必要な種類の大きな素数を生成する場合は、エラトステネスのふるいよりも優れたアルゴリズムが必要になります。Python 用の Miller-Rabin primality チェッカーの実装を次に示します。

def isPrime(n):
    def isSpsp(n, a):
        d, s = n - 1, 0
        while d % 2 == 0: d, s = d / 2, s + 1
        t = pow(a, d, n)
        if t == 1: return True
        while s > 0:
            if t == n - 1: return True
            t, s = (t * t) % n, s - 1
        return False
    ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
         43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    if n in ps: return True
    for p in ps:
        if not isSpsp(n, p): return False
    return True

素数を使ったプログラミングに興味がある場合は、私のブログでこのエッセイをお勧めします。RSA 半素数の生成に関するこのページを含め、私のブログの他のページもご覧になることをお勧めします。

于 2013-09-16T20:45:28.250 に答える
1

あなたは計算の複雑さの問題について話している。プロセッサーやコンパイラーがどんなに高速であっても、アルゴリズムを高速化することができなくなる特定の問題があります。たとえば、NP 完全問題を解こうとしている場合、値が小さい場合は簡単ですが、値が大きい場合は難しくなります。

したくない場合でも、コードを改善することをお勧めします。または、素数生成を独自に処理するライブラリを見つけます。ここに興味深いリンクがあります: http://rebrained.com/?p=458

これは、素数を生成するための非常に優れたコードのようです...しかし、大きな素数も生成しません (非常に高速な iMac で試しました)。約 100000 まで高速でした。ランダムに生成された多数の素数をテストする方法については、このSO の質問を参照することをお勧めします。

于 2013-09-16T16:39:10.963 に答える