// Arup Guha
// 11/1/07
// Phollard-Rho Factoring Algorithm
// Edited on 10/25/2018 for Fall 2018 CIS 3362 Homework #5

import java.util.*;
import java.math.*;

public class FactoringHW5 {
	
	final public static BigInteger TWO = new BigInteger("2");
	
	// Test everything
	public static void main(String[] args) {
		long[] vals = {441075437627829133L, 733561193479131791L, 611217877192686991L, 1442059257386438303L, 3008502085141882717L};
		
		for (long x: vals) {
			fermat(""+x);
		}
	}

  	public static void pollardrho(String val) {
    
    	// Initial values of a and b in the algorithm.
    	BigInteger a = new BigInteger("2");
    	BigInteger b = new BigInteger("2");
    	BigInteger n = new BigInteger (val);
    	BigInteger d = null;
    	
    	// Start timer.
    	long start = System.currentTimeMillis();

		// Keep on going, we'll break out of the loop based on a couple
		// conditions.
    	while (true) {

      		// Operate on a once, and b twice.
      		a = (a.multiply(a).add(BigInteger.ONE)).mod(n);
      		b = (b.multiply(b).add(BigInteger.ONE)).mod(n);
      		b = (b.multiply(b).add(BigInteger.ONE)).mod(n);

      		// We want the gcd of the difference of a and b and d.
      		d = n.gcd(a.subtract(b));

			// We got lucky and found a factor!
      		if (!d.equals(BigInteger.ONE) && !d.equals(n))
        		break;

			// This means we won't ever find one in this manner.
      		if (d.equals(n))
        		break;
     	}
     	
     	long end = System.currentTimeMillis();

		// Output the appropriate message.
     	if (d.equals(n))
       		System.out.println("Test failed, couldn't factor.");
     	else
       		System.out.println(n+" = "+(d)+" * "+n.divide(d));
       		
       	System.out.println("Took "+(end-start)+" ms.");
  	}
  	
  	// Does Trial Division...
  	public static void trialdiv(long n) {
  		
  		long p1 = -1;
  		long start = System.currentTimeMillis();
  		
  		// Easy enough...just try dividing by each i.
  		for (long i=2; i*i<=n; i++) {
  			if (n%i == 0) {
  				p1 = i;
  				break;
  			}
  		}
  		long p2 = n/p1;
  		long end = System.currentTimeMillis();
  		System.out.println(n+" = "+p1+" * "+p2);
  		System.out.println("Took "+(end-start)+" ms.");
  		
  	}
  	
  	public static void fermat(String val) {
  		
  		BigInteger n = new BigInteger (val);
  		long start = System.currentTimeMillis();
  		
  		// Find our starting value.
  		BigInteger a = sqrtfloor(n).add(BigInteger.ONE);

  		BigInteger p1 = null, p2 = null;
  		while (true) {
  			
  			// See if the appropriate difference is a perfect square or not.
  			BigInteger asqr = a.multiply(a);
  			BigInteger bsqr = asqr.subtract(n);
  			BigInteger maybe = sqrtfloor(bsqr);
  			
  			// Here it is...
  			if (maybe.multiply(maybe).equals(bsqr)) {
  				p1 = a.add(maybe);
  				p2 = a.subtract(maybe);
  				break;
  			}
  			
  			// Go to the next value...
  			a = a.add(BigInteger.ONE);
  		}
  		long end = System.currentTimeMillis();
  		System.out.println(val+" = "+p1+" * "+p2);
  		System.out.println("Took "+(end-start)+" ms.");
  	}
  	
  	// Returns max x such that x*x <= n.
  	public static BigInteger sqrtfloor(BigInteger n) {
  		
  		BigInteger x = BigInteger.ONE;
  		
  		while (true) {
  		
  			// Forces x to converge towards the square root.
  			x = x.add(n.divide(x)).divide(TWO);
  			
  			// Got it.
  			if (x.multiply(x).compareTo(n) == 0) return x;
  			
  			// See if one higher is big enough.
  			else if (x.multiply(x).compareTo(n) < 0) {
  				BigInteger y = x.add(BigInteger.ONE);
  				if (y.multiply(y).compareTo(n) > 0)
  					return x;
  			}
  			
  			// See if one lower is small enough.
  			else {
  				BigInteger y = x.subtract(BigInteger.ONE);
  				if (y.multiply(y).compareTo(n) <= 0)
  					return y;
  			}
  		}
  		
  	}
}