1

私はPythonで暗号化スキームをシミュレートしています。私はそれに対する新しいユーザーです。

p = 512ビット数であり、その最大の素因数を計算する必要があります。私は2つのことを探しています。

  1. この大規模な素因数分解を処理するための最速のコード
  2. 512ビットの数値を入力として受け取り、それを処理できるコード。

私は他の言語でさまざまな実装を見てきました。私のコード全体はPythonであり、これが私が立ち往生している最後のポイントです。それで、Pythonに実装があるかどうか教えてください。

私はPythonの新規ユーザーなので、簡単に説明してください

英語が下手でごめんなさい。

編集（以下のOPの回答から取得）：

#!/usr/bin/env python
def highest_prime_factor(n):
   if isprime(n):
      return n
   for x in xrange(2,n ** 0.5 + 1):
      if not n % x:
         return highest_prime_factor(n/x)

def isprime(n):
   for x in xrange(2,n ** 0.5 + 1):
      if not n % x:
         return False
   return True

if  __name__ == "__main__":
   import time
   start = time.time()
   print highest_prime_factor(1238162376372637826)
   print time.time() - start

上記のコードは「1238162376372637826」に対して（少し遅れて）機能しますが、

10902610991329142436630551158108608965062811746392 57767545600484549911304430471090261099132914243663 05511581086089650628117463925776754560048454991130443047

Pythonを狂わせます。上記のように、すぐに計算してもらう方法はありますか？

4

4 に答える 4

3

Python ベースのソリューションについては、pyecm を参照してください。gmpyがインストールされているシステムでも、pyecm は次の要素を検出しました。

101、521、3121、9901、36479、300623、53397071018461、1900381976777332243781

因数分解されていない 98 桁のコンポジットがまだあります。

60252507174568243758911151187828438446814447653986842279796823262165159406500174226172705680274911

ECM を使用してこの残りのコンポジットを因数分解することは、実際的ではない場合があります。

編集：数時間後、残りの要因は

6060517860310398033985611921721

と

9941808367425935774306988776021629111399536914790551022447994642391

于 2010-03-09T06:36:46.977 に答える
2

これは、大きな数に対する自明なアプローチよりも適しているはずです (ただし、この種の数を計算すると、すべての純粋な Python 実装には時間がかかります): Pollard Rho 素因数分解.

于 2010-03-08T18:47:45.177 に答える
1

拡張機能をインストールできる場合は、gmpyが役立ちます。このSO の質問に対する私の回答、具体的def prime_factors(x)にはそこに表示されているコードの関数を参照してください。

純粋な Python (拡張が許可されていない場合) では、少し難しく、はるかに遅くなります。たとえば、コードを参照してください。

于 2010-03-08T18:29:01.410 に答える
-1 
('''==============================================================================='''
>        '''              CALCULATE  HIGHEST PRIME
> FACTOR                                  '''
>
> '''===============================================================================''')
>
> #!/usr/bin/env python
> def highest_prime_factor(n):
>    if isprime(n):
>       return n
>    for x in xrange(2,n ** 0.5 + 1):
>       if not n % x:
>          return highest_prime_factor(n/x)
> def isprime(n):
>    for x in xrange(2,n ** 0.5 + 1):
>       if not n % x:
>          return False
>    return True
> if  __name__ == "__main__":
>    import time
>    start = time.time()
>    print highest_prime_factor(1238162376372637826)
>    print time.time() - start

コードは番号「1238162376372637826」で少し遅れて動作しますが、（109026109913291424366305511581086089650628117463925776754560048454991130443047109026109913291424366305511581086089650628117463925776754560048454991130443047）に拡張するとPythonがおかしくなります。上記のような方法はありますか、すぐに計算してもらうことができます。

于 2010-03-08T19:24:36.863 に答える