Need help with edutainment software

Question

I am working on a factorization problem and works well for small numbers. I was able to calculate factors (getting answers from Wolfram Alpha) for small numbers, for example, on the Wikipedia page (5959).

Along with the Wikipedia page, I was in accordance with this guide . Once again, since my mathematical knowledge is rather poor, I cannot follow what I need to do next.

EDIT: It finally works! I will write the working code here as soon as I can, that it will work fully so that others in my predicament can learn from it.

Answer 1

In your loop:

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

What is the purpose of the following instructions?

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

I believe that in order to check what b2is a square, you should try to calculate the square root (the above instruction is just one step of the canonical algorithm to calculate the square roots), using the method that you already have:

    root = getIntSqrt(b2);

The same 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 method sqrt()needs isSqrt()one that checks to see if the rootapproximate root of is n, while the loop fermat()needs an accurate check. I am adding 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();
}
}

Answer 2

getIntSqrt()... , , ( BigInteger String?) ?

(-) .

Answer 3

Your function isSqrt()is incorrect for what you are trying to do. You want to know, if for n = root^2sure, but your function is isSqrt()written to return "true" if it njust lies in the interval (root^2, (root+1)^2).

I think all you have to do is check what nis equal root.pow(2).