問題タブ [factorization]

方法に問題がありtestPerfectます。因子を計算して配列に入れ、数値が完全かどうかのブール値を返すためにtrue必要falseです。今のところ、配列は 1,2,3...5,6,7... を取得しているだけで、チェックするために入力された数字は何でも構いません。助言がありますか？

私の入力はIntegerです。その値までは、すべての素数を見つけて5列に出力する必要があります。次に、整数を「素数分解」して結果を出力する必要があります。

それはうまくいきますが、遅すぎません...

}

どこでリソースを節約できますか？ところで、今のところ配列しか使えません...ドイツ語のコメントでごめんなさい。本当に不要な長いループなどが目に入った場合

ありがとう！

数の因数を見つけるための公式を考えるのに助けが必要です：

パラメータとして整数を受け取り、fencepostループを使用して、単語「と」で区切られたその数値の因数を出力するprintFactorsという名前のメソッドを記述します。たとえば、24の因数は次のように出力されます。

数値パラメータの値は0より大きいと想定できます。

自分で試してみたいので、COMPLETEプログラムを教えてはいけません。

現在のコードには、表示される「and」の数を制御するforループがありますが、「24 and」を付けたくないので、最後の数を単独で出力しました...出力は次のようになります。現時点では次のようなものです：「1と2と3」（私はまだ方程式を考えていません。したがって、1,2,3 ...）

私は現在、要因には％種類の式が必要だと考えていますよね？分割が必要ですか？私はまた、1と数自体が常にそれ自体の要因であるため、1とあなたが要因を見つけている数（この場合は24）を印刷することを考えていました。他に何が欠けていますか？

前もって感謝します！！:)

楕円曲線因数分解アルゴリズムの誕生日のパラドックスの続きを、因数分解プログラムのコレクションに追加したいと思います。ブレントは2つの 論文でアルゴリズムを説明しており、モンゴメリーもアルゴリズムを説明しており、私はBosmaとLenstraによる詳細な説明に従ってアルゴリズムを実装しようとしています。以下は、これまでに Python で作成したもので、 ideone.com /vMXSabで実行できます。

この関数はエラトステネスのふるいの単純なバージョンを実装し、nprimes未満の素数のリストを返します。関数は拡張ユークリッド アルゴリズムを実装し、aの逆数、bの逆数、およびそれらの最大公約数を返します。楕円演算は関数と関数によって与えられます。add は「ポイント」 (0, 0, d ) を返し、非可逆分母を通知し、それを伝播します。因数分解関数での の使用は、呼び出されるたびにそれをチェックする必要があります。関数は、楕円曲線因数分解の単純な 1 段階バージョンであり、適切に動作します。bezoutaddmulmulmulmullenstra1

関数lenstra2とその補助関数parmsは、上記の Bosma/Lenstra の論文に記載されているアルゴリズムを実装しようとする私の試みです。セクション 6.4 と 6.7 の最適化を考慮せずに、セクション 6.1 で説明されているように、最初に基本的なバージョンを機能させようとしています。parmsの計算は正しいと思います。関数は実行されますが、常に を返しますFalse。これは、因数が見つからなかったことを示します。または、アルゴリズムを完了して最終的なgcd計算から戻る前に、楕円演算の早期中断後に戻ります。問題はfの係数の計算と、 fを使用したdの計算にあると思います。

だから私の質問：

1. fの係数を正しく計算しましたか?
2. dの値を正しく計算しましたか?
3. セクション 6.4 と 6.7 の最適化を実装するにはどうすればよいですか? どちらもわかりません。
4. セクション 5.1 の Suyama 曲線を Weierstrass 座標を使用して実装するにはどうすればよいですか?

どうもありがとう。

RSAアルゴリズムを検討しており、RSA公開鍵を因数分解するのにIntel i-7コア（@ 2.50 gHz）にかかる時間を知りたいと思います。

このためにJavaを作成しましたが、それがどれほど効果的かはわかりません。

2 ^ 45前後の数値では、PCに約33ミリ秒かかりました。理論的には、2 ^ 1024前後の数を因数分解するのにどのくらい時間がかかりますか？

前もって感謝します ：）

画像処理アルゴリズムの実装では、次の形式の大規模な線形システムを解く必要がA*x=bあります。

• 行列A=L+Dは、ラプラシアン行列 L と対角行列 D の和です
• ラプラシアン行列 L はスパースで、行ごとに約 25 個の非ゼロがあります
• システムは大規模で、入力イメージ内のピクセルと同じ数の未知数があります (通常 > 100 万)。

ラプラシアン行列 L は、アルゴリズムの連続実行間で変化しません。前処理でこの行列を構築し、おそらくその因数分解を計算できます。対角行列 D と右辺ベクトル b は、アルゴリズムの実行ごとに変化します。

実行時にシステムを解決する最速の方法を見つけようとしています。前処理 (たとえば、L の因数分解を計算するため) に時間を費やすことは気にしません。

私の最初のアイデアは、L のコレスキー分解を事前に計算し、実行時に D の値で分解を更新し (cholupdate を使用してランク 1 を更新)、逆置換で問題をすばやく解決することでした。残念ながら、コレスキー分解は元の L 行列ほどスパースではなく、ディスクからロードするだけでもすでに 5.48 秒かかります。比較として、バックスラッシュを使用してシステムを直接解決するには 8.30 秒かかります。

私の行列の形状を考えると、前処理時間にどれだけ時間がかかっても、実行時の解決を高速化するために推奨する他の方法はありますか?

私は Python をいじり始めたばかりで、時間をつぶすためにいくつかの断片をまとめています。私は素数のテストで遊んでいて、非素数の因数を示すという考えを持っていました。上記でまとめた関数は、一貫性のない出力が得られることを除いて、十分に機能しているようです。

たとえば、n = 65432 に設定すると...

それは私が期待するものです。しかし、n = 659306 に設定すると...

最後に係数 329653 が含まれていないため、これは異なります。すべての要因がどこかに表示されるので、これは問題ではありませんが、いくつかの数値でなぜこれが起こるのか分からないのは私を悩ませています!

私が完全なバカではないことを示すために、これは長さが 5 文字を超える整数値でのみ発生するように思われることを突き止めました。これら2つのケースで出力が異なる理由を教えてください。

$μ（n）= 0 $の場合、整数nには多重度のある因子が少なくとも1つあることがわかります。

有理数（m / n）> 1を素因数に分解する際に、（-1）未満のべき乗があるかどうかをどのように判断できますか？例えば

数学のメビウス関数μに似た関数で、この仕事をしてくれるものはありますか？コードを書くことはできると思いますが、Mathematicaで定義された関数が必要ですか？

ありがとう

大きな整数の因数分解のさまざまなアルゴリズムを比較するプログラムに取り組んでいます。比較に含めているアルゴリズムの 1 つは、Fermats 因数分解法です。このアルゴリズムは、小さな数では問題なく機能しているように見えますが、大きな数になると奇妙な結果が得られます。

これが私のコードです：

ここで、42139523531366663 を因数分解しようとすると、結果の因数6194235479と2984853201が得られます。この結果が得られたのは、アルゴリズムのどこかで数字が長くなりすぎたり、似たようなものになるポイントに到達したためだと考えました。そのため、アルゴリズムが少し混乱しました。2 つの因数の積を計算し、入力値と比較するチェックを追加して、因数分解に問題がある場合にアラートを受け取るようにしました。

興味深いことに、チェックは true として渡され、アラートは表示されませんでした。乗算の結果を印刷してみましたが、これが実際に入力値になりました。私の質問は、なぜ私のプログラムがこのように動作するのか、それに対して何ができるのかということです。

私のmatlabコード内で、特定の行列のコレスキー分解を処理する必要があります。私は通常chol(A,'lower')、下三角因子を生成するために呼び出しています。

今、私のコードを でチェックすると、特に入力行列のサイズが大きくなった場合、関数が本当に時間がかかるprofilerことが明らかです。chol

cholしたがって、組み込み関数に代わる価値のあるものがあるかどうかを知りたいです。

LAPACK私は図書館、つまりspptrf関数について考えてきました。で利用できますMATLABか?

ヒントやサポートは大歓迎です。

編集

例として、プロファイラーは次の情報を取得します。

どこCoh_uにサイズがあります(1395*1395)。また、さまざまな構成でコレスキー係数が必要なため、時間cholと呼ばれることにも注意してください。40004000