0

演習として書いている RSA 実装の素数性テストを実装しようとしています。私は主に Rabin-Miller を使用していますが、1,000 未満のすべての素数のリストを定式化するエラトステネスのふるいを持っており、候補者がそのうちの 1 つを素因数として持っているかどうかを判断するための簡単なテストに使用します。

関連する機能は次のとおりです。

def comp_test(to_test, primeList):
    for i in primeList:
        if (to_test / float(i)) % 1 == 0:
            return False
    return True

ここで、primeList は Sieve によって生成された素数のリストです。これは 2^55 程度の to_test 値までは完全に機能しますが、それを超えると、

(to_test / float(i)) % 1

このステートメントは、Rabin-Miller が素数であると判断した to_test を渡した場合でも、常に 0.0 と評価されます。これが何であるかわかりません。Python が非常に大きな数をどのように処理するかについては明確ではありませんが、私の知る限り、2^55 はオーバーフロー ボーダーのようなものではないようです。Sieve を使用すると、関数が大幅に高速になり、2048 ビットの実装のキーを生成するにはしばらく時間がかかるため、これは演習ですが、Sieve が機能するかどうかを確認したいと思います。

前もって感謝します。

4

2 に答える 2

2

Python は、浮動小数点数 (小数点以下約 16 桁) に対して 53 ビットの精度しか処理しないため、大きな浮動小数点数を使用するとうまく機能しません。

代わりに剰余演算子を使用します。

>>> (2**80 / float(3)) % 1  # Doesn't work
    0.0
>>> 2**80 % 3  # Works
    1L
>>> 2**80 % 2  # Works
    0L

また、除算よりもかなり高速です。

>>> %timeit (2**40 / float(2)) == 0
1000000 loops, best of 3: 224 ns per loop
>>> %timeit 2**40 % 2 == 0        
10000000 loops, best of 3: 53.5 ns per loop

iが の因数である場合n、n % i == 0(は を法とするn合同です)。0i

于 2013-04-24T02:12:03.320 に答える
0

大量のニーズには GMP を使用することをお勧めします。

以下は、私が過去に Python で行ったプライム関連のプロジェクトの一部です。

http://stromberg.dnsalias.org/svn/primes-below
http://stromberg.dnsalias.org/svn/big-prime
http://stromberg.dnsalias.org/svn/huge-prime
http://stromberg.dnsalias.org/svn/sieve
于 2013-04-24T03:06:19.690 に答える