Require help with program for edutainment game

Question

I am working on a factorisation problem and for small numbers it is working well. I've been able to calculate the factors (getting the answers from Wolfram Alpha) for small numbers, like the one on the Wikipedia page (5959).

Along with the Wikipedia page I have been following this guide. Once again, as my Math knowledge is pretty poor I cannot follow what I need to do next.

EDIT: It finally works! I'll post the working code up here once I've got it fully working so that others in my predicament can learn from it.

Answer 1

That getIntSqrt() method... I don't know if it's ok, but it looks awful (convert the BigInteger to String ??) Have you checked it?

Here is a (apparently) better method.

Answer 2

In your loop:

// while b2 not square
while(!(isSqrt(b2, root))) {

what is the purpose of the following instruction?

    root = root.add(b2.divide(root)).divide(TWO);

I think that in order to check that b2 is a square, you should instead try to compute the square root (the above instruction is just one step of the canonical algorithm to compute square roots), with the method you already have:

    root = getIntSqrt(b2);

The same observation applies to this code:

// ??
final int bitLength = N.bitLength();
BigInteger root = BigInteger.ONE.shiftLeft(bitLength / 2);
root = root.add(b2.divide(root)).divide(TWO);

EDIT. The problem is that your sqrt() method needs an isSqrt() that checks whether root is an approximate root of n, whereas the loop in fermat() needs an exact check. I append some code that seems to pass your last test:

import java.math.BigInteger;

public class Fermat {

private BigInteger a, b, N;
private static final BigInteger TWO = BigInteger.valueOf(2);

private static boolean isApproximateSqrt(BigInteger n, BigInteger root) {
    final BigInteger lowerBound = root.pow(2);
    final BigInteger upperBound = root.add(BigInteger.ONE).pow(2);
    return lowerBound.compareTo(n) <= 0
        && n.compareTo(upperBound) < 0;
}

private static BigInteger intSqrt(BigInteger n) {
    if (n.signum() >= 0) {
        final int bitLength = n.bitLength();
        BigInteger root = BigInteger.ONE.shiftLeft(bitLength / 2);

        while ( ! isApproximateSqrt(n, root) ) {
            root = root.add(n.divide(root)).divide(TWO);
        }
        return root;
    } else {
        throw new ArithmeticException("square root of negative number");
    }
}

private void init() {
    a = intSqrt(N);                             // a <- ceil(sqrt(N))
    BigInteger b2, root;
    do {
        a = a.add(BigInteger.ONE);              // a <- a + 1
        b2 = (a.multiply(a)).subtract(N);       // b2 <- (a * a) - N
        root = intSqrt(b2);
    } while( root.pow(2).compareTo(b2) != 0 );  // while b2 not exact sqrt
    b = root;
}

public void print() {
    BigInteger a2 = a.pow(2);
    BigInteger b2 = b.pow(2);
    BigInteger squareDifference = a2.subtract(b2);
    System.out.println("A: " + a + "\nB: " + b);
    System.out.println("A^2: " + a2 + "\nB^2: " + b2);
    System.out.println("N: " + N);
    if(squareDifference.compareTo(N) != 0) {
        System.out.println("Something is wrong....");
    }
}

public Fermat(BigInteger aNumber) {
    N = aNumber;
    init();
}

public static void main(String[] args) {
    Fermat f = new Fermat(new BigInteger("90283"));
    f.print();
}
}