我正在开发一个程序来比较大整数因式分解的不同算法。我在比较中包含的算法之一是费马因式分解方法。该算法似乎对于较小的数字工作得很好,但是当我得到较大的数字时,我会得到奇怪的结果。
这是我的代码:
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.");
有趣的是,检查通过了,我没有收到警报。我尝试只打印乘法的结果,这实际上产生了输入值。所以我的问题是为什么我的程序会这样,我该怎么办?
最佳答案
看起来 long
某处存在溢出,因为 long 有 64 位,并且
42139523531366663 + 2^64 = 18488883597240918279
对于足够大的数字,您可能需要切换到使用 BigInteger
.
关于java - 费马分解方法不起作用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15072992/