問題タブ [factorization]

したがって、私の課題では、ユーザーに整数の入力を求めるプログラムを作成し、その数値の素因数分解を出力する必要があります。これは私が持っているものです:

私が今抱えている問題は、15453 などの数値で実行すると、素因数だけが必要な場合に 1 から 100 までのすべての因数とその指数のリストを取得することです。続行します。

私の仕事は、フェルマーの素因数分解法を使用して非常に大きな合成数を因数分解することです。数値は1024ビットで、10進数で約309桁です。

私は以下のPythonコードを思いつきました。これは、gmpy2正確さのためにモジュールを使用しています。これは、ウィキペディアのページに表示されている擬似コードのPython実装にすぎません。そのページの「ふるいの改善」のセクションを読みましたが、それを実装する方法がわかりませんでした。

このコードは、小さい数値の場合はかなり高速に実行されますが、問題で指定された数値と同じ大きさの数値の場合は時間がかかりすぎます。このコードの速度を改善するにはどうすればよいですか？私は自分のコードを書いてくれる人を探していませんが、いくつかの提案をいただければ幸いです。ご回答ありがとうございます。

私はコンピュータサイエンスの初心者です。実行時間について何かを学びましたが、理解したことが正しいかどうかわかりません。だから私を助けてください。

したがって、素因数分解は現在、多項式時間の問題ではありませんが、素数性テストは問題です。チェックする番号がnであると仮定します。1からsqrt（n）までのすべての数値がnを除算できるかどうかを判断するためだけにプログラムを実行し、答えが「はい」の場合は、その数値を格納します。このプログラムは多項式時間だと思いますね。

私が間違っている可能性のある方法の1つは、因数分解プログラムが最初に検出された素数ではなく、すべての素数を検出する必要があることです。だから多分これが理由です。

ただし、公開鍵暗号では、暗号を攻撃するには、多数の素因数を見つけることが不可欠です。通常、多数（公開鍵）は2つの素数の積にすぎないため、一方の素数を見つけることは、もう一方の素数を見つけることを意味します。これは多項式時間である必要があります。では、なぜ攻撃が困難または不可能なのですか？

通常、素因数分解を行ってすべての素因数を取得し、順列と組み合わせを行ってすべての因数を見つけます。

例: 1824 は因数分解しようとしている数値です。ここで、300 の中に 1824 の因数が必要です。

何かコツはありますか？？

Xで を解決する必要があるこの問題がありAX=Bます。A15000 x 15000 のオーダーで、まばらで対称的です。B15000 X 7500 で、まばらではありません。X を解くための最速の方法は何ですか?

2通り考えられます。

1. 可能な限り簡単な方法、X = A\B

2. forループを使用して、

   /li>

上記の2つよりも良い方法はありますか？そうでない場合、私が言及した2つの中でどちらが最適ですか?

欠損値 (NA) を処理し、それらを 0 と見なさない、R の NMF (非負行列因数分解) 用のパッケージ/可能な場合は比較的既製のソリューションを探しています。

実際の目標は、単純なレコメンデーション システムのために、因数分解の積を通じてこれらの欠損値を推定することです。

NMF CRANパッケージは素晴らしいですが、それができないようです（最近のCRAN以外の継続もそうではありません）。適切な代替パッケージが見つかりませんでした...

pymfモジュールを使用して、データセットに行列因数分解を適用してみます。pymfサイトの例で説明されているように、私はを使用non-negative matrix factorizationしているので、いくつかのW-および-H行列を取得します。W-vectorが分散の説明に従って返されることをどのように確認できますか？私はそれをマニュアルで見つけることができませんでした、そして私のすべてのテストでそれはそうでした。すでにソートされている場合は、再度ソートすることは避けたいと思います。

そうでない場合：一般的に最速の方法はありますか？

私はどちらかのようなものを考えました

また

？

私は宿題のためにこの質問を設定しました：

因数分解への別のアプローチは、1643 年に Fermat によって使用されました。これは、小さい因数よりも大きい因数を見つけるのに適しています。n が奇数であり、n = u × v であると仮定します。n = x^2 − y^2 に従います。ここで、x = (u + v)/2 と y = (v − u)/2 は両方とも整数です。数字（なぜ？）フェルマーの方法は、x^2 − y^2 = n および 0 ≤ y < x となるような y が存在する x の最小値を体系的に検索することで構成されます。

演習 11. x の可能な最小値、つまり検索を開始する値は? ある段階で、検索が x ≥ p および y ≥ q に絞り込まれたとします。r = p^2 − q^2 − n とします。r = 0 の場合、完了です。r < 0 の場合、p または q をどのように変更すればよいでしょうか? また、r = p^2 − q^2 − n を維持するために r を変更するにはどうすればよいでしょうか? r > 0 の場合はどうなるでしょうか。このメソッドがすべての奇数 n で終了することが保証されているのはなぜですか? search pqr が検索を実行するように関数検索を設計します。したがって、与えられた奇数の 2 つの因数を返す関数 fermat を設計します。

これは私がこれまでに持っているものです:

これは、33 のような一部の数値 (期待どおり (3,11) を取得) では機能しますが、99 のような他の数値 ((9,11) ではなく (1,99) を取得) では機能しません。q の初期値には別のものを使用する必要があると思います。いくつかのヒントをいただければ幸いです。

q の初期値を に変更しようとしましたisqrt( abs(p*p-n))が、それでも 99 が (3, 33) になり、正しくありません。

私はオイラーのTotient関数のバージョンを動作させることができましたが、小さい数値で動作するものはあります(ここでは、計算に必要な1024ビット数値と比較して小さいです)

私のバージョンはここにあります -

これは小さい数値に対しては機能しますが、1 から計算中の数値まで可能な限りすべて反復することによって機能します。大きな BigInteger では、これはまったく実行不可能です。

各反復で数を分割することが可能であり、それらを1つずつ処理する必要がなくなることを読みました。何を何で割るべきかわかりません (私が見た例のいくつかは C であり、long と平方根を使用しています - 私の知る限り、正確な正確な計算はできませんBigInteger の平方根また、このような剰余算術の場合、mod が何であるかを示す引数を関数に含める必要があるかどうかも疑問に思っています。

ここで誰かが私を正しい方向に向けることができますか?

PS Euler Totient Function の変更を見つけたときに、この質問を削除しました。BigIntegers で動作するように調整しました -

そして、正確な結果が得られます.1024ビットの数値を渡すと、ビットは永遠に実行されます（終了したかどうかはまだわかりません.20分間実行されています）。

連立一次方程式を解くには、MKLを使用する必要があります。この連立方程式は2Dポアソン問題を解くために使用されるため、正確に5つの対角線は0とは異なります。システムAx = bの行列Aは正方形で、そのサイズはn*nです。Intelのドキュメントを調べましたが、呼び出しシーケンスについて少し戸惑っています。プロトタイプは次のとおりです。

1）matrix_order。行列の次数は、行と列の数の間で最大になります。ライブラリは2番目と3番目のパラメータからそれを理解するべきではありませんか？

2）mおよびn。これらは元の行列Aを参照していますか、それともバンドストレージの表現を参照していますか？

3）バンドストレージ。問題の構造を考えると、主対角線の上にd対角線があり、主対角線の下にd対角線があるので、因数分解用の追加の行を含めて、バンドストレージのメモリ領域は（n * n）*（3 * d + 1）要素。要素は列単位です。私は正しいですか？

4）主要な次元。これは（3 * d + 1）である必要があります

どんな助けでも大歓迎です