java - 费马分解方法不起作用

Question

我正在开发一个程序来比较大整数因式分解的不同算法。我在比较中包含的算法之一是费马因式分解方法。该算法似乎对于较小的数字工作得很好，但是当我得到较大的数字时，我会得到奇怪的结果。

这是我的代码:

public void fermat(long n)
{
    ArrayList<Long> factors = new ArrayList<Long>();
    a = (long)Math.ceil(Math.sqrt(n));
    b = a*a - n;
    b_root = (long)(Math.sqrt(b)+0.5);
    while(b_root*b_root != b)
    {
        a++;
        b = a*a - n;
        b_root = (long)(Math.sqrt(b)+0.5);
    }
    factors.add(a-b_root);
    factors.add(a+b_root);
}

现在，当我尝试分解 42139523531366663 时，我得到结果因子 6194235479 和 2984853201，这是不正确的，因为 6194235479 * 2984853201 = 18488883597240918279。我认为我得到这个结果是因为在算法中的某个地方，我到达了一个点，数字在很长一段时间或类似的情况下变得太大，所以算法因此变得有点困惑。我添加了一个检查，计算两个因子的乘积并与输入值进行比较，这样如果分解错误我会收到警报:

long x,y;
x = factors.get(0);
y = factors.get(1);
if(x*y!=n)
    System.out.println("Faulty factorization.");

有趣的是，检查通过了，我没有收到警报。我尝试只打印乘法的结果，这实际上产生了输入值。所以我的问题是为什么我的程序会这样，我该怎么办？

Answer 1

看起来 long 某处存在溢出，因为 long 有 64 位，并且

42139523531366663 + 2^64 = 18488883597240918279

对于足够大的数字，您可能需要切换到使用 BigInteger .