java Pollard Rho找不到因子

Question

因此，我尝试在Java中创建一个Pollard的Rho分解算法，使用BigInteger类来支持非常大的整数。代码基本上可以工作，但找不到4或8的因子（应该是2）。目前，我已经将其限制为在算法中循环10000000次，但仍然无法找到2作为因子a是随机生成的（限制在0到1000之间）。这只是Pollard Rho算法中的一个缺陷，还是实现中的某个地方存在错误

正在传递的n是4

初始值a以与下面代码中相同的方式计算为随机值，介于0和1000之间

sqrt(n)方法返回n的平方根的下限（在本例中sqrt(sqrt(4)) = 1

我在最后打印了count，以确保它实际迭代了它应该迭代的次数

private static BigInteger PollardRho (BigInteger a, BigInteger n) {

    BigInteger gcd = BigInteger.ZERO;

    BigInteger Tort = a;

    BigInteger Hare = a;

    BigInteger count = BigInteger.ZERO;

    BigInteger iterationLim = (sqrt(sqrt(n))).multiply(BigInteger.valueOf(10000000));

    while (count.compareTo(iterationLim)!=0)
    //makes sure that the algorithm does not surpass (4th root of n)*10000000 iterations.
    {

    Tort = ((Tort.pow(2)).add(BigInteger.ONE)).mod(n);

    //System.out.println("Tort: "+Tort);

    Hare = (((Hare.pow(2)).add(BigInteger.ONE).pow(2)).add(BigInteger.ONE)).mod(n);

    //System.out.println("Hare: "+Hare);

    gcd = (Tort.subtract(Hare)).gcd(n);

    //System.out.println("gcd: "+gcd);

    if (gcd.compareTo(BigInteger.ONE) != 0 && gcd.compareTo(n) != 0)
    {
    //  System.out.println("took if, gcd = "+gcd);

        return gcd;
    }

    if (gcd.compareTo(n) == 0)
    {
        a = (BigInteger.valueOf((long) (1000*Math.random())));
        Tort = a;
        Hare = a;
    }

    count = count.add(BigInteger.ONE);

    }

    System.out.println(count);
    return n;


}

Answer 1

Pollard的Rho方法通常只能拆分由不同素数组成的数。对于素数幂的数字，它在大多数情况下都失败了。4和8是单个素数2的幂，因此不太可能用这种方法分割

该方法通过迭代一个随机函数f（x）mod n来工作，在这种情况下使用f（x）=x^2+1，但其他函数也可以工作。诀窍是f（x）mod p，其中p是n的素因子，在不同素数的不同迭代次数后进入一个循环。所以f（x）mod p1可能已经在一个循环中，f（x）mod p2还没有。然后，gcd计算能够找到系数p1

顺便说一句，很容易检查一个数字是否是整数的适当幂。只需计算第二、第三、第四。。。根并检查它是否为整数