smallfactors.java

factorization.zip

package javax.math.factorization;

/**
 * <p>Title: Factorization Library</p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2004</p>
 * <p>Company: </p>
 * @author Vladimir Silva
 * @version 1.0
 */
import java.math.BigInteger;

/**
 * Sorry about all this awful spagethi code :-<
 * I got it from: Dario Alejandro Alpern (Buenos Aires - Argentina)
 * Last updated October 16th, 2003. See http://www.alpertron.com.ar/ECM.HTM
 * I am not to blame for its crappy design and implementation, but....
 * what the hell. it works!
 * I modified it though, to make it less horrible (extracted the pieces i needed)
 * If you are a brave soul,  try to port this stuff to an object oriented, well-designed
 * structure. I tried, but just gave up....
 */
public class SmallFactors
{

      /**
       * all factors < 2^17
       */
  static long GetSmallFactors(BigInteger NumberToFactor, BigInteger PD[],
      int Exp[], int Typ[], int Type) {

    long Div,TestComp;
    int i;
    boolean checkExpParity = false;

    BigNumOps.BigNbrToBigInt(NumberToFactor);
    Factorizer.NbrFactors = 0;
    long[] TestNbr = Factorizer.TestNbr;

    for (i=0; i<400; i++) {
      Exp[i] = Typ[i] = 0;
    }
    while ((TestNbr[0] & 1) == 0) {         //
      if (Exp[Factorizer.NbrFactors] == 0) {
        PD[Factorizer.NbrFactors] = Constants.BigInt2;
      }
      Exp[Factorizer.NbrFactors]++;
      BigNumOps.DivBigNbrByLong(TestNbr,2,TestNbr);
    }
    if (Exp[Factorizer.NbrFactors] != 0) {Factorizer.NbrFactors++;}
    while (BigNumOps.RemDivBigNbrByLong(TestNbr,3)==0) {
      if (Type == 1) {
        checkExpParity = !checkExpParity;
      }
      if (Exp[Factorizer.NbrFactors] == 0) {
        PD[Factorizer.NbrFactors] = Constants.BigInt3;
      }
      Exp[Factorizer.NbrFactors]++;
      BigNumOps.DivBigNbrByLong(TestNbr,3,TestNbr);
    }
    if (checkExpParity) {
      return -1;                 // Discard it
    }
    if (Exp[Factorizer.NbrFactors] != 0) {Factorizer.NbrFactors++;}
    Div = 5;
    TestComp = TestNbr[0] + (TestNbr[1] << 32);
    if (TestComp < 0) {
      TestComp = 10000*Constants.DosALa32;
    }
    else {
      for (i=2; i< Factorizer.NumberLength; i++) {
        if (TestNbr[i] != 0) {
          TestComp = 10000*Constants.DosALa32;
          break;
        }
      }
    }
    while (Div < 131072) {
      if (Div%3 != 0) {
        while (BigNumOps.RemDivBigNbrByLong(TestNbr,Div)==0) {
          if (Type == 1 && Div%4 == 3) {
            checkExpParity = !checkExpParity;
          }
          if (Exp[Factorizer.NbrFactors] == 0) {
            PD[Factorizer.NbrFactors] = BigInteger.valueOf(Div);
          }
          Exp[Factorizer.NbrFactors]++;
          BigNumOps.DivBigNbrByLong(TestNbr,Div,TestNbr);
          TestComp = TestNbr[0] + (TestNbr[1] << 32);
          if (TestComp < 0) {
            TestComp = 10000*Constants.DosALa32;
          }
          else {
            for (i=2; i< Factorizer.NumberLength; i++) {
              if (TestNbr[i] != 0) {
                TestComp = 10000*Constants.DosALa32;
                break;
              }
            }
          }      // end while
        }
        if (checkExpParity) {
          return -1;                    // Discard it
        }
        if (Exp[Factorizer.NbrFactors] != 0) {Factorizer.NbrFactors++;}
      }
      Div += 2;
      if (TestComp < Div*Div && TestComp != 1) {
        if (Type == 1 && TestComp%4 == 3) {
          return -1;                 // Discard it
        }
        if (Exp[Factorizer.NbrFactors] != 0) {Factorizer.NbrFactors++;}
        PD[Factorizer.NbrFactors] = BigInteger.valueOf(TestComp);
        Exp[Factorizer.NbrFactors] = 1;
        TestComp = 1;
        Factorizer.NbrFactors++;
        break;
      }
    }
    return TestComp;
}


      /**
       *
       */
      public static void main(String[] args) {
	    //SmallFactors smallFactors1 = new SmallFactors();
      }

}