I am working on a factorisation problem using Fermat's Factorization 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).
Just when I thought I had the problem licked I soon realised that my program was not working when it came to larger numbers. The program follows through the examples from the Wikipedia page, printing out the values a, b, a2 and b2; the results printed for large numbers are not correct. I've followed the pseudocode provided on the Wikipedia page, but am struggling to understand where to go next.
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. The code I am using so far is as follows:
import java.math.BigInteger;
/**
*
* @author AlexT
*/
public class Fermat {
private BigInteger a, b;
private BigInteger b2;
private static final BigInteger TWO = BigInteger.valueOf(2);
public void fermat(BigInteger N) {
// floor(sqrt(N))
BigInteger tmp = getIntSqrt(N);
// a <- ceil(sqrt(N))
a = tmp.add(BigInteger.ONE);
// b2 <- a*a-N
b2 = (a.multiply(a)).subtract(N);
final int bitLength = N.bitLength();
BigInteger root = BigInteger.ONE.shiftLeft(bitLength / 2);
root = root.add(b2.divide(root)).divide(TWO);
// while b2 not square root
while(!(isSqrt(b2, root))) {
// a <- a + 1
a = a.add(BigInteger.ONE);
// b2 <- (a * a) - N
b2 = (a.multiply(a)).subtract(N);
root = root.add(b2.divide(root)).divide(TWO);
}
b = getIntSqrt(b2);
BigInteger a2 = a.pow(2);
// Wrong
BigInteger sum = (a.subtract(b)).multiply((a.add(b)));
//if(sum.compareTo(N) == 0) {
System.out.println("A: " + a + "\nB: " + b);
System.out.println("A^2: " + a2 + "\nB^2: " + b2);
//}
}
/**
* Is the number provided a perfect Square Root?
* @param n
* @param root
* @return
*/
private static boolean isSqrt(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;
}
public BigInteger getIntSqrt(BigInteger x) { // It returns s where s^2 < x < (s+1)^2
BigInteger s; // final result
BigInteger currentRes = BigInteger.valueOf(0); // init value is 0
BigInteger currentSum = BigInteger.valueOf(0); // init value is 0
BigInteger sum = BigInteger.valueOf(0);
String xS = x.toString(); // change input x to a string xS
int lengthOfxS = xS.length();
int currentTwoBits;
int i=0; // index
if(lengthOfxS % 2 != 0) {// if odd length, add a dummy bit
xS = "0".concat(xS); // add 0 to the front of string xS
lengthOfxS++;
}
while(i < lengthOfxS){ // go through xS two by two, left to right
currentTwoBits = Integer.valueOf(xS.substring(i,i+2));
i += 2;
// sum = currentSum*100 + currentTwoBits
sum = currentSum.multiply(BigInteger.valueOf(100));
sum = sum.add(BigInteger.valueOf(currentTwoBits));
// subtraction loop
do {
currentSum = sum; // remember the value before subtract
// in next 3 lines, we work out
// currentRes = sum - 2*currentRes - 1
sum = sum.subtract(currentRes);
// currentRes++
currentRes = currentRes.add(BigInteger.valueOf(1));
sum = sum.subtract(currentRes);
} while(sum.compareTo(BigInteger.valueOf(0)) >= 0);
// the loop stops when sum < 0
// go one step back
currentRes = currentRes.subtract(BigInteger.valueOf(1));
currentRes = currentRes.multiply(BigInteger.valueOf(10));
}
s = currentRes.divide(BigInteger.valueOf(10)); // go one step back
return s;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Fermat fermat = new Fermat();
//Works
//fermat.fermat(new BigInteger("5959"));
// Doesn't Work
fermat.fermat(new BigInteger("90283"));
}
}
If anyone can help me out with this problem I'll be eternally grateful.
