Java 费马分解算法 BigInteger 不工作

Question

我正在使用 BigInteger 实现 Fermat 分解算法，所以我可以分解。但是目前，代码不起作用；它出于某种原因挂起。有人可以告诉我问题出在哪里，或者让我知道我的算法是否不正确？ BigInteger过不去，只好求求平方根法

import java.math.BigInteger;
import java.util.Scanner;

public class Fermat
{
    /** Fermat factor **/
    public void FermatFactor(BigInteger N)
    {
        BigInteger a = sqrt(N);
        BigInteger b2 = a.multiply(a).subtract(N);

        while (!isSquare(b2)) {
            a = a.add(a);
            b2 = a.multiply(a).subtract(N);
        }

        BigInteger r1 = a.subtract(sqrt(b2));
        BigInteger r2 = N.divide(r1);
        display(r1, r2);
    }

    /** function to display roots **/
    public void display(BigInteger r1, BigInteger r2) {
        System.out.println("\nRoots = "+ r1 +" , "+ r2);    
    }

    /** function to check if N is a perfect square or not **/
    public boolean isSquare(BigInteger N) {
        BigInteger ONE = new BigInteger("1");
        BigInteger sqr = sqrt(N);

        if (sqr.multiply(sqr) == N  || (sqr.add(ONE)).multiply(sqr.add(ONE)) == N)
            return true;
        return false;
    }


    public static BigInteger sqrt(BigInteger x)
            throws IllegalArgumentException {
        if (x.compareTo(BigInteger.ZERO) < 0) {
            throw new IllegalArgumentException("Negative argument.");
        }
        // square roots of 0 and 1 are trivial and
        // y == 0 will cause a divide-by-zero exception
        if (x == BigInteger.ZERO || x == BigInteger.ONE) {
            return x;
        } // end if
        BigInteger two = BigInteger.valueOf(2L);
        BigInteger y;
        // starting with y = x / 2 avoids magnitude issues with x squared
        for (y = x.divide(two);
                y.compareTo(x.divide(y)) > 0;
                y = ((x.divide(y)).add(y)).divide(two));
        if (x.compareTo(y.multiply(y)) == 0) {
            return y;
        } else {
            return y.add(BigInteger.ONE);
        }
    } // end bigIntSqRootCeil


    /** main method **/
    public static void main(String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Fermat Factorization Test\n");
        System.out.println("Enter odd number");
        BigInteger N = scan.nextBigInteger();
        Fermat ff = new Fermat();
        ff.FermatFactor(N);
        scan.close();
    }
}

我知道我有很多错误，但感谢您的帮助。谢谢

Answer 1

你的 "for" 循环：

for (y = x.divide(two);
    y.compareTo(x.divide(y)) > 0;
    y = ((x.divide(y)).add(y)).divide(two));

不终止。也许您可以跟踪变量 'y' 的值，以猜测何时必须停止。

编辑：那是错误的（见评论）。问题出在行

a = a.add(a)

内部程序 FermatFactor。应该是

a = a.add(ONE)

在我的机器上，我在使用 'A == B' 测试等式时也遇到了麻烦。方法 'A.equals(B)' 修复了它。

Java 费马分解算法 BigInteger 不工作

Java Fermat Factorisation algorithm BigInteger not working

java

algorithm

biginteger