8

与えられた数の因子を見つけるアルゴリズムを開発しました。したがって、与えられた数が素数であるかどうかを見つけるのにも役立ちます。これが因子や素数を見つけるための最速のアルゴリズムだと思います。

このアルゴリズムは、与えられた数が5 * Nの時間枠で素数であるかどうかを検出します（ここで、Nは入力数です）。したがって、これを線形時間アルゴリズムと呼べることを願っています。

これが利用可能な最速のアルゴリズムであるかどうかを確認するにはどうすればよいですか？誰かがこの問題で助けることができますか？（GNFSやその他の既知のものよりも高速です）

アルゴリズムを以下に示します

Input: A Number (whose factors is to be found)
Output: The two factor of the Number. If the one of the factor found is 1 then it can be concluded that the
Number is prime.

Integer N, mL, mR, r;
Integer temp1; // used for temporary data storage
mR = mL = square root of (N);
/*Check if perfect square*/
temp1 = mL * mR;
if temp1 equals N then
{
  r = 0; //answer is found
  End;
}
mR = N/mL; (have the value of mL less than mR)
r = N%mL;
while r not equals 0 do
{
  mL = mL-1;
  r = r+ mR;

  temp1 = r/mL;
  mR = mR + temp1;
  r = r%mL;
}
End; //mR and mL has answer

あなたのコメントを提供してください..詳細については私に連絡することを躊躇しないでください。

ありがとう、ハリッシュ http://randomoneness.blogspot.com/2011/09/algorithm-to-find-factors-or-primes-in.html

4

3 に答える 3

14

「線形時間」とは、入力データの長さに比例する時間を意味します。この場合、因数分解しようとしている数値のビット数です。あなたのアルゴリズムは線形時間またはそれに近いもので実行されません、そして私はそれが多くの既存の因数分解アルゴリズムよりはるかに遅いのではないかと心配しています。（例えば、GNFSを含む。）

于 2011-04-07T12:34:03.287 に答える