2

以下のアルゴリズムがエラーのない整数因数分解メソッドであり、常にNの自明でない因数を返す理由を誰かに説明してもらえますか？これがいかに奇妙に聞こえるかは知っていますが、2年前にこのメソッドを設計しましたが、まだ理解していません。その背後にある数理論理学は、私がそれを改善することを困難にしている。とてもシンプルなので、足し算と引き算だけが必要です。

public static long factorX( long N )
{
    long x=0, y=0;
    long b = (long)(Math.sqrt(N));
    long a = b*(b+1)-N;
    if( a==b ) return a;

    while ( a!= 0 )
    {
        a-= ( 2+2*x++ - y);
        if( a<0 ) { a+= (x+b+1); y++; }
    }

return ( x+b+1 );
}

上記の方法は、実際にはディオファントス方程式の反復によって解を見つけるようです。

f(x,y) = a - x(x+1) + (x+b+1)y
where b = floor( sqrt(N) ) and a = b(b+1) - N
that is, when a = 0, f(x,y) = 0 and (x+b+1) is a factor of N.

Example: N = 8509  
b = 92, a = 47  
f(34,9) = 47 - 34(34+1) + 9(34+92+1) = 0  
and so x+b+1 = 127 is a factor of N.

メソッドを書き直す：

public static long factorX(long N)
{
long x=1, y=0, f=1;
long b = (long)(Math.sqrt(N));
long a = b*(b+1)-N;
if( a==b ) return a;

  while( f != 0 )
  {
    f = a - x*(x+1) + (x+b+1)*y;
      if( f < 0 ) y++;
    x++;
  }

return x+b+1;
}

この方法を改善する方法についての提案を本当にいただければ幸いです。

18桁のランダムな半素数10個のリストは次のとおりです。

349752871155505651 = 666524689 x 524741059   in 322 ms
259160452058194903 = 598230151 x 433211953   in 404 ms
339850094323758691 = 764567807 x 444499613   in 1037 ms
244246972999490723 = 606170657 x 402934339   in 560 ms
285622950750261931 = 576888113 x 495109787   in 174 ms
191975635567268981 = 463688299 x 414018719   in 101 ms
207216185150553571 = 628978741 x 329448631   in 1029 ms
224869951114090657 = 675730721 x 332780417   in 1165 ms
315886983148626037 = 590221057 x 535201141   in 110 ms
810807767237895131 = 957028363 x 847213937   in 226 ms
469066333624309021 = 863917189 x 542952889   in 914 ms
4

3 に答える 3

2

OK、Matlab を使用して、ここで何が起こっているかを確認しました。N=100000 の結果は次のとおり です。各反復でここに画像の説明を入力 増加xしており、変な変数のパターンはa残りと強く関連してN % x+b+1います (プロットの灰色の線でわかるように、a + (N % (x+b+1)) - x = floor(sqrt(N)))。したがって、単純な反復よりも大きな最初の要因を見つけているだけだと思いsqrt(N)ますが、それが実際に要因であると判断するためのかなりあいまいな基準があります:D(半分答えて申し訳ありません...私は去らなければなりません、多分後で続きます）。

自分でテストしたい場合に備えて、matlab コードを次に示します。

clear all
close all

N = int64(100000);

histx = [];
histDiffA = [];
histy = [];
hista = [];
histMod = [];
histb = [];

x=int64(0);
y=int64(0);
b = int64(floor(sqrt(double(N))));
a = int64(b*(b+1)-N);
if( a==b ) 
    factor = a;
else
    while ( a ~= 0 )
        a = a - ( 2+2*x - y);
        histDiffA(end+1) = ( 2+2*x - y);
        x = x+1;
        if( a<0 ) 
            a = a + (x+b+1); 
            y = y+1;
        end
        hista(end+1) = a;
        histb(end+1) = b;
        histx(end+1) = x;
        histy(end+1) = y;
        histMod(end+1) = mod(N,(x+b+1));
    end
    factor = x+b+1;
end

figure('Name', 'Values');
hold on
    plot(hista,'-or')
    plot(hista+histMod-histx,'--*', 'Color', [0.7 0.7 0.7])
    plot(histb,'-ob')
    plot(histx,'-*g')
    plot(histy,'-*y')
    legend({'a', 'a+mod(N,x+b+1)-x', 'b', 'x', 'y'}); % 'Input',
hold off

fprintf( 'factor is %d \n', factor );
于 2013-02-08T11:39:35.820 に答える
1

あなたの方法は、（na）*（n + b）の試行乗算の変形です。ここで、n = floor（sqrt（N））およびb==1です。

次に、アルゴリズムは、（na）*（n + b）-N==0の差になるまでa--/b++を繰り返します。

（aとbに関する）部分的な違いは、それぞれ2bと2aに比例します。したがって、真の乗算は必要ありません。

複雑さは|a|の一次関数です または|b| --「正方形」のNが多いほど、メソッドの収束が速くなります。要約すると、はるかに高速な方法があり、最も理解しやすい方法の1つは、平方剰余ふるいです。

于 2013-02-12T11:33:44.870 に答える
0

私のC＃を許してください、私はJavaを知りません。x と y を 2 ずつ進めると、アルゴリズムの速度が上がります。

using System.Numerics;                      // needed for BigInteger
    /* Methods ************************************************************/
    private static BigInteger sfactor(BigInteger k) // factor odd integers
    {
        BigInteger x, y;
        int flag;
        x = y = iSqrt(k);                   // Integer Square Root
        if (x % 2 == 0) { x -= 1; y += 1; } // if even make x & y odd
        do
        { 
            flag = BigInteger.Compare((x*y), k);
            if (flag > 0) x -= 2;
            y += 2;
        } while(flag != 0);
        return x;                           // return x
    } // end of sfactor()

    // Finds the integer square root of a positive number
    private static BigInteger iSqrt(BigInteger num)
    {
        if (0 == num) { return 0; }           // Avoid zero divide
        BigInteger n = (num / 2) + 1;         // Initial estimate, never low
        BigInteger n1 = (n + (num / n)) >> 1; // right shift to divide by 2
        while (n1 < n)
        {
            n = n1;
            n1 = (n + (num / n)) >> 1;        // right shift to divide by 2
        }
        return n;
    } // end iSqrt()

于 2015-11-15T00:10:57.970 に答える