bignumops.java

factorization.zip

		    Diff[i] = Cy & Constants.MaxUInt; //MaxUInt;
		    Cy >>= 32;
	      }
	}
  }

   static boolean BigNbrIsZero(long Nbr[]) {
	for (int i = 0; i < Factorizer.NumberLength; i++) {
	      if (Nbr[i] != 0) {
		    return false;
	      }
	}
	return true;
  }

   static boolean BigNbrAreEqual(long Nbr1[], long Nbr2[]) {
    for(int i=0; i< Factorizer.NumberLength ; i++) {
      if (Nbr1[i] != Nbr2[i]) {
        return false;
      }
    }
    return true;
  }


   static void JacobiSum(int A, int B, int P, int PK, int PL, int PM, int Q)
  {
	int I, J, K;
        int NumberLength = Factorizer.NumberLength; // x.getLength();

	for (I = 0; I < PL; I++) {
	      for (J = 0; J < NumberLength; J++) {
		    aiJ0[I][J] = 0;
	      }
	}
	for (I = 1; I <= Q - 2; I++) {
	      J = (A * I + B * aiF[I]) % PK;
	      if (J < PL) {
		    AddBigNbrModN(aiJ0[J], MontgomeryParams.MontgomeryMultR1, aiJ0[J]);
	      }
	      else {
		    for (K = 1; K < P; K++) {
			  SubtractBigNbrModN(aiJ0[J - K * PM],
					     MontgomeryParams.MontgomeryMultR1,
					     aiJ0[J - K * PM]);
		    }
	      }
	}
  }

  // Compare Nbr1^2 vs. Nbr2
  static int CompareSquare(long Nbr1[], long Nbr2[]) {
	int I, k;
        int NumberLength = Factorizer.NumberLength;

	for (I = NumberLength - 1; I > 0; I--) {
	      if (Nbr1[I] != 0) {
		    break;
	      }
	}
	k = NumberLength / 2;
	if (NumberLength % 2 == 0) {
	      if (I >= k) {
		    return 1;
	      } // Nbr1^2 > Nbr2
	      if (I < k - 1 || biS[k - 1] < 65536) {
		    return -1;
	      } // Nbr1^2 < Nbr2
	}
	else {
	      if (I < k) {
		    return -1;
	      } // Nbr1^2 < Nbr2
	      if (I > k || biS[k] >= 65536) {
		    return 1;
	      } // Nbr1^2 > Nbr2
	}
	MultBigNbr(biS, biS, biTmp);
	SubtractBigNbr(biTmp, Factorizer.TestNbr, biTmp);

	if (BigNbrIsZero(biTmp) == true) {
	      return 0;
	} // Nbr1^2 == Nbr2

	if (biTmp[NumberLength - 1] >= 0) {
	      return 1;
	} // Nbr1^2 > Nbr2
	return -1; // Nbr1^2 < Nbr2
  }

  // Perform JS <- JS ^ 2
   static void JS_2(int PK, int PL, int PM, int P) {
	int I, J, K;
        // MontgomeryParams params = new MontgomeryParams(mpx);
        MontgomeryParams.GetMontgomeryParams();

        int len = Factorizer.NumberLength;

	for (I = 0; I < PL; I++) {
	      K = 2 * I % PK;
	      //MontgomeryMult(aiJS[I], aiJS[I], biTmp);
              MontgomeryParams.MontgomeryMult(aiJS[I], aiJS[I], biTmp);

	      AddBigNbrModN(aiJX[K], biTmp, aiJX[K]);
	      AddBigNbrModN(aiJS[I], aiJS[I], biT);
	      for (J = I + 1; J < PL; J++) {
		    K = (I + J) % PK;
		    //MontgomeryMult(biT, aiJS[J], biTmp);
                    MontgomeryParams.MontgomeryMult(biT, aiJS[J], biTmp);
		    AddBigNbrModN(aiJX[K], biTmp, aiJX[K]);
	      }
	}
	for (I = 0; I < PK; I++) {
	      for (J = 0; J < len; J++) {
		    aiJS[I][J] = aiJX[I][J];
		    aiJX[I][J] = 0;
	      }
	}
	NormalizeJS(PK, PL, PM, P);
  }

  // Perform JS <- JS * JW
   static void JS_JW(int PK, int PL, int PM, int P ) {
    int I,J,K;
    int len = Factorizer.NumberLength;
    MontgomeryParams.GetMontgomeryParams();//

    for (I=0; I<PL; I++) {
      for (J=0; J<PL; J++) {
        K = (I+J)%PK;
        // MontgomeryMult(aiJS[I], aiJW[J], biTmp);
        MontgomeryParams.MontgomeryMult(aiJS[I], aiJW[J], biTmp);
        AddBigNbrModN(aiJX[K], biTmp, aiJX[K]);
      }
    }
    for (I=0; I<PK; I++) {
      for (J=0; J<len; J++) {
        aiJS[I][J] = aiJX[I][J];
        aiJX[I][J] = 0;
      }
    }
    NormalizeJS(PK, PL, PM, P);
  }

  // Perform JS <- JS ^ E
   static void JS_E(int PK, int PL, int PM, int P) {
    int I, J, K;
    long Mask;
    int NumberLength = Factorizer.NumberLength;

    for (I=NumberLength-1; I>0; I--) {
      if (biExp[I] != 0) {break;}
    }
    if (I == 0 && biExp[0] == 1) {return;}   // Return if E == 1
    for (K=0; K<PL; K++) {
      for (J=0; J<NumberLength; J++) {
        aiJW[K][J] = aiJS[K][J];
      }
    }
    Mask = Constants.DosALa31;
    while (true) {
      if ((biExp[I] & Mask) != 0) {break;}
      Mask /= 2;
    }
    do {
      JS_2(PK, PL, PM, P);
      Mask /= 2;
      if (Mask == 0) {
        Mask = Constants.DosALa31;
        I--;
      }
      if ((biExp[I] & Mask) != 0) {
        JS_JW(PK, PL, PM, P);
      }
    } while (I>0 || Mask != 1);
  }

  // Normalize coefficient of JW
  static  void NormalizeJW(int PK, int PL, int PM, int P) {
    int I,J;
    int NumberLength = Factorizer.NumberLength;

    for (I=PL; I<PK; I++) {
      if (BigNbrIsZero(aiJW[I]) == false) {
        for (J=0; J<NumberLength; J++) {
          biT[J] = aiJW[I][J];
        }
        for (J=1; J<P; J++) {
          SubtractBigNbrModN(aiJW[I-J*PM], biT, aiJW[I-J*PM]);
        }
        for (J=0; J<NumberLength; J++) {
          aiJW[I][J] = 0;
        }
      }
    }
  }

  // Normalize coefficient of JS
   static void NormalizeJS(int PK, int PL, int PM, int P) {
	int I, J;
        int len = Factorizer.NumberLength;

	for (I = PL; I < PK; I++) {
	      if (BigNbrIsZero(aiJS[I]) == false) {
		    for (J = 0; J < len; J++) {
			  biT[J] = aiJS[I][J];
		    }
		    for (J = 1; J < P; J++) {
			  SubtractBigNbrModN(aiJS[I - J * PM], biT,
					     aiJS[I - J * PM]);
		    }
		    for (J = 0; J < len; J++) {
			  aiJS[I][J] = 0;
		    }
	      }
	}
  }

static    void LongToBigNbr(long Nbr, long Out[]) {
    int i;

    Out[0] = Nbr & Constants.MaxUInt; // MaxUInt;
    Out[1] = Nbr >>> 32;
    for (i=2; i< Factorizer.NumberLength; i++) {
      Out[i] = (Nbr<0? Constants.MaxUInt: 0);
    }
  }

  static long RemDivBigNbrByLong(long Dividend[], long Divisor) {
    int i;
    long Divid, Rem = 0;
    int len = Factorizer.NumberLength;

    if (Divisor < 0) {
      Divisor = -Divisor;
    }
    if (Dividend[len-1] >= Constants.DosALa31) {
      Rem = Divisor - 1;
    }
    for (i=len-1; i>=0; i--) {
      Divid = Dividend[i] + (Rem << 32);
      Rem = Divid % Divisor;
    }
    return Rem;
  }

  static long modPow(long NbrMod, long Expon, long currentPrime) {
    long Power = 1;
    long Square = NbrMod;
    while (Expon != 0) {
      if ((Expon & 1) == 1) {
        Power = (Power * Square) % currentPrime;
      }
      Square = (Square * Square) % currentPrime;
      Expon /= 2;
    }
    return Power;
  }

  static  long modInv(long NbrMod, long currentPrime) {
    long QQ, T1, T3;
    long U1 = 1;
    long U3 = NbrMod;
    long V1 = 0;
    long V3 = currentPrime;
    while (V3 != 0) {
      QQ = U3/V3;
      T1 = U1 - V1*QQ;
      T3 = U3 - V3*QQ;
      U1 = V1; U3 = V3;
      V1 = T1; V3 = T3;
    }
    return (U1+currentPrime)%currentPrime;
  }

  static BigInteger BigIntToBigNbr(long [] GD) {
    byte [] Result;
    int I;
    int NL;
    int len= Factorizer.NumberLength;

    NL = len*4;
    Result = new byte[NL];
    for (I=0;I<len;I++) {
      Result[NL-1-4*I] = (byte)(GD[I] & 0xFF);
      Result[NL-2-4*I] = (byte)(GD[I]/0x100 & 0xFF);
      Result[NL-3-4*I] = (byte)(GD[I]/0x10000 & 0xFF);
      Result[NL-4-4*I] = (byte)(GD[I]/0x1000000 & 0xFF);
    }
    return (new BigInteger(Result));
  }


}