1

ここに、310桁の10進整数を素数に分解できるソフトウェアがありますか？120桁の因数分解に使用できたmsieveがありましたが、310桁がmsieveの最大許容数である308桁を超えています。

PS：因数分解する数には2つの素数があり、p-1、p+1およびその他の簡単で高速な因数分解方法は失敗する可能性があります。

更新：GGNFSのみが機能するようで、因数分解を自動化するためのPythonスクリプトがいくつかあります。

4

1 に答える 1

1

半素数でない場合は、LenstraのECアルゴリズムを使用します。それ以外の場合は、PomeranceのNFSを使用してください。これらの「ボックス」の両方について、優れた紹介があります。私の賭けは、LenstraとPomeranceのホームページを閲覧することです。どちらも説明がとても上手です。または、Mark Herkommerによる「NumberTheory ： AProgrammersGuide」をチェックしてください。それはあなたが必要としているものであり、それ以上のものではなく、非常に明確です。

編集：あなたが従来のハードウェアを持っていると仮定すると、1000ビットのモジュラスは少しストレッチかもしれませんが。

編集：確かに、いくつかの追加のリンク：Herkommerの本のhttp://tinyurl.com/herkAmzon 。

Hendrik LenstraのホームページからのEC因数分解に関する1987年の論文：楕円曲線による整数の因数分解、Ann。数学の。126、649-673。。

広大なネットから：上記のアルゴリズムの非常に単純なPythonソースコード（私は校正していません）

カール・ポメランスのホームページとナンバーフィールドシーブに関する関連論文はこちら

ただし、ふるいの開発に関するこの物語、またはPomeranceのページからの2次バージョンに関するこの説明も役立つ場合があります。

GNFSの実装専用のこのサイトをチェックしてください。ただし、数ページに明確で単純なソースコードが含まれているHerkommerの本のコピーを見つけることを強くお勧めします。

編集：ElasticComputeクラウド全体でファクタリングを実行することも検討してください。このWiREDの記事によると、男が75ドルで一晩それをしていると聞きました

于 2011-12-22T18:55:55.690 に答える