問題タブ [prime-factoring]

私は Java で素因数分解プログラムに取り組んでおり、それらが繰り返されていても、数値のすべての素因数を表示します。そして、私はこれを持っています:

繰り返される要因を考慮する必要があります (8 に対して 2、2、2 など)。完全に再構築せずにどうすればそれを行うことができますか?

シンプルなふるいを作るのは簡単です：

しかし、N が非常に大きく、そのような配列をメモリに保持できない場合はどうでしょうか? セグメント化されたふるいのアプローチを調べましたが、sqrt(N) まで素数を見つける必要があるようですが、それがどのように機能するかわかりません。N が非常に大きい (たとえば 10^18) 場合はどうなるでしょうか。

大きな数の因数分解の複雑さを見つけようとしています。最良のアルゴリズムはどれですか、そして数の素因数を見つけることの複雑さはどれですか？数の長さがnであると仮定します。

これはプロジェクト Euler の問題 3 です。知らない人のために、600851475143 の最大の素因数を見つけなければなりません。以下のコードがあります。

しかし、100000000 のように、600851475143 より (かなり) 小さい値でプログラムをテストすると、プログラムに時間がかかります。ここでは明らかに間違ったアプローチをとっています (もちろん、プログラムは動作します。小さい数値で試してみました)。誰も網羅的でない方法を提案できますか?

このfactorコマンドは、指定された整数 NUMBER の素因数を出力します。

やってみたところ

そのような大きな数であっても、ミル内で結果が得られます。

どのアルゴリズムを使用していますか?

94 桁の素因数を求める必要があります。インターネットでこのリンクを見つけました。これは、初心者が仕事をするためのガイダンスであると思われます。Step2に合格できませんでした。

とにかく、私の問題は、Windows または CYGWIN で GGNFS を使用する方法がわからないことですか? 必要なファイルをダウンロードしましたが、コードの実行方法がわかりません。

GGNFS をHEREからダウンロードしました。ダウンロードしたファイルの詳細は次のとおりです。

タイプ------プロセッサ----バージョン----サイズ--------ファイル----------------------- - - - - - 日にち

32bit-------x86-----------SVN 413----4.0 MB---ggnfs-svn413-win32-p4.zip-----03/20/2011

あなたの助けをいただければ幸いです。

ありがとう、

JPanelがすべてセットアップされたJFrameGUIが機能しています。セットアップして機能している2つの異なるコードを組み合わせようとしています。最初のコードはJPanelのUpperCaseへのテキストコンバーターで、2番目のコードは素因数（素数ではない）コードです。私はJPanelに、ユーザーが入力した任意の数の素因数の出力を提供させようとしています。これが私が持っているものです...

JPanelコード

これが素因数コードです

一番下にある最後のPrimeFactorsコードは、私が自分で動作させようとしていたときから残っているものです。助けてくれてありがとう!!!

素因数分解の難しさに基づいていない公開鍵アルゴリズムを探しています。特に、素因数分解が、より優れたアルゴリズムとブルート フォーシングのための馬力の組み合わせを使用して、一部の国家セキュリティ装置で解決されているという噂があります。

数年前に、P <> NP の場合に簡単に解決できない、同じように難しい問題に基づく代替アルゴリズムについて読んだことを覚えています。

素因数分解に依存しないセキュリティと暗号化の最も有望な研究手段は何ですか?

プロジェクトオイラーの問題3で指定された番号600851475143の素因数を見つけようとしています （最高の素因数を要求しますが、すべてを見つけたいと思います）。ただし、このプログラムを実行しようとすると、結果が得られません。それは私のプログラムがそのような大きな数にかかる時間と関係がありますか、それとも数自体と関係がありますか？

また、この問題を解決するためのより効率的な方法は何ですか。また、問題を解決しているときに、これらのより洗練されたソリューションに向けてどのように舵を切ることができるかについてのヒントはありますか？

いつものように、ありがとう！

Project Euler の問題 3 は次のとおりです。

13195 の素因数は 5、7、13、29 です。

600851475143 の最大の素因数は?

私の解決策は永遠にかかります。私は正しい実装を得たと思います。ただし、大きな数でテストすると、結果を見ることができませんでした。それは永遠に実行されます。私のアルゴリズムに何か問題があるのだろうか：