import java.math.BigInteger;
import java.security.SecureRandom;

/*****************************************************************************
 *                             Fermat Factorization                          *
 * 						                             *
 * 			         Christer Karlsson                           *							
 *                                                                           *
 * Let n be a an odd positive integer, and a*b be the factorization          *
 * of n into two poistive integers.                                          *
 * Then n can be written as the difference between two squares               *
 * n = a*b = s^2 - t^2                                                       *
 * where s = (a+b)/2 and t = (a-b)/2                                         *
 *                                                                           *
 *****************************************************************************/

public class Fermat {

	public static void main( String[] args)
	{
		BigInteger one      = new BigInteger("1");
		BigInteger two      = new BigInteger("2");
		SecureRandom random = new SecureRandom();
		
    	// Variables
	boolean solved = false;
	int bitlength  = 25;			  // Size of our prime numbers		
       	BigInteger p1  = new BigInteger( "16" );  // Set 1st Prime to composite number number
       	BigInteger p2  = new BigInteger( "16" );  // Set 2nd Prime to composite number number
       	BigInteger n   = new BigInteger( "16" );  // Our Composite number (Set out to be even)
       	BigInteger i;
       	BigInteger L;                             // Upper limit       	
       	BigInteger r;
       	BigInteger t;
       	BigInteger s;
       	
       	// Generate a random odd composite number
       	while(n.mod(two).compareTo(one) !=0)
       	{
       		// generate a test value for p1
       		// 24 bits long, probably prime.
       		while(!p1.isProbablePrime(100))
       		{
       			p1 = new BigInteger( bitlength,  // size in bits //
                                	 100,    	 // 1 in 100 chance not prime //
                                	 random );
       		}
       		if(p1.isProbablePrime(100))
       			System.out.print("Prime           p1: " );
       		System.out.println( p1 +" " + p1.bitLength() +" bits long");
       		// generate a test value for p2
       		// 24 bits long, probably prime.
       		while(!p2.isProbablePrime(100))
       		{
       			bitlength -=2;
       			p2 = new BigInteger( bitlength,  // size in bits //
                                	 100,  		 // 1 in 100 chance not prime //
                                	 random );
       		}
       		if(p2.isProbablePrime(100))
       			System.out.print("Prime           p2: " );
       		System.out.println( p2 +" " + p2.bitLength() +" bits long");
       		// Create a composite number
       		// n = new BigInteger("5157437");
       		n = p1.multiply(p2);
       	}
        System.out.print("Composite Number n: ");
        System.out.println( n +" " + n.bitLength() +" bits long");
        // Find the square-root
        r = sqrt(n);

        // We could have been lucky and it was a perfect square
        if( (r.multiply(r)).compareTo(n) == 0)
        {
    		System.out.println( "We found a solution in 0 iterations");
        	System.out.print(n + " = " +r +" * " +r);        		
    		solved = true;        	
        }        
        // Is r^2 < n ? (We know it is as the sqrt function returns the floor)
        else if((r.multiply(r)).compareTo(n) < 0)
        {
        	// Make sure that r*r is larger than n       	
        	while( (r.multiply(r)).compareTo(n) < 0)
        		r = r.add(one);      		
        }
        System.out.print("The squareroot   r: " );
        System.out.println( r + " ");
 
        // Record the starting value 
        i = r; 
        // Set upper limit to (n+1)/2 - sqrt(n)
        L = ((n.add(one)).divide(two)).subtract(r);
        // Start solving we
        while(!solved && r.compareTo(L) < 0)
        {
        	t = r.multiply(r).subtract(n);
        	s = sqrt(t);
        	if(s.multiply(s).compareTo(t) !=0)
        		r = r.add(one);
        	else
        	{
        		System.out.println( "We found a solution in " +r.subtract(i) +" iterations");
        		t = r.subtract(s);
            	s = r.add(s);
            	System.out.print(n + " = " +t +" * " +s);        		
        		solved = true;        		
        	}
        		
        }
        // We found no factor between r and n
        if(!solved)
        	System.out.println("Unable to find a factorization with " +L +" iterations");        	
	}
	
	public static BigInteger sqrt(BigInteger x)
	{
	    BigInteger p, s, one, two;	    
		one = new BigInteger("1");
		two	= new BigInteger("2");	
		
	    p = x.divide(two);
	    s = (x.divide(p.pow(1))).add(p.multiply(two.subtract(one)));
	    s = s.divide(two);

	    while (p.compareTo(s) != 0 && one.compareTo(p.subtract(s)) !=0 )
	    {
	    	p = s;
	    	s = (x.divide(p.pow(1))).add(p.multiply(two.subtract(one)));
	    	s = s.divide(two);
	    }
	    // Was x a perfect square?
	    if( (s.multiply(s)).compareTo(x) == 0)
	    	return (s);
	    // Make sure that s is the floor of sqrt(x)
	    while( (s.multiply(s)).compareTo(x) < 0)
	    		s = s.add(one);
        s = s.subtract(one);
        return (s);
	}
}