bignumops.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;

/**
 * I am truly 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 BigNumOps implements Constants
{

  static void BigNbrToBigInt(BigInteger N) {
    byte [] Result;
    int I,J;
    long K,P;

    Result = N.toByteArray();
    Factorizer.NumberLength = (Result.length+3)/4;

    Factorizer.yieldFreq = 1000000/(Factorizer.NumberLength* Factorizer.NumberLength);

    if (Factorizer.yieldFreq > 100000) Factorizer.yieldFreq = Factorizer.yieldFreq / 100000 * 100000;
    else if (Factorizer.yieldFreq > 10000) Factorizer.yieldFreq = Factorizer.yieldFreq / 10000 * 10000;
    else if (Factorizer.yieldFreq > 1000) Factorizer.yieldFreq = Factorizer.yieldFreq / 1000 * 1000;
    else if (Factorizer.yieldFreq > 100) Factorizer.yieldFreq = Factorizer.yieldFreq / 100 * 100;
    J = 0;
    K = 1;
    P = 0;
    for (I=Result.length-1; I>=0; I--) {
      P += K*(long)(Result[I]>=0?Result[I]:Result[I]+256);
      K *= 0x100;
      if (K == Constants.DosALa32) {
        Factorizer.TestNbr[J] = P;
        J++;
        K = 1;
        P = 0;
      }
    }
    Factorizer.TestNbr[J] = P;
    if (Factorizer.TestNbr[Factorizer.NumberLength-1] > Constants.Mi) {
      Factorizer.TestNbr[Factorizer.NumberLength] = 0;
      Factorizer.NumberLength++;
    }
    Factorizer.TestNbr[Factorizer.NumberLength] = 0;
  }

      static void ChSignBigNbr(long Nbr[]) {
	    int NumberLength = Factorizer.NumberLength;
	    long Cy = 0;
	    for (int i = 0; i < NumberLength; i++) {
		  Cy -= Nbr[i];
		  Nbr[i] = (Cy >= 0 ? Cy : Cy + Constants.DosALa32);
		  Cy = (Cy >= 0 ? 0 : -1);
	    }
      }

      static void AdjustModN(long Nbr[]) {
	    int _length = Factorizer.NumberLength;
	    long TrialQuotient;
	    long Cy;
	    int i;
	    double dAux;

	    dAux = (double) Nbr[_length] * Constants.dDosALa32 + (double) Nbr[_length - 1];
	    if (_length > 1) {
		  dAux += (double) Nbr[_length - 2] / Constants.dDosALa32; //DMAX_WORD;
	    }
	    TrialQuotient = (long) Math.ceil(dAux / Factorizer.dN) + 2;
	    if (TrialQuotient >= Constants.dDosALa32) { //MAX_WORD) {
		  Cy = 0;
		  for (i = 0; i < _length; i++) {
			Cy = Nbr[i + 1] - (TrialQuotient >>> 32) * Factorizer.TestNbr[i] - Cy;
			Nbr[i + 1] = Cy & Constants.MaxUInt;
			Cy = (Constants.MaxUInt - Cy) >>> 32;
		  }
		  TrialQuotient &= Constants.MaxUInt;
	    }
            Cy = 0;
	    for (i = 0; i < _length; i++) {
		  Cy = Nbr[i] - TrialQuotient * Factorizer.TestNbr[i] - Cy;
		  Nbr[i] = Cy & Constants.MaxUInt;
		  Cy = (Constants.MaxUInt - Cy) >>> 32;
	    }
	    Nbr[_length] -= Cy;
	    while ( (Nbr[_length] & Constants.MaxUInt) != 0) {
		  Cy = 0;
		  for (i = 0; i < _length; i++) {
			Cy += Nbr[i] + Factorizer.TestNbr[i];
			Nbr[i] = Cy & Constants.MaxUInt;
			Cy >>= 32;
		  }
		  Nbr[_length] += Cy;
	    }
      }

  // debug
  static void AddBigNbr(long Nbr1[], long Nbr2[], long Sum[]) {
	long Cy = 0;
	for (int i = 0; i < Factorizer.NumberLength; i++) {
	      Cy += Nbr1[i] + Nbr2[i];
	      Sum[i] = Cy & Constants.MaxUInt; // MaxUInt;
	      Cy >>= 32;
	}
  }


      static void MultBigNbrModN(long Nbr1[], long Nbr2[], long Prod[])
      {
	    int _length = Factorizer.NumberLength;
	    int i, j;
	    long Pr, Nbr;

	    i = _length;
	    do {
                  Prod[--i] = 0;
	    }
	    while (i > 0);

	    i = _length;
	    do {
		  Nbr = Nbr1[--i];
		  j = _length;
		  do {
			Prod[j] = Prod[j - 1];
			j--;
		  }
                  while (j > 0);
		  Prod[0] = 0;
		  Pr = 0;
		  for (j = 0; j < _length; j++) {
			Pr = (Pr >>> 32) + Nbr * Nbr2[j] + Prod[j];
			Prod[j] = Pr & Constants.MaxUInt;
		  }
		  Prod[j] += (Pr >>> 32);

		  AdjustModN(Prod);
	    }
	    while (i > 0);
      }

  static void AddBigNbrModN(long Nbr1[], long Nbr2[], long Sum[]) {
//        int NumberLength = mpx.getLength();
        long[] TestNbr = Factorizer.TestNbr;
	long Cy = 0;
	int i;

	for (i = 0; i < Factorizer.NumberLength; i++) {
	      Cy += Nbr1[i] + Nbr2[i] - TestNbr[i];
	      Sum[i] = Cy & Constants.MaxUInt; // MaxUInt;
	      Cy >>= 32;
	}
	if (Cy < 0) {
	      Cy = 0;
	      for (i = 0; i < Factorizer.NumberLength; i++) {
		    Cy += Sum[i] + TestNbr[i];
		    Sum[i] = Cy & Constants.MaxUInt; //MaxUInt;
		    Cy >>= 32;
	      }
	}
  }

   static void BigNbrModN(long Nbr[], int Length, long Mod[]) {
    int i,j;
    int len = Factorizer.NumberLength;

    for (i=0; i<len; i++) {
      Mod[i] = Nbr[i + Length - len];
    }
    Mod[i] = 0;
    //AdjustModN(Mod);
    AdjustModN(Mod);

    for (i=Length - len - 1; i>=0; i--) {
      for (j=len; j>0; j--) {
        Mod[j] = Mod[j-1];
      }
      Mod[0] = Nbr[i];
      //AdjustModN(Mod);
      AdjustModN(Mod);
    }
  }

   static long BigNbrModLong(long Nbr1[], long Nbr2) {
	int i;
	long Rem = 0;

	for (i = Factorizer.NumberLength - 1; i >= 0; i--) {
	      Rem = ( (Rem << 32) + Nbr1[i]) % Nbr2;
	}
	return Rem;
  }

   static void MultBigNbr(long Nbr1[], long Nbr2[], long Prod[]) {
	long Cy, Pr;
	int i, j;
	Cy = Pr = 0;
	for (i = 0; i < Factorizer.NumberLength; i++) {
	      Pr = Cy & Constants.MaxUInt; // MaxUInt;
	      Cy >>>= 32;
	      for (j = 0; j <= i; j++) {
		    Pr += Nbr1[j] * Nbr2[i - j];
		    Cy += (Pr >>> 32);
		    Pr &= Constants.MaxUInt;
	      }
	      Prod[i] = Pr;
	}
  }

   static void MultBigNbrByLong(long Nbr1[], long Nbr2, long Prod[]) {
	long Cy, Pr;
	int i, j;
        Cy = 0;
	for (i = 0; i < Factorizer.NumberLength; i++) {
	      Pr = (Cy & Constants.MaxUInt) + Nbr2 * Nbr1[i];
	      Cy = (Cy >>> 32) + (Pr >>> 32);
	      Prod[i] = Pr & Constants.MaxUInt;
	}
  }

   static void MultBigNbrByLongModN(long Nbr1[], long Nbr2, long Prod[]) { //int NumberLength) {
	long Pr;
	int j;
        int len = Factorizer.NumberLength;

        Pr = 0;
	for (j = 0; j < len; j++) {
	      Pr = (Pr >>> 32) + Nbr2 * Nbr1[j];
	      Prod[j] = Pr & Constants.MaxUInt; // MaxUInt;
	}
	Prod[j] = (Pr >>> 32);
        AdjustModN(Prod);
  }

   static void DivBigNbrByLong(long Dividend[], long Divisor, long Quotient[]) {
    int i;
    boolean ChSignDivisor=false;
    long Divid, Rem = 0;

    if (Divisor < 0) {
      ChSignDivisor = true;
      Divisor = -Divisor;
    }
    if (Dividend[Factorizer.NumberLength-1] >= Constants.DosALa31) {
      Rem = Divisor - 1;
    }
    for (i=Factorizer.NumberLength-1; i>=0; i--) {
      Divid = Dividend[i] + (Rem << 32);
      Rem = Divid % Divisor;
      Quotient[i] = Divid / Divisor;
    }
    if (ChSignDivisor) {
      ChSignBigNbr(Quotient);
    }
  }

   static void SubtractBigNbr(long Nbr1[], long Nbr2[], long Diff[]) {
	long Cy = 0;
	for (int i = 0; i < Factorizer.NumberLength; i++) {
	      Cy += Nbr1[i] - Nbr2[i];
	      Diff[i] = Cy & Constants.MaxUInt; // MaxUInt;
	      Cy >>= 32;
	}
  }

   static void SubtractBigNbrModN(long Nbr1[], long Nbr2[], long Diff[]) {
        long[] TestNbr = Factorizer.TestNbr;
        int len = Factorizer.NumberLength;
	long Cy = 0;
	int i;

	for (i = 0; i < len; i++) {
	      Cy += Nbr1[i] - Nbr2[i];
	      Diff[i] = Cy & Constants.MaxUInt; // MaxUInt;
	      Cy >>= 32;
	}
	if (Cy < 0) {
	      Cy = 0;
	      for (i = 0; i < len; i++) {
		    Cy += Diff[i] + TestNbr[i];