java - Pollard Rho 算法陷入循环

Question

我正在尝试实现 Pollard 的 Rho 算法来查找整数 n 的因数。我有一个通常有效的实现，但现在遇到了一些问题。在这种情况下，我的 n = 262063。

这是我的 Rho 算法，以及引用的 getGCD() 和 pollardRhoFunction() [我保留了 println，以便之后提供结果]:

public static int pollardRho(int n, int xStart){

    // the function we will be using is f(x)=x^2+1, as per our textbook,            
    // (in question# 5.26)

    int x = xStart;
    int xPrime = pollardRhoFunction(x) % n;
    int p = getGCD(x-xPrime, n);
    int nmbr = 0;
    System.out.println("x="+x);
    System.out.println("xPrime="+xPrime);
    System.out.println("p"+p);

    while (p == 1||p==31313||p==20||p==75||p==25||p == n ||p==262063){
        System.out.println("i="+nmbr);
        x = pollardRhoFunction(x) % n;
        xPrime = pollardRhoFunction(xPrime) % n;
        System.out.println("xPrime="+xPrime);
        xPrime = pollardRhoFunction(xPrime) % n;
        System.out.println("xPrime="+xPrime);
        p = getGCD(x-xPrime, n);
        nmbr++;
    }
    updateIterNmbrs(nmbr);
    if (p == n){
        return -1;
    }
    else{
        return p;
    }
}
public static int getGCD(int a, int b){
int a_0 = a;
int b_0 = b;
int q = (int)Math.floor(a_0/b_0); 
int r = a_0 - q*b_0;
while (r > 0){
    a_0 = b_0;
    b_0 = r;
    q = (int)Math.floor(a_0/b_0);
    r = a_0 - q*b_0;    
} 

r = b_0;
return r;
}

public static int pollardRhoFunction(int x){

    // the function we will be using is f(x)=x^2+1, as per our textbook,            
    // (in question# 5.26)

    int result = (int)Math.pow(x,2)+2;
    //System.out.println("x^2+1="+result);
    return result;
}

一段时间后，它陷入了一个循环。这是 System.out.println() 的(一些)打印输出:

 x=1
 xPrime=3
 p262063
 i=0
 x=3
 xPrime=11
 xPrime=123
 r= -120; a_0= -120; b_0= 262063
 p262063
 i=1
 x=11
 xPrime=15131
 xPrime=166164
 r= -166153; a_0= -166153; b_0= 262063
 p262063
 i=2
 x=123
 xPrime=-139425
 xPrime=-139425
 r= 139548; a_0= 139548; b_0= 262063
 r= 122515; a_0= 262063; b_0= 139548
 r= 17033; a_0= 139548; b_0= 122515
 r= 3284; a_0= 122515; b_0= 17033
 r= 613; a_0= 17033; b_0= 3284
 r= 219; a_0= 3284; b_0= 613
 r= 175; a_0= 613; b_0= 219
 r= 44; a_0= 219; b_0= 175
 r= 43; a_0= 175; b_0= 44
 r= 1; a_0= 44; b_0= 43
 r= 0; a_0= 43; b_0= 1
 p1
 i=3
 x=15131
 xPrime=-139425
 xPrime=-139425
      r= 154556; a_0= 154556; b_0= 262063
 r= 107507; a_0= 262063; b_0= 154556
 r= 47049; a_0= 154556; b_0= 107507
 r= 13409; a_0= 107507; b_0= 47049
 r= 6822; a_0= 47049; b_0= 13409
 r= 6587; a_0= 13409; b_0= 6822
 r= 235; a_0= 6822; b_0= 6587
 r= 7; a_0= 6587; b_0= 235
 r= 4; a_0= 235; b_0= 7
 r= 3; a_0= 7; b_0= 4
 r= 1; a_0= 4; b_0= 3
 r= 0; a_0= 3; b_0= 1
 p1
 i=4
 x=166164
 xPrime=-139425
 xPrime=-139425
 r= 43526; a_0= 305589; b_0= 262063
 r= 907; a_0= 262063; b_0= 43526
 r= 897; a_0= 43526; b_0= 907
 r= 10; a_0= 907; b_0= 897
 r= 7; a_0= 897; b_0= 10
 r= 3; a_0= 10; b_0= 7
 r= 1; a_0= 7; b_0= 3
 r= 0; a_0= 3; b_0= 1
 p1
 i=5
 x=-139425
 xPrime=-139425
 xPrime=-139425
 r= 0; a_0= 0; b_0= 262063
 p262063
 i=6
 x=-139425
 xPrime=-139425
 xPrime=-139425
 r= 0; a_0= 0; b_0= 262063
 p262063
 i=7
 x=-139425
 xPrime=-139425
 xPrime=-139425
 r= 0; a_0= 0; b_0= 262063
 p262063
 i=8
 x=-139425
 xPrime=-139425
 xPrime=-139425
 r= 0; a_0= 0; b_0= 262063
 p262063
 i=9
 x=-139425
 xPrime=-139425
 xPrime=-139425
 r= 0; a_0= 0; b_0= 262063
 p262063
 i=10
 x=-139425
 xPrime=-139425
 xPrime=-139425
 r= 0; a_0= 0; b_0= 262063
 p262063

你明白了......出于某种原因它卡在了某个点......

Answer 1

您似乎在这一行中有错误:

int result = (int)Math.pow(x,2)+2;

应该这样读

int result = x*x + 1;