// Written by Alan Davidson (adavidso@cs.hmc.edu), November 5, 2006

// Fast-ish program to factor large numbers. 
//
// In its current state, this program takes an integer from the command line,
// and generates two prime numbers of that bitlength. It then multiplies them
// together, and tries to factor the resulting number using a depth-first
// search technique: it starts by deciding on the most significant digit of
// each of the two factors it hopes to create. It then recursively tries making
// the most significant unknown bit of each number 0 and 1. It prunes any pair
// of factors whose minimum product is greater than the target or whose maximum
// product is less than the target number. 

// In this program, I use the following variables: 
//        target is the target number to be factored 
//        a and b are the minimum possible factors we're currently considering 
//        amax and bmax are the maximum possible factors we're considering
//        m and n are the most significant unknown bits of a and b 
//        tries is the number of times we've called checkAndContinue() so far

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

class factorizor{
  static void p(Object o){System.out.print(o);}
  static void pl(Object o){System.out.print("" + o + "\n");}

  static BigInteger pow(int p){return BigInteger.ONE.shiftLeft(p-1);} 
  static BigInteger tries;

  static void tryToFactor(BigInteger target, 
                          BigInteger a, BigInteger amax, int m,
                          BigInteger b, BigInteger bmax, int n) {
    if (m >= n) {  // If a has more unknown digits than b
      // Try making the next digit of a 1.
      checkAndContinue(target, a.add(pow(m)), amax, m-1, b, bmax, n);

      // Try making the next digit of a 0.
      checkAndContinue(target, a, amax.subtract(pow(m)), m-1, b, bmax, n);
    } else {  // If b has more unknown digits than a
      // Try making the next digit of b 1.
      checkAndContinue(target, a, amax, m, b.add(pow(n)), bmax, n-1);

      // Try making the next digit of b 0.
      checkAndContinue(target, a, amax, m, b, bmax.subtract(pow(n)), n-1); 
    }
  }

  static void checkAndContinue(BigInteger target, 
                               BigInteger a, BigInteger amax, int m, 
                               BigInteger b, BigInteger bmax, int n) {
    tries = tries.add(BigInteger.ONE);
    if (target.equals(a.multiply(b))) {
      pl("I found it!");
      pl(target + " = " + a + " * " + b);
      pl("This only took me " + tries + " tries.");
      System.exit(0);
    }
    if (target.equals(amax.multiply(bmax))) {
      pl("I found it!");
      pl(target + " = " + amax + " * " + bmax);
      pl("This only took me " + tries + " tries.");
      System.exit(0);
    }
    if (m == 0 && n == 0) {
      return;  // We'd be removing the final 1 that makes the number odd.
    }
    if (target.compareTo(a.multiply(b)) < 0) {
      return;  // The minimum product is already too large.
    }
    if (target.compareTo(amax.multiply(bmax)) > 0) {
      return;  // The maximum product we can get is too small.
    }
    tryToFactor(target, a, amax, m, b, bmax, n);
  }

  public static void main(String[] args) {
    try {
      // Setting up the two factors and the product.
      int bits = Integer.parseInt(args[0]);
      Random rand = new Random();
      BigInteger factorOne = BigInteger.probablePrime(bits, rand);
      BigInteger factorTwo = BigInteger.probablePrime(bits, rand);
      pl("First factor is " + factorOne);
      pl("Second Factor is " + factorTwo);
      BigInteger target = factorOne.multiply(factorTwo);
      pl("Their product is " + target);
      tries = BigInteger.ZERO;
      int newbits = target.bitLength();


      // I couldn't find a good way to figure out how many bits each of the
      // factors should start with (for instance, if the target number is, say,
      // 600, and the first factor is between 16 and 31, the second factor can
      // be either in the 16-31 range or the 32-63 range. 
      //
      // Instead of trying to figure out exactly which ranges of factors were
      // viable, I just try them all. The ones that aren't plausible are culled
      // immediately in the checkAndContinue function. 
      for (int i = 1; i < newbits; i = i + 1) {
        for (int j = 1; j <= i; j = j + 1) {
          BigInteger a = pow(i);
          BigInteger b = pow(j);
          BigInteger amax = a.shiftLeft(1).subtract(BigInteger.ONE);
          BigInteger bmax = b.shiftLeft(1).subtract(BigInteger.ONE);

          checkAndContinue(target, 
                           a.add(BigInteger.ONE), amax, a.bitLength()-1, 
                           b.add(BigInteger.ONE), bmax, b.bitLength()-1);
        }
      }

      pl("If we ever get here, there is no solution. Is it prime?");
      pl("We made " + tries + " tries to factor the number."); 

    } catch(Exception e) {e.printStackTrace();}
	}
}