問題タブ [prime-factoring]

数の最大の素因数を計算するための最良のアプローチは何ですか？

最も効率的なのは次のことだと思います。

1. きれいに分割する最小の素数を見つける
2. 除算の結果が素数であるかどうかを確認します
3. そうでない場合は、次に低いものを見つけます
4. 2に進みます。

この仮定は、小さな素因数を計算する方が簡単であることに基づいています。これは正しいですか？他にどのようなアプローチを検討する必要がありますか？

編集：結果が他の2つの素数の積である場合、ステップ2は失敗するため、2つ以上の素因数が作用している場合、私のアプローチは無駄であることに気付きました。したがって、再帰的アルゴリズムが必要です。

もう一度編集します。最後に見つかった素数が最大である必要があるため、これが引き続き機能することに気付きました。したがって、ステップ2の非素数の結果をさらにテストすると、素数が小さくなります。

3000億以上の素因数を調べないといけない。それらのリストに追加する機能があります...非常にゆっくりと！現在、約1時間実行されており、静止するにはかなりの距離があると思います。私はそれを完全に間違っていますか、それとも期待されていますか?

編集：番号600851475143の最大の素因数を見つけようとしています.

編集：結果：

MLでは、数の素数の約数を取得したいと思います。どうすればこれができますか、私は初心者です。

非常に高速な素因数分解アルゴリズムがいくつかあるようです (理想的に見えるのは二次ふるいです)。ただし、独自の (おそらく貧弱な) 実装を作成するのではなく、簡単にするために既製のライブラリを使用したいと考えています。

最大 15 桁の整数を効率的に因数分解できる必要があります。^{そのため、因数分解される数値が 10 15}未満であると想定できるため、必ずしも漸近的に最適にスケーリングするアルゴリズムを探しているわけではありません。

ウィキペディアの Quadratic Sieve ページにリストされている実装のいくつかを既に見てきました。ただし、一部の実装は適切に管理されていないようです。ドキュメントがないものもあります。等々！Boost などのいくつかの有名なライブラリに因数分解メソッドがあるかどうかを確認しましたが、そうではないようです。

上記の基準を満たすライブラリを推奨できる人はいますか?

数を一連のに変換する単純な暗号があり ます。 （ ）

数値（0 .. 2147483647）をこの表現に暗号化するには、次のものが必要です。

• 素因数分解
• 与えられたp（pはPrime）に対して、pの順序シーケンス（つまり、 PrimeOrd（2） == 0、PrimeOrd（227） == 49）

いくつかの例

問題のソースコード

問題は、プロシージャPrimeOrdのスローネスです。素数の素数の順序を見つけるためのより速い解決策を知っていますか？

見出し

素数の順序をすばやく見つける方法を知っている場合は、何か提案してください。:-)

ありがとうございました。

PS 2,147,483,648未満の最大の素数は2,147,483,647で、105,097,565番目の素数です。2^31より大きい数を期待する必要はありません。

KenKen パズルは、エッジが接続されたドメインに分割されたラテン方陣です。1 つのセル、同じ行または列内の 2 つの隣接するセル、行またはエルに配置された 3 つのセルなどです。各ドメインには、ターゲットを与えるラベルがあります。数値と、ドメインのセル内の数値に適用してターゲット数値を生成する単一の算術演算 (+-*/)。(ドメインにセルが 1 つしかない場合、演算子は指定されず、ターゲットだけが指定されます --- 正方形は自動的に解決されます。演算子が - または / の場合、ドメインにはセルが 2 つしかありません。)パズルは、ドメインの境界とラベルと一致するラテン方陣を (再) 構築することです。(解が一意ではないパズルを一度だけ見たことがあると思います。)

セル内の数値は、1 からパズルの幅 (高さ) までの範囲で指定できます。通常、パズルは 1 辺が 4 または 6 セルですが、任意のサイズのパズルを検討してください。公開されたパズル (4x4 または 6x6) のドメインは、通常 5 つ以下のセルしかありませんが、これも厳しい制限ではないようです。(ただし、パズルのドメインが 1 つだけの場合、その次元のラテン方陣と同じ数の解が存在することになります...)

KenKen ソルバーを作成するための最初のステップは、最初はドメインのジオメトリを無視して、任意のドメインで可能な数値の組み合わせを生成できるルーチンを用意することです。(3 つのセルの行のような線形ドメインは、解決されたパズルで重複した数字を持つことはできませんが、当面はこれを無視します。) ケースバイケースで加算ラベルを処理する Python 関数を作成できました。パズルの幅、ドメイン内のセルの数、およびターゲットの合計であり、ターゲットに加算される有効な数値のタプルのリストを返します。

乗算のケースは私を避けます。与えられたサイズのパズルで与えられたサイズのドメインで達成可能な製品に等しいキーを持つ辞書を取得できます。値は、製品を与える要因を含むタプルのリストです。しかし、ケースを解決することはできません-ケースバイケースのルーチンであり、悪いものでもありません。

与えられた積を素数に因数分解するのは簡単に思えますが、素数のリストを必要な数の因数に分割することは私を困惑させます。(私は Knuth の TAOCP の Volume 4 の Fascicle 3 について熟考しましたが、彼のアルゴリズムの説明を「理解する」方法を学んでいないので、集合分割のための彼のアルゴリズムが出発点になるかどうかはわかりません。Knuth の説明を理解することは、別の質問！）

一般的なドメインとパズルのサイズの「乗算」辞書を事前に計算し、ロード時間をオーバーヘッドまでチョークするだけで十分ですが、そのアプローチは、たとえば、100 個のセルを片側にパズルし、サイズが 2 ～ 50 セルのドメイン。

私の理解では、最近の多くの公開鍵暗号化アルゴリズムは、鍵を構成するために大きな素数に依存しており、2つの素数の積を因数分解するのが難しいため、暗号化が破られにくくなっています。また、このような大きな数値を因数分解することが非常に難しい理由の1つは、使用される数値のサイズが非常に大きいため、32ビットと64ビットの非常に小さいCPUが一致しないため、CPUが数値を効率的に操作できないことを意味することも理解しています。 1024、2048、さらには4096ビット数の場合。これらの数値を処理するには、特殊なBig Integer数学ライブラリを使用する必要があります。また、CPUは一度に小さなチャンク（32ビットや64ビットなど）しか保持（および処理）できないため、これらのライブラリは本質的に低速です。

それで...

8ビットから16ビット、32ビットから64ビットのCPUにスケーリングしたのと同じように、2048ビットレジスタと巨大な算術回路を備えた高度に特殊化されたカスタムチップを構築できないのはなぜですか。このチップは、従来のCPUのほとんどの回路を必要とせず、結局のところ、仮想メモリ、マルチスレッド、I/Oなどを処理する必要はありません。保存された命令をサポートする汎用プロセッサである必要はありません。膨大な数に対して必要な算術計算を実行するための最低限のことです。

ICの設計についてはよくわかりませんが、論理ゲートのしくみ、半加算器、全加算器の作成方法、および多数の加算器をリンクしてマルチビット演算を行う方法について学んだことを覚えています。スケールアップするだけです。多くの。

さて、上記が機能しないという非常に正当な理由（または17）があることはかなり確信しています（そうでなければ、私よりも賢い多くの人々の1人がすでにそれを行っているため）が、その理由を知りたいと思っていますそれは動作しません。

（注：質問が理にかなっているかどうかはまだわかりませんので、この質問にはいくつかのやり直しが必要な場合があります）

数値を素因数分解するために次のプログラムを作成しました。

以下は私が得る出力です：

Altho'、戻り値は適切に出力されますが、戻り値の後は常に何も出力されないようです。私は何が欠けていますか？

また、プログラムを改善するにはどうすればよいですか（再帰を引き続き使用します）

私は最近、暗号化における素因数の一般的な使用について読んでいます。私が読んだところはどこでも、キーの素因数を見つけるために（指数時間ではなく）多項式時間で動作する「PUBLISHED」アルゴリズムはないと述べています。

多項式時間で動作するアルゴリズムが発見または公開された場合、理論やコンピューター サイエンスの世界とは対照的に、現実世界のコンピューティング環境にどのような影響を与えるでしょうか。私たちが暗号にどれだけ依存しているかを考えると、暗号は突然停止するでしょう。

これを念頭に置いて、P = NP が真である場合、何が起こるか、それがまだ証明されていないという事実にどれだけ依存するか.

私は初心者なので、質問の間違いをお許しください。

これは、私が読んでいる本のwhileループを理解するための例ですが、なぜ床分割してからy％xなのか、よくわかりません。誰かがこのコードを説明してもらえますか、それは何をしているのですか？

ありがとう！