//
Escrito por Darío Alejandro Alpern (alpertron@hotmail.com)
");
text.append(upperTextArea.getText());
text.append("
");
text.append(lower);
if (lower.indexOf("completa") < 0)
{
final long New = System.currentTimeMillis();
if (OldTimeElapsed >= 0)
{
OldTimeElapsed += New - Old;
Old = New;
text.append("
Tiempo transcurrido: ");
text.append(GetDHMS(OldTimeElapsed / 1000));
if (lModularMult >= 0)
{
text.append("\nSe realizaron ");
text.append(lModularMult);
text.append(" multiplicaciones modulares");
}
}
}
text.append("
");
return text.toString();
}
else
{
return null;
}
}
String GetDHMS(final long time)
{
return time / 86400 + "d " + (time % 86400) / 3600 + "h " +
((time % 3600) / 60) + "m " + (time % 60) + "s";
}
String GetDHMSd(final long time)
{
return time / 864000 + "d " + (time % 864000) / 36000 + "h " +
((time % 36000) / 600) + "m " + ((time % 600)/10)+"."+
(time%10) + "s";
}
void addStringToLabel(String value)
{
if (value.length() + 1 + StringToLabel.length() >= 79)
{
textAreaContents += StringToLabel + "\n";
StringToLabel = value + " ";
}
else
{
StringToLabel += value + " ";
}
}
void ShowUpperPane()
{
int i;
textAreaContents = "";
StringToLabel = "";
insertBigNbr(NumberToFactor);
if (NbrFactors == 1 && Exp[0] == 1)
{
if (Typ[0] > 0)
{
addStringToLabel("es compuesto");
}
else
{
if (Typ[0] < 0)
{
addStringToLabel("es desconocido");
}
else
{
addStringToLabel("es primo");
}
}
}
else
{
addStringToLabel("=");
for (i = 0; i < NbrFactors; i++)
{
if (i != 0)
{
addStringToLabel("x");
}
insertBigNbr(PD[i]);
if (Exp[i] != 1)
{
addStringToLabel("^");
addStringToLabel(String.valueOf(Exp[i]));
}
if (Typ[i] > 0)
{
if ((digitsInGroup & 0x800) == 0x800)
{
if (Typ[i] == TYP_AURIF)
{
addStringToLabel("(Aurifeuille)");
}
else if (Typ[i] / 50000000 * 50000000 == TYP_AURIF)
{
addStringToLabel("(Aurif - Compuesto)");
}
else if (Typ[i] == TYP_TABLE)
{
addStringToLabel("(Tabla)");
}
else if (Typ[i] / 50000000 * 50000000 == TYP_TABLE)
{
addStringToLabel("(Tabla - Compuesto)");
}
else if (Typ[i] == TYP_SIQS)
{
addStringToLabel("(SIQS)");
}
else if (Typ[i] / 50000000 * 50000000 == TYP_SIQS)
{
addStringToLabel("(SIQS - Compuesto)");
}
else if (Typ[i] == TYP_LEHMAN)
{
addStringToLabel("(Lehman)");
}
else if (Typ[i] / 50000000 * 50000000 == TYP_LEHMAN)
{
addStringToLabel("(Lehman - Compuesto)");
}
else if (Typ[i] > TYP_EC)
{
addStringToLabel("(Curva " + (Typ[i] - TYP_EC) + ")");
}
else
{
addStringToLabel("(Compuesto)");
}
}
else if (
Typ[i] < TYP_EC
&& Typ[i] != TYP_LEHMAN
&& Typ[i] != TYP_SIQS
&& Typ[i] != TYP_AURIF
&& Typ[i] != TYP_TABLE)
{
addStringToLabel("(Compuesto)");
}
}
else
{
if (Typ[i] < 0)
{
addStringToLabel("(Desconocido)");
}
}
}
}
upperTextArea.setText(textAreaContents + StringToLabel);
}
void insertBigNbr(final BigInteger N)
{
int i, dig;
dig = digitsInGroup & 0x3FF;
final String value = N.toString();
i = (value.length() + dig - 1) % dig + 1;
addStringToLabel(value.substring(0, i));
while (i < value.length())
{
addStringToLabel(value.substring(i, i + dig));
i += dig;
}
}
void InsertNewFactor(final BigInteger InputFactor)
{
int g,exp;
/* Insert input factor */
for (g = NbrFactors - 1; g >= 0; g--)
{
PD[NbrFactors] = PD[g].gcd(InputFactor);
if (PD[NbrFactors].equals(BigInt1) || PD[NbrFactors].equals(PD[g]))
{
continue;
}
for (exp=0; PD[g].remainder(PD[NbrFactors]).signum() == 0; exp++)
{
PD[g] = PD[g].divide(PD[NbrFactors]);
}
Exp[NbrFactors] = Exp[g] * exp;
if (Typ[g] < 100000000)
{
Typ[g] = -EC;
Typ[NbrFactors] = -TYP_EC - EC;
}
else if (Typ[g] < 150000000)
{
Typ[NbrFactors] = -Typ[g];
Typ[g] = TYP_AURIF - Typ[g];
}
else if (Typ[g] < 200000000)
{
Typ[NbrFactors] = -Typ[g];
Typ[g] = TYP_TABLE - Typ[g];
}
else if (Typ[g] < 250000000)
{
Typ[NbrFactors] = -Typ[g];
Typ[g] = TYP_SIQS - Typ[g];
}
else
{
Typ[NbrFactors] = -Typ[g];
Typ[g] = TYP_LEHMAN - Typ[g];
}
NbrFactors++;
}
SortFactorsInputNbr();
}
void SortFactorsInputNbr()
{
int g, i, j;
BigInteger Nbr1;
for (g = 0; g < NbrFactors - 1; g++)
{
for (j = g + 1; j < NbrFactors; j++)
{
if (PD[g].compareTo(PD[j]) > 0)
{
Nbr1 = PD[g];
PD[g] = PD[j];
PD[j] = Nbr1;
i = Exp[g];
Exp[g] = Exp[j];
Exp[j] = i;
i = Typ[g];
Typ[g] = Typ[j];
Typ[j] = i;
}
}
}
}
void startNewFactorization(final boolean completefactorization)
{
if (calcThread != null && batchFinished)
{
TerminateThread = true;
try
{
calcThread.join(); /* Wait until the factorization thread dies */
}
catch (InterruptedException ie)
{
}
}
onlyFactoring = completefactorization ^ true;
lModularMult = OldTimeElapsed = NbrFactors = EC = 0;
if (completefactorization)
{
factorize();
}
else
{
calcThread = new Thread(this); /* Start factorization thread */
calcThread.start();
}
}
public void run()
{
if (!batchFinished)
{
BatchThread();
return;
}
polynomialsSieved = 0;
trialDivisions = 0;
smoothsFound = 0;
totalPartials = 0;
partialsFound = 0;
factorize();
}
void factorize()
{
BigInteger NN;
long TestComp, New;
BigInteger N1, N2, Tmp;
int i, j;
int ExpressionRC;
final BigInteger ExpressionResult[] = new BigInteger[1];
timePrimalityTests = 0; // Reset to zero all timings.
timeSIQS = 0;
timeECM = 0;
nbrPrimalityTests = 0; // Reset to zero all counters.
nbrSIQS = 0;
nbrECM = 0;
StepECM = 0;
primeModMult = 0;
Computing3Squares = false;
TerminateThread = false;
Old = System.currentTimeMillis();
if (onlyFactoring)
{
if (NbrFactors == 0)
{
lowerTextArea.setText("Calculando expresión de entrada...");
try
{
ExpressionRC =
expression.ComputeExpression(
textNumber.getText().trim(),
0,
ExpressionResult);
}
catch (OutOfMemoryError e)
{
lowerTextArea.setText("Sin memoria.");
return;
}
catch (ArithmeticException e)
{
return;
}
NumberToFactor = ExpressionResult[0];
if (ExpressionRC != 0)
{
lowerTextArea.setText(expressionText[-1 - ExpressionRC]);
return;
}
}
}
else
{
if (NbrFactors == 0)
{
NumberToFactor = new BigInteger(textNumber.getText().trim());
}
}
BigNbr1[0] = 1;
for (i = 1; i < NLen; i++)
{
BigNbr1[i] = 0;
}
try
{
if (NbrFactors == 0)
{
lowerTextArea.setText(
"Buscando factores pequeños (menores que 131072).");
TestComp = GetSmallFactors(NumberToFactor, PD, Exp, Typ, 0);
if (TestComp != 1)
{ // There are factors greater than 131071.
PD[NbrFactors] = BigIntToBigNbr(TestNbr);
Exp[NbrFactors] = 1;
Typ[NbrFactors] = -1; /* Unknown */
NbrFactors++;
ShowUpperPane();
if (batchFinished || !batchPrime)
{
lowerTextArea.setText("Buscando potencias perfectas más/menos 1.");
PowerPM1Check(); /* Find algebraic and Aurifeuillian factors */
lowerTextArea.setText("Buscando números de Lucas.");
LucasCheck();
lowerTextArea.setText("Buscando números de Fibonacci.");
FibonacciCheck();
}
}
}
performLehman = true;
factor_loop : for (;;)
{
ShowUpperPane();
for (i = 0; i < NbrFactors; i++)
{
if (Typ[i] < 0)
{ /* Unknown */
lowerTextArea.setText("Buscando potencias perfectas.");
if (PowerCheck(i) != 0)
{
SortFactorsInputNbr();
continue factor_loop;
}
if (PD[i].bitLength() <= 33)
{
j = 0;
}
else
{
lowerTextArea.setText("Antes de llamar a la rutina de verificación de numeros primos");
final long oldModularMult = lModularMult;
timePrimalityTests -= System.currentTimeMillis();
j = AprtCle(PD[i]);
timePrimalityTests += System.currentTimeMillis();
nbrPrimalityTests++;
primeModMult += lModularMult - oldModularMult;
if (!batchFinished && batchPrime)
{
NbrFactors = j;
return;
}
}
if (j == 0)
{
if (Typ[i] < -TYP_EC)
{
Typ[i] = -Typ[i]; /* Prime */
}
else if (Typ[i] < -TYP_LEHMAN)
{
Typ[i] = TYP_LEHMAN; /* Prime */
}
else if (Typ[i] < -TYP_SIQS)
{
Typ[i] = TYP_SIQS; /* Prime */
}
else if (Typ[i] < -TYP_AURIF)
{
Typ[i] = TYP_AURIF; /* Prime */
}
else
{
Typ[i] = 0; /* Prime */
}
}
else
{
if (Typ[i] < -TYP_EC)
{
Typ[i] = -TYP_EC - Typ[i]; /* Composite */
}
else
{
Typ[i] = -Typ[i]; /* Composite */
}
}
continue factor_loop;
}
}
for (i = 0; i < NbrFactors; i++)
{
EC = Typ[i];
if (EC > 0 && EC < TYP_EC && EC != TYP_AURIF
&& EC != TYP_SIQS && EC != TYP_LEHMAN)
{ /* Composite */
EC %= 50000000;
timeECM -= System.currentTimeMillis();
NN = fnECM(PD[i], i);
timeECM += System.currentTimeMillis();
nbrECM++;
if (NN.equals(BigInt1))
{
timeSIQS -= System.currentTimeMillis();
NN = FactoringSIQS(PD[i]);
timeSIQS += System.currentTimeMillis();
nbrSIQS++;
}
if (foundByLehman)
{ // Factor found using Lehman method
Typ[i] = TYP_LEHMAN + EC + 1;
}
else
{
Typ[i] = EC;
}
InsertNewFactor(NN);
continue factor_loop;
}
}
break;
}
if (onlyFactoring)
{
textAreaContents = upperTextArea.getText() + "\n\n";
StringToLabel = ""; // Start new line.
addStringToLabel("Cantidad de divisores: ");
N1 = BigInt1;
for (i = 0; i < NbrFactors; i++)
{
N1 = N1.multiply(BigInteger.valueOf(Exp[i] + 1));
}
insertBigNbr(N1); // Show number of divisors.
textAreaContents += StringToLabel + "\n\n";
StringToLabel = ""; // Start new line.
addStringToLabel("Suma de divisores: ");
N1 = BigInt1;
for (i = 0; i < NbrFactors; i++)
{
N1 =
N1.multiply(PD[i].pow(Exp[i] + 1).subtract(BigInt1)).divide(
PD[i].subtract(BigInt1));
}
insertBigNbr(N1); // Show sum of divisors.
textAreaContents += StringToLabel + "\n\n";
StringToLabel = ""; // Start new line.
addStringToLabel("Indicador de Euler: ");
N1 = NumberToFactor;
for (i = 0; i < NbrFactors; i++)
{
N1 = N1.multiply(PD[i].subtract(BigInt1)).divide(PD[i]);
}
insertBigNbr(N1);
j = 1; // Compute Moebius
for (i = 0; i < NbrFactors; i++)
{
if (Exp[i] == 1)
{
j = -j;
}
else
{
j = 0;
}
} // Show Euler's totient and Moebius
textAreaContents += StringToLabel + "\n\nMoebius: " + j;
StringToLabel = "\n\nSuma de cuadrados: "; // Start new line.
ComputeFourSquares(PD, Exp); // Quad1^2 + Quad2^2 + Quad3^2 + Quad4^2
NbrFactors1 = NbrFactors;
if (Quad4.signum() != 0)
{ // Check if four squares are really needed.
j = NumberToFactor.getLowestSetBit();
if (j % 2 != 0
|| !NumberToFactor.shiftRight(j).and(BigInteger.valueOf(7)).equals(
BigInteger.valueOf(7)))
{
/* Only three squares are required here */
Computing3Squares = true;
j = j / 2;
lowerTextArea.setText("Calculando suma de tres cuadrados perfectos...");
for (N1 = BigInt1.shiftLeft(j);; N1 = N1.add(BigInt1.shiftLeft(j)))
{
if (TerminateThread)
{
throw new ArithmeticException();
}
New = System.currentTimeMillis();
if (OldTimeElapsed >= 0
&& OldTimeElapsed / 1000 != (OldTimeElapsed + New - Old) / 1000)
{
OldTimeElapsed += New - Old;
Old = New;
labelStatus.setText(
"Transcurrió: "
+ GetDHMS(OldTimeElapsed / 1000)
+ " mult mod: "
+ (lModularMult >= 0 ? "" + lModularMult : "No lo sé"));
}
N2 = NumberToFactor.subtract(N1.multiply(N1));
TestComp = GetSmallFactors(N2, PD1, Exp1, Typ1, 1);
if (TestComp >= 0)
{
if (TestComp == 1)
{ // Number has all factors < 2^17
ComputeFourSquares(PD1, Exp1); // Quad1^2 + Quad2^2
break;
}
if (TestNbr[0] % 4 == 3)
{
continue;
} // This value of c does not work
PD1[NbrFactors] = BigIntToBigNbr(TestNbr);
Exp1[NbrFactors] = 1;
NbrFactors++;
if (ComputeFourSquares(PD1, Exp1))
{ // Quad1^2 + Quad2^2
break;
}
}
} /* end for */
Quad3 = N1;
// Sort squares (only Quad3 can be out of order).
if (Quad1.compareTo(Quad3) < 0)
{
Tmp = Quad1;
Quad1 = Quad3;
Quad3 = Tmp;
}
if (Quad2.compareTo(Quad3) < 0)
{
Tmp = Quad2;
Quad2 = Quad3;
Quad3 = Tmp;
}
Computing3Squares = false;
}
}
NbrFactors = NbrFactors1;
if (Quad4.signum() == 0)
{
if (Quad3.signum() == 0)
{
if (Quad2.signum() == 0)
{
insertBigNbr(Quad1);
addStringToLabel("^2");
}
else
{
textAreaContents += StringToLabel + "a^2 + b^2\n";
StringToLabel = "a = "; // Start new line.
insertBigNbr(Quad1);
textAreaContents += StringToLabel + "\n";
StringToLabel = "b = "; // Start new line.
insertBigNbr(Quad2);
}
}
else
{
textAreaContents += StringToLabel + "a^2 + b^2 + c^2\n";
StringToLabel = "a = "; // Start new line.
insertBigNbr(Quad1);
textAreaContents += StringToLabel + "\n";
StringToLabel = "b = "; // Start new line.
insertBigNbr(Quad2);
textAreaContents += StringToLabel + "\n";
StringToLabel = "c = "; // Start new line.
insertBigNbr(Quad3);
}
}
else
{
textAreaContents += StringToLabel + "a^2 + b^2 + c^2 + d^2\n";
StringToLabel = "a = "; // Start new line.
insertBigNbr(Quad1);
textAreaContents += StringToLabel + "\n";
StringToLabel = "b = "; // Start new line.
insertBigNbr(Quad2);
textAreaContents += StringToLabel + "\n";
StringToLabel = "c = "; // Start new line.
insertBigNbr(Quad3);
textAreaContents += StringToLabel + "\n";
StringToLabel = "d = "; // Start new line.
insertBigNbr(Quad4);
}
upperTextArea.setText(textAreaContents + StringToLabel);
New = System.currentTimeMillis();
if (OldTimeElapsed >= 0)
{
OldTimeElapsed += New - Old;
final String timeElapsed = GetDHMS(OldTimeElapsed / 1000);
String textAreaInfo = "Factorización completada en " + timeElapsed;
if (lModularMult >= 0)
{
textAreaInfo += "\nECM: "
+ (lModularMult - primeModMult)
+ " multiplicaciones modulares\nVerificación de primos: "
+ primeModMult
+ " multiplicaciones modulares";
}
if (smoothsFound > 0)
{
textAreaInfo += "\nSIQS: "
+ polynomialsSieved
+ " polinomios utilizados\n "
+ trialDivisions
+ " conjuntos de divisiones de prueba\n "
+ smoothsFound
+ " congruencias completas (1 de cada "
+ ValuesSieved/smoothsFound+" valores)\n "
+ totalPartials
+ " congruencias parciales (1 de cada "
+ ValuesSieved/totalPartials+" valores)\n "
+ partialsFound
+ " congruencias parciales útiles.";
}
if (nbrSIQS > 0 || nbrECM > 0 || nbrPrimalityTests > 0)
{
textAreaInfo += "\n\nTiempos:";
if (nbrPrimalityTests > 0)
{
textAreaInfo += "\nTest de primalidad de "+nbrPrimalityTests+
" número"+(nbrPrimalityTests!=1?"s":"")+
": " + GetDHMSd(timePrimalityTests/100);
}
if (nbrECM > 0)
{
textAreaInfo += "\nFactorización de "+nbrECM+
" número"+(nbrECM!=1?"s":"")+
" usando ECM: " + GetDHMSd(timeECM/100);
}
if (nbrSIQS > 0)
{
textAreaInfo += "\nFactorización de "+nbrSIQS+
" número"+(nbrSIQS!=1?"s":"")+
" usando SIQS: " + GetDHMSd(timeSIQS/100);
}
}
lowerTextArea.setText(textAreaInfo);
labelStatus.setText(
"Transcurrió: "
+ timeElapsed
+ " mult mod: "
+ (lModularMult >= 0 ? "" + lModularMult : "No lo sé"));
}
else
{
lowerTextArea.setText("Factorización completa");
}
NextEC = -1; /* First curve of new number should be 1 */
}
}
catch (ArithmeticException e)
{
New = System.currentTimeMillis();
if (OldTimeElapsed >= 0)
{
OldTimeElapsed += New - Old;
}
System.gc();
return;
}
System.gc();
}
long GetSmallFactors(
final BigInteger NumberToFactor,
BigInteger PD[],
int Exp[],
int Typ[],
final int Type)
{
long Div, TestComp;
int i;
boolean checkExpParity = false;
BigNbrToBigInt(NumberToFactor);
NbrFactors = 0;
for (i = 0; i < 400; i++)
{
Exp[i] = Typ[i] = 0;
}
while ((TestNbr[0] & 1) == 0)
{ /* N even */
if (Exp[NbrFactors] == 0)
{
PD[NbrFactors] = BigInt2;
}
Exp[NbrFactors]++;
DivBigNbrByLong(TestNbr, 2, TestNbr);
}
if (Exp[NbrFactors] != 0)
{
NbrFactors++;
}
while (RemDivBigNbrByLong(TestNbr, 3) == 0)
{
if (Type == 1)
{
checkExpParity ^= true;
}
if (Exp[NbrFactors] == 0)
{
PD[NbrFactors] = BigInt3;
}
Exp[NbrFactors]++;
DivBigNbrByLong(TestNbr, 3, TestNbr);
}
if (checkExpParity)
{
return -1; /* Discard it */
}
if (Exp[NbrFactors] != 0)
{
NbrFactors++;
}
Div = 5;
TestComp = TestNbr[0] + (TestNbr[1] << 31);
if (TestComp < 0)
{
TestComp = 10000 * DosALa31;
}
else
{
for (i = 2; i < NumberLength; i++)
{
if (TestNbr[i] != 0)
{
TestComp = 10000 * DosALa31;
break;
}
}
}
while (Div < 131072)
{
if (Div % 3 != 0)
{
while (RemDivBigNbrByLong(TestNbr, Div) == 0)
{
if (Type == 1 && Div % 4 == 3)
{
checkExpParity ^= true;
}
if (Exp[NbrFactors] == 0)
{
PD[NbrFactors] = BigInteger.valueOf(Div);
}
Exp[NbrFactors]++;
DivBigNbrByLong(TestNbr, Div, TestNbr);
TestComp = TestNbr[0] + (TestNbr[1] << 31);
if (TestComp < 0)
{
TestComp = 10000 * DosALa31;
}
else
{
for (i = 2; i < NumberLength; i++)
{
if (TestNbr[i] != 0)
{
TestComp = 10000 * DosALa31;
break;
}
}
} /* end while */
}
if (checkExpParity)
{
return -1; /* Discard it */
}
if (Exp[NbrFactors] != 0)
{
NbrFactors++;
}
}
Div += 2;
if (TestComp < Div * Div && TestComp != 1)
{
if (Type == 1 && TestComp % 4 == 3)
{
return -1; /* Discard it */
}
if (Exp[NbrFactors] != 0)
{
NbrFactors++;
}
PD[NbrFactors] = BigInteger.valueOf(TestComp);
Exp[NbrFactors] = 1;
TestComp = 1;
NbrFactors++;
break;
}
} /* end while */
return TestComp;
}
int PowerCheck(final int i)
{
long New;
final int maxExpon = (PD[i].bitLength() - 1) / 17;
int h, j;
long modulus;
int intLog2N;
double log2N;
BigInteger root, rootN1, rootN, dif, nextroot;
final int prime2310x1[] =
{ 2311, 4621, 9241, 11551, 18481, 25411, 32341, 34651, 43891, 50821 };
// Primes of the form 2310x+1.
boolean expon2 = true, expon3 = true, expon5 = true;
boolean expon7 = true, expon11 = true;
for (h = 0; h < prime2310x1.length; h++)
{
final long testprime = prime2310x1[h];
final long mod = PD[i].mod(BigInteger.valueOf(testprime)).intValue();
if (expon2 && modPow(mod, testprime / 2, testprime) > 1)
expon2 = false;
if (expon3 && modPow(mod, testprime / 3, testprime) > 1)
expon3 = false;
if (expon5 && modPow(mod, testprime / 5, testprime) > 1)
expon5 = false;
if (expon7 && modPow(mod, testprime / 7, testprime) > 1)
expon7 = false;
if (expon11 && modPow(mod, testprime / 11, testprime) > 1)
expon11 = false;
}
boolean ProcessExpon[] = new boolean[maxExpon + 1];
boolean primes[] = new boolean[2 * maxExpon + 3];
for (h = 2; h <= maxExpon; h++)
{
ProcessExpon[h] = true;
}
for (h = 2; h < primes.length; h++)
{
primes[h] = true;
}
for (h = 2; h * h < primes.length; h++)
{ // Generation of primes
for (j = h * h; j < primes.length; j += h)
{ // using Eratosthenes sieve
primes[j] = false;
}
}
for (h = 13; h < primes.length; h++)
{
if (primes[h])
{
int processed = 0;
for (j = 2 * h + 1; j < primes.length; j += 2 * h)
{
if (primes[j])
{
modulus = PD[i].mod(BigInteger.valueOf(j)).longValue();
if (modPow(modulus, j / h, j) > 1)
{
for (j = h; j <= maxExpon; j += h)
{
ProcessExpon[j] = false;
}
break;
}
}
if (++processed > 10)
break;
}
}
}
for (int Exponent = maxExpon; Exponent >= 2; Exponent--)
{
if (Exponent % 2 == 0 && !expon2)
continue; // Not a square
if (Exponent % 3 == 0 && !expon3)
continue; // Not a cube
if (Exponent % 5 == 0 && !expon5)
continue; // Not a fifth power
if (Exponent % 7 == 0 && !expon7)
continue; // Not a 7th power
if (Exponent % 11 == 0 && !expon11)
continue; // Not an 11th power
if (!ProcessExpon[Exponent])
continue;
New = System.currentTimeMillis();
if (OldTimeElapsed >= 0
&& OldTimeElapsed / 1000 != (OldTimeElapsed + New - Old) / 1000)
{
OldTimeElapsed += New - Old;
Old = New;
labelStatus.setText(
"Transcurrió: "
+ GetDHMS(OldTimeElapsed / 1000)
+ " Exponente potencia: "
+ Exponent);
// Thread.yield();
if (TerminateThread)
{
throw new ArithmeticException();
}
}
intLog2N = PD[i].bitLength() - 1;
log2N =
intLog2N
+ Math.log(PD[i].shiftRight(intLog2N - 32).add(BigInt1).doubleValue())
/ Math.log(2)
- 32;
log2N /= Exponent;
if (log2N < 32)
{
root = BigInteger.valueOf((long) Math.exp(log2N * Math.log(2)));
}
else
{
intLog2N = (int) Math.floor(log2N) - 32;
root =
BigInteger
.valueOf((long) Math.exp((log2N - intLog2N) * Math.log(2)) + 10)
.shiftLeft(intLog2N);
}
for (;;)
{
rootN1 = root.pow(Exponent - 1);
rootN = root.multiply(rootN1);
dif = PD[i].subtract(rootN);
if (dif.signum() == 0)
{ // Perfect power
PD[i] = root;
Exp[i] *= Exponent;
return 1;
}
nextroot =
dif
.add(BigInt1)
.divide(BigInteger.valueOf(Exponent).multiply(rootN1))
.add(root)
.subtract(BigInt1);
if (root.compareTo(nextroot) <= 0)
break; // Not a perfect power
root = nextroot;
}
}
return 0;
}
// Perform Lehman algorithm
static BigInteger Lehman(final BigInteger nbr, final int k)
{
final long bitsSqr[] = { 0x0000000000000003L, // 3
0x0000000000000013L, // 5
0x0000000000000017L, // 7
0x000000000000023BL, // 11
0x000000000000161BL, // 13
0x000000000001A317L, // 17
0x0000000000030AF3L, // 19
0x000000000005335FL, // 23
0x0000000013D122F3L, // 29
0x00000000121D47B7L, // 31
0x000000165E211E9BL, // 37
0x000001B382B50737L, // 41
0x0000035883A3EE53L, // 43
0x000004351B2753DFL, // 47
0x0012DD703303AED3L, // 53
0x022B62183E7B92BBL, // 59
0x1713E6940A59F23BL, // 61
};
final int primes[] =
{ 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 };
int nbrs[] = new int[17];
int diffs[] = new int[17];
int i, j, m;
int intLog2N;
double log2N;
BigInteger root, rootN, dif, nextroot;
BigInteger bM, a, c, r, sqr, val;
if (!nbr.testBit(0))
{ // nbr Even
r = BigInt0;
m = 1;
bM = BigInt1;
}
else
{
if (k % 2 == 0)
{ // k Even
r = BigInt1;
m = 2;
bM = BigInt2;
}
else
{ // k Odd
r = BigInteger.valueOf(k).add(nbr).and(BigInt3);
m = 4;
bM = BigInteger.valueOf(4);
}
}
sqr = nbr.multiply(BigInteger.valueOf(k)).shiftLeft(2);
intLog2N = sqr.bitLength() - 1;
log2N =
intLog2N
+ Math.log(sqr.shiftRight(intLog2N - 32).add(BigInt1).doubleValue())
/ Math.log(2)
- 32;
log2N /= 2;
if (log2N < 32)
{
root = BigInteger.valueOf((long) Math.exp(log2N * Math.log(2)));
}
else
{
intLog2N = (int) Math.floor(log2N) - 32;
root =
BigInteger
.valueOf((long) Math.exp((log2N - intLog2N) * Math.log(2)) + 10)
.shiftLeft(intLog2N);
}
for (;;)
{
rootN = root.multiply(root);
dif = sqr.subtract(rootN);
if (dif.signum() == 0)
{ // Perfect power
break;
}
nextroot =
dif.add(BigInt1).divide(BigInt2.multiply(root)).add(root).subtract(
BigInt1);
if (root.compareTo(nextroot) <= 0)
break; // Not a perfect power
root = nextroot;
}
a = root;
while (!a.mod(bM).equals(r) ||
a.multiply(a).compareTo(sqr)<0)
{
a = a.add(BigInt1);
}
c = a.multiply(a).subtract(sqr);
for (i = 0; i < 17; i++)
{
final BigInteger prime = BigInteger.valueOf(primes[i]);
nbrs[i] = c.mod(prime).intValue();
diffs[i] = bM.multiply(a.shiftLeft(1).add(bM)).mod(prime).intValue();
}
for (j = 0; j < 10000; j++)
{
for (i = 0; i < 17; i++)
{
if ((bitsSqr[i] & (1L << nbrs[i])) == 0)
{ // Not a perfect square
break;
}
}
if (i == 17)
{ // Test for perfect square
val = a.add(BigInteger.valueOf(m * j));
c = val.multiply(val).subtract(sqr);
intLog2N = c.bitLength() - 1;
log2N =
intLog2N
+ Math.log(c.shiftRight(intLog2N - 32).add(BigInt1).doubleValue())
/ Math.log(2)
- 32;
log2N /= 2;
if (log2N < 32)
{
root = BigInteger.valueOf((long) Math.exp(log2N * Math.log(2)));
}
else
{
intLog2N = (int) Math.floor(log2N) - 32;
root =
BigInteger
.valueOf((long) Math.exp((log2N - intLog2N) * Math.log(2)) + 10)
.shiftLeft(intLog2N);
}
for (;;)
{
rootN = root.multiply(root);
dif = c.subtract(rootN);
if (dif.signum() == 0)
{ // Perfect power -> factor found
root = nbr.gcd(val.add(root));
if (root.compareTo(BigInteger.valueOf(10000)) > 0)
{
return root; // Return non-trivial found
}
}
nextroot =
dif.add(BigInt1).divide(BigInt2.multiply(root)).add(root).subtract(
BigInt1);
if (root.compareTo(nextroot) <= 0)
break; // Not a perfect power
root = nextroot;
}
}
for (i = 0; i < 17; i++)
{
nbrs[i] = (nbrs[i] + diffs[i]) % primes[i];
diffs[i] = (diffs[i] + 2 * m * m) % primes[i];
}
}
return BigInt1; // Factor not found
}
final void PowerPM1Check()
{
if (onlyFactoring)
{
boolean plus1 = false;
boolean minus1 = false;
int Exponent = 0;
int i, j;
int modulus;
long i2;
final int mod9 = NumberToFactor.mod(BigInteger.valueOf(9L)).intValue();
final int maxExpon = NumberToFactor.bitLength();
final double logar =
(maxExpon - 32) * Math.log(2)
+ Math.log(NumberToFactor.shiftRight(maxExpon - 32).longValue());
boolean ProcessExpon[] = new boolean[maxExpon + 1];
boolean primes[] = new boolean[2 * maxExpon + 3];
for (i = 2; i <= maxExpon; i++)
{
ProcessExpon[i] = true;
}
for (i = 2; i < primes.length; i++)
{
primes[i] = true;
}
for (i = 2; i * i < primes.length; i++)
{ // Generation of primes
for (j = i * i; j < primes.length; j += i)
{
primes[j] = false;
}
}
// If the number +/- 1 is multiple of a prime but not a multiple
// of its square then the number +/- 1 cannot be a perfect power.
for (i = 2; i < primes.length; i++)
{
if (primes[i])
{
i2 = (long) i * (long) i;
modulus = NumberToFactor.mod(BigInteger.valueOf(i)).intValue();
if (modulus == 1
&& NumberToFactor.mod(BigInteger.valueOf(i2)).longValue() != 1L)
{
plus1 = true; // NumberFactor cannot be a power + 1
}
if (modulus == i - 1
&& NumberToFactor.mod(BigInteger.valueOf(i2)).longValue() != i2 - 1L)
{
minus1 = true; // NumberFactor cannot be a power - 1
}
if (minus1 && plus1)
return;
if (!ProcessExpon[i / 2])
{
continue;
}
if (modulus > (plus1 ? 1 : 2) && modulus < (minus1 ? i - 1 : i - 2))
{
for (j = i / 2; j <= maxExpon; j += i / 2)
{
ProcessExpon[j] = false;
}
}
else
{
if (modulus == i - 2)
{
for (j = i - 1; j <= maxExpon; j += i - 1)
{
ProcessExpon[j] = false;
}
}
}
}
}
for (j = 2; j < 100; j++)
{
double u = logar / Math.log(j) + .000005;
Exponent = (int) Math.floor(u);
if (u - Exponent > .00001)
continue;
if (Exponent % 3 == 0 && mod9 > 2 && mod9 < 7)
continue;
if (!ProcessExpon[Exponent])
continue;
if (ProcessExponent(Exponent))
return;
}
for (; Exponent >= 2; Exponent--)
{
if (Exponent % 3 == 0 && mod9 > 2 && mod9 < 7)
continue;
if (!ProcessExpon[Exponent])
continue;
if (ProcessExponent(Exponent))
return;
}
}
}
private boolean ProcessExponent(int Exponent)
{
BigInteger NFp1, NFm1, root, rootN1, rootN, rootbak;
BigInteger nextroot, dif;
int intLog2N;
double log2N;
long New = System.currentTimeMillis();
if (OldTimeElapsed >= 0
&& OldTimeElapsed / 1000 != (OldTimeElapsed + New - Old) / 1000)
{
OldTimeElapsed += New - Old;
Old = New;
labelStatus.setText(
"Transcurrió: "
+ GetDHMS(OldTimeElapsed / 1000)
+ " Exponente potencia +/- 1: "
+ Exponent);
// Thread.yield();
if (TerminateThread)
{
throw new ArithmeticException();
}
}
NFp1 = NumberToFactor.add(BigInt1);
NFm1 = NumberToFactor.subtract(BigInt1);
intLog2N = NFp1.bitLength() - 1;
log2N =
intLog2N
+ Math.log(NFp1.shiftRight(intLog2N - 32).add(BigInt1).doubleValue())
/ Math.log(2)
- 32;
log2N /= Exponent;
if (log2N < 32)
{
root = BigInteger.valueOf((long) Math.exp(log2N * Math.log(2)));
}
else
{
intLog2N = (int) Math.floor(log2N) - 32;
root =
BigInteger
.valueOf((long) Math.exp((log2N - intLog2N) * Math.log(2)) + 10)
.shiftLeft(intLog2N);
}
rootbak = root;
for (;;)
{
rootN1 = root.pow(Exponent - 1);
rootN = root.multiply(rootN1);
dif = NFp1.subtract(rootN);
if (dif.signum() == 0)
{ // Perfect power
Cunningham(root, Exponent, BigInt1.negate(), PD[NbrFactors - 1]);
return true;
}
nextroot =
dif
.add(BigInt1)
.divide(BigInteger.valueOf(Exponent).multiply(rootN1))
.add(root)
.subtract(BigInt1);
if (root.compareTo(nextroot) <= 0)
break; // Not a perfect power
root = nextroot;
}
root = rootbak;
for (;;)
{
rootN1 = root.pow(Exponent - 1);
rootN = root.multiply(rootN1);
dif = NFm1.subtract(rootN);
if (dif.signum() == 0)
{ // Perfect power
Cunningham(root, Exponent, BigInt1, PD[NbrFactors - 1]);
return true;
}
nextroot =
dif
.add(BigInt1)
.divide(BigInteger.valueOf(Exponent).multiply(rootN1))
.add(root)
.subtract(BigInt1);
if (root.compareTo(nextroot) <= 0)
break; // Not a perfect power
root = nextroot;
}
return false;
}
final void LucasCheck()
{
int i, j;
if (onlyFactoring)
{
if (NumberToFactor.bitLength() > 32)
{
int maxExpon = NumberToFactor.bitLength();
double logar =
(maxExpon - 32) * Math.log(2)
+ Math.log(NumberToFactor.shiftRight(maxExpon - 32).longValue());
logar = logar / 0.481211825059603; // index of L
if (logar + .000005 - Math.floor(logar + .000005) > .00001)
return;
}
BigInteger LucasPrev = BigInteger.valueOf(-1);
BigInteger LucasAct = BigInt2;
BigInteger LucasNext;
i = 0;
for (;;)
{
j = LucasAct.compareTo(NumberToFactor);
if (j == 0)
{
FactorLucas(i, PD[NbrFactors - 1]);
return;
}
if (j > 0)
{
return;
}
LucasNext = LucasPrev.add(LucasAct);
LucasPrev = LucasAct;
LucasAct = LucasNext;
i++;
}
}
}
final void FibonacciCheck()
{
int i, j;
if (onlyFactoring)
{
if (NumberToFactor.bitLength() > 32)
{
int maxExpon = NumberToFactor.bitLength();
double logar =
(maxExpon - 32) * Math.log(2)
+ Math.log(NumberToFactor.shiftRight(maxExpon - 32).longValue());
logar = (logar + 0.80471895621705) / 0.481211825059603; // index of F.
if (logar + .000005 - Math.floor(logar + .000005) > .00001)
return;
}
BigInteger FibonPrev = BigInt1;
BigInteger FibonAct = BigInt0;
BigInteger FibonNext;
i = 0;
for (;;)
{
j = FibonAct.compareTo(NumberToFactor);
if (j == 0)
{
FactorFibonacci(i, PD[NbrFactors - 1]);
return;
}
if (j > 0)
{
return;
}
FibonNext = FibonPrev.add(FibonAct);
FibonPrev = FibonAct;
FibonAct = FibonNext;
i++;
}
}
}
// Prime checking routine
// Return codes: 0 = Number is prime.
// 1 = Number is composite.
int AprtCle(BigInteger N)
{
int i, j, G, H, I, J, K, P, Q, T, U, W, X;
int IV, InvX, LEVELnow, NP, PK, PL, PM, SW, VK, TestedQs, TestingQs;
int QQ, T1, T3, U1, U3, V1, V3;
int LengthN, LengthS;
long Mask;
double dS;
String primalityString = "";
lowerTextArea.setText("Comenzando rutina de verificación de primos.");
BigNbrToBigInt(N);
GetMontgomeryParms();
if (!Computing3Squares)
{
textAreaContents = "";
StringToLabel = "Verificando si es primo ";
insertBigNbr(N);
addStringToLabel("(" + N.toString().length() + " digits)");
primalityString =
textAreaContents + StringToLabel + "\nProgreso del APRT-CLE: ";
}
j = PK = PL = PM = 0;
for (I = 0; I < NumberLength; I++)
{
biS[I] = 0;
for (J = 0; J < PWmax; J++)
{
aiJX[J][I] = 0;
}
}
GetPrimes2Test : for (i = 0; i < LEVELmax; i++)
{
biS[0] = 2;
for (I = 1; I < NumberLength; I++)
{
biS[I] = 0;
}
for (j = 0; j < aiNQ[i]; j++)
{
Q = aiQ[j];
U = aiT[i] * Q;
do
{
U /= Q;
MultBigNbrByLong(biS, Q, biS);
}
while (U % Q == 0);
// Exit loop if S^2 > N.
if (CompareSquare(biS, TestNbr) > 0)
{
break GetPrimes2Test;
}
} /* End for j */
} /* End for i */
if (i == LEVELmax)
{ /* too big */
return ProbabilisticPrimeTest(N);
}
LEVELnow = i;
TestingQs = j;
T = aiT[LEVELnow];
NP = aiNP[LEVELnow];
MainStart : for (;;)
{
for (i = 0; i < NP; i++)
{
P = aiP[i];
SW = TestedQs = 0;
Q = W = (int) BigNbrModLong(TestNbr, P * P);
for (J = P - 2; J > 0; J--)
{
W = (W * Q) % (P * P);
}
if (P > 2 && W != 1)
{
SW = 1;
}
for (;;)
{
for (j = TestedQs; j <= TestingQs; j++)
{
Q = aiQ[j] - 1;
G = aiG[j];
K = 0;
while (Q % P == 0)
{
K++;
Q /= P;
}
Q = aiQ[j];
if (K == 0)
{
continue;
}
if (!Computing3Squares)
{
lowerTextArea.setText(
primalityString
+ "P = "
+ P
+ ", Q = "
+ Q
+ " ("
+ (i * (TestingQs + 1) + j) * 100 / (NP * (TestingQs + 1))
+ "%)");
}
PM = 1;
for (I = 1; I < K; I++)
{
PM = PM * P;
}
PL = (P - 1) * PM;
PK = P * PM;
J = 1;
for (I = 1; I < Q; I++)
{
J = J * G % Q;
aiIndx[J] = I;
}
J = 1;
for (I = 1; I <= Q - 2; I++)
{
J = J * G % Q;
aiF[I] = aiIndx[(Q + 1 - J) % Q];
}
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJ0[I][J] = aiJ1[I][J] = 0;
}
}
if (P > 2)
{
JacobiSum(1, 1, P, PK, PL, PM, Q);
}
else
{
if (K != 1)
{
JacobiSum(1, 1, P, PK, PL, PM, Q);
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJW[I][J] = 0;
}
}
if (K != 2)
{
for (I = 0; I < PM; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJW[I][J] = aiJ0[I][J];
}
}
JacobiSum(2, 1, P, PK, PL, PM, Q);
for (I = 0; I < PM; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJS[I][J] = aiJ0[I][J];
}
}
JS_JW(PK, PL, PM, P);
NormalizeJS(PK, PL, PM, P);
for (I = 0; I < PM; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJ1[I][J] = aiJS[I][J];
}
}
JacobiSum(3 << (K - 3), 1 << (K - 3), P, PK, PL, PM, Q);
for (J = 0; J < NumberLength; J++)
{
for (I = 0; I < PK; I++)
{
aiJW[I][J] = 0;
}
for (I = 0; I < PM; I++)
{
aiJS[I][J] = aiJ0[I][J];
}
}
JS_2(PK, PL, PM, P);
NormalizeJS(PK, PL, PM, P);
for (I = 0; I < PM; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJ2[I][J] = aiJS[I][J];
}
}
}
}
}
for (J = 0; J < NumberLength; J++)
{
aiJ00[0][J] = aiJ01[0][J] = MontgomeryMultR1[J];
for (I = 1; I < PK; I++)
{
aiJ00[I][J] = aiJ01[I][J] = 0;
}
}
VK = (int) BigNbrModLong(TestNbr, PK);
for (I = 1; I < PK; I++)
{
if (I % P != 0)
{
U1 = 1;
U3 = I;
V1 = 0;
V3 = PK;
while (V3 != 0)
{
QQ = U3 / V3;
T1 = U1 - V1 * QQ;
T3 = U3 - V3 * QQ;
U1 = V1;
U3 = V3;
V1 = T1;
V3 = T3;
}
aiInv[I] = (U1 + PK) % PK;
}
else
{
aiInv[I] = 0;
}
}
if (P != 2)
{
for (IV = 0; IV <= 1; IV++)
{
for (X = 1; X < PK; X++)
{
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJS[I][J] = aiJ0[I][J];
}
}
if (X % P == 0)
{
continue;
}
if (IV == 0)
{
LongToBigNbr(X, biExp);
}
else
{
LongToBigNbr(VK * X / PK, biExp);
if (VK * X / PK == 0)
{
continue;
}
}
JS_E(PK, PL, PM, P);
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJW[I][J] = 0;
}
}
InvX = aiInv[X];
for (I = 0; I < PK; I++)
{
J = I * InvX % PK;
AddBigNbrModN(aiJW[J], aiJS[I], aiJW[J]);
}
NormalizeJW(PK, PL, PM, P);
if (IV == 0)
{
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJS[I][J] = aiJ00[I][J];
}
}
}
else
{
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJS[I][J] = aiJ01[I][J];
}
}
}
JS_JW(PK, PL, PM, P);
if (IV == 0)
{
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJ00[I][J] = aiJS[I][J];
}
}
}
else
{
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJ01[I][J] = aiJS[I][J];
}
}
}
} /* end for X */
} /* end for IV */
}
else
{
if (K == 1)
{
MultBigNbrByLongModN(MontgomeryMultR1, Q, aiJ00[0]);
for (J = 0; J < NumberLength; J++)
{
aiJ01[0][J] = MontgomeryMultR1[J];
}
}
else
{
if (K == 2)
{
if (VK == 1)
{
for (J = 0; J < NumberLength; J++)
{
aiJ01[0][J] = MontgomeryMultR1[J];
}
}
for (J = 0; J < NumberLength; J++)
{
aiJS[0][J] = aiJ0[0][J];
aiJS[1][J] = aiJ0[1][J];
}
JS_2(PK, PL, PM, P);
if (VK == 3)
{
for (J = 0; J < NumberLength; J++)
{
aiJ01[0][J] = aiJS[0][J];
aiJ01[1][J] = aiJS[1][J];
}
}
MultBigNbrByLongModN(aiJS[0], Q, aiJ00[0]);
MultBigNbrByLongModN(aiJS[1], Q, aiJ00[1]);
}
else
{
for (IV = 0; IV <= 1; IV++)
{
for (X = 1; X < PK; X += 2)
{
for (I = 0; I <= PM; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJS[I][J] = aiJ1[I][J];
}
}
if (X % 8 == 5 || X % 8 == 7)
{
continue;
}
if (IV == 0)
{
LongToBigNbr(X, biExp);
}
else
{
LongToBigNbr(VK * X / PK, biExp);
if (VK * X / PK == 0)
{
continue;
}
}
JS_E(PK, PL, PM, P);
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJW[I][J] = 0;
}
}
InvX = aiInv[X];
for (I = 0; I < PK; I++)
{
J = I * InvX % PK;
AddBigNbrModN(aiJW[J], aiJS[I], aiJW[J]);
}
NormalizeJW(PK, PL, PM, P);
if (IV == 0)
{
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJS[I][J] = aiJ00[I][J];
}
}
}
else
{
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJS[I][J] = aiJ01[I][J];
}
}
}
NormalizeJS(PK, PL, PM, P);
JS_JW(PK, PL, PM, P);
if (IV == 0)
{
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJ00[I][J] = aiJS[I][J];
}
}
}
else
{
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJ01[I][J] = aiJS[I][J];
}
}
}
} /* end for X */
if (IV == 0 || VK % 8 == 1 || VK % 8 == 3)
{
continue;
}
for (I = 0; I < PM; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJW[I][J] = aiJ2[I][J];
aiJS[I][J] = aiJ01[I][J];
}
}
for (; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJW[I][J] = aiJS[I][J] = 0;
}
}
JS_JW(PK, PL, PM, P);
for (I = 0; I < PM; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJ01[I][J] = aiJS[I][J];
}
}
} /* end for IV */
}
}
}
for (I = 0; I < PL; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJS[I][J] = aiJ00[I][J];
}
}
for (; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJS[I][J] = 0;
}
}
DivBigNbrByLong(TestNbr, PK, biExp);
JS_E(PK, PL, PM, P);
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJW[I][J] = 0;
}
}
for (I = 0; I < PL; I++)
{
for (J = 0; J < PL; J++)
{
MontgomeryMult(aiJS[I], aiJ01[J], biTmp);
AddBigNbrModN(biTmp, aiJW[(I + J) % PK], aiJW[(I + J) % PK]);
}
}
NormalizeJW(PK, PL, PM, P);
MatchingRoot : do
{
H = -1;
W = 0;
for (I = 0; I < PL; I++)
{
if (!BigNbrIsZero(aiJW[I]))
{
if (H == -1
&& BigNbrAreEqual(aiJW[I], MontgomeryMultR1))
{
H = I;
}
else
{
H = -2;
AddBigNbrModN(aiJW[I], MontgomeryMultR1, biTmp);
if (BigNbrIsZero(biTmp))
{
W++;
}
}
}
}
if (H >= 0)
{
break MatchingRoot;
}
if (W != P - 1)
{
return 1; /* Not prime */
}
for (I = 0; I < PM; I++)
{
AddBigNbrModN(aiJW[I], MontgomeryMultR1, biTmp);
if (BigNbrIsZero(biTmp))
{
break;
}
}
if (I == PM)
{
return 1; /* Not prime */
}
for (J = 1; J <= P - 2; J++)
{
AddBigNbrModN(aiJW[I + J * PM], MontgomeryMultR1, biTmp);
if (!BigNbrIsZero(biTmp))
{
return 1; /* Not prime */
}
}
H = I + PL;
}
while (false);
if (SW == 1 || H % P == 0)
{
continue;
}
if (P != 2)
{
SW = 1;
continue;
}
if (K == 1)
{
if ((TestNbr[0] & 3) == 1)
{
SW = 1;
}
continue;
}
// if (Q^((N-1)/2) mod N != N-1), N is not prime.
MultBigNbrByLongModN(MontgomeryMultR1, Q, biTmp);
for (I = 0; I < NumberLength; I++)
{
biR[I] = biTmp[I];
}
I = NumberLength - 1;
Mask = 0x40000000L;
while ((TestNbr[I] & Mask) == 0)
{
Mask /= 2;
if (Mask == 0)
{
I--;
Mask = 0x40000000L;
}
}
do
{
Mask /= 2;
if (Mask == 0)
{
I--;
Mask = 0x40000000L;
}
MontgomeryMult(biR, biR, biT);
for (J = 0; J < NumberLength; J++)
{
biR[J] = biT[J];
}
if ((TestNbr[I] & Mask) != 0)
{
MontgomeryMult(biR, biTmp, biT);
for (J = 0; J < NumberLength; J++)
{
biR[J] = biT[J];
}
}
}
while (I > 0 || Mask > 2);
AddBigNbrModN(biR, MontgomeryMultR1, biTmp);
if (!BigNbrIsZero(biTmp))
{
return 1; /* Not prime */
}
SW = 1;
} /* end for j */
if (SW == 0)
{
TestedQs = TestingQs + 1;
if (TestingQs < aiNQ[LEVELnow] - 1)
{
TestingQs++;
Q = aiQ[TestingQs];
U = T * Q;
do
{
MultBigNbrByLong(biS, Q, biS);
U /= Q;
}
while (U % Q == 0);
continue; /* Retry */
}
LEVELnow++;
if (LEVELnow == LEVELmax)
{
return ProbabilisticPrimeTest(N); /* Cannot tell */
}
T = aiT[LEVELnow];
NP = aiNP[LEVELnow];
biS[0] = 2;
for (J = 1; J < NumberLength; J++)
{
biS[J] = 0;
}
for (J = 0; J <= aiNQ[LEVELnow]; J++)
{
Q = aiQ[J];
U = T * Q;
do
{
MultBigNbrByLong(biS, Q, biS);
U /= Q;
}
while (U % Q == 0);
if (CompareSquare(biS, TestNbr) > 0)
{
TestingQs = J;
continue MainStart; /* Retry from the beginning */
}
} /* end for J */
return ProbabilisticPrimeTest(N); /* Program error */
} /* end if */
break;
} /* end for (;;) */
} /* end for i */
// Final Test
LengthN = NumberLength;
for (I = 0; I < NumberLength; I++)
{
biN[I] = TestNbr[I];
TestNbr[I] = biS[I];
biR[I] = 0;
}
for (;;)
{
if (TestNbr[NumberLength - 1] != 0)
{
break;
}
NumberLength--;
}
dN = (double) TestNbr[NumberLength - 1];
if (NumberLength > 1)
{
dN += (double) TestNbr[NumberLength - 2] / dDosALa31;
}
if (NumberLength > 2)
{
dN += (double) TestNbr[NumberLength - 3] / dDosALa62;
}
LengthS = NumberLength;
dS = dN;
MontgomeryMultR1[0] = 1;
for (I = 1; I < NumberLength; I++)
{
MontgomeryMultR1[I] = 0;
}
biR[0] = 1;
BigNbrModN(biN, LengthN, biT); /* Compute N mod S */
for (J = 1; J <= T; J++)
{
MultBigNbrModN(biR, biT, biTmp);
for (i = NumberLength - 1; i > 0; i--)
{
if (biTmp[i] != 0)
{
break;
}
}
if (i == 0 && biTmp[0] != 1)
{
return 0; /* Number is prime */
}
for (;;)
{
if (biTmp[NumberLength - 1] != 0)
{
break;
}
NumberLength--;
}
for (I = 0; I < NumberLength; I++)
{
TestNbr[I] = biTmp[I];
}
dN = (double) TestNbr[NumberLength - 1];
if (NumberLength > 1)
{
dN += (double) TestNbr[NumberLength - 2] / dDosALa31;
}
if (NumberLength > 2)
{
dN += (double) TestNbr[NumberLength - 3] / dDosALa62;
}
for (i = NumberLength - 1; i > 0; i--)
{
if (TestNbr[i] != biTmp[i])
{
break;
}
}
if (TestNbr[i] > biTmp[i])
{
BigNbrModN(biN, LengthN, biTmp); /* Compute N mod R */
if (BigNbrIsZero(biTmp))
{ /* If N is multiple of R.. */
return 1; /* Number is composite */
}
}
dN = dS;
NumberLength = LengthS;
for (I = 0; I < NumberLength; I++)
{
biR[I] = TestNbr[I];
TestNbr[I] = biS[I];
}
} /* End for J */
return 0; /* Number is prime */
}
}
// Prime checking routine
// Return codes: 0 = Number is prime.
// 1 = Number is composite.
int ProbabilisticPrimeTest(BigInteger N)
{
long Base, Q;
int baseNbr, nbrBases, exp, index, j, k;
long mask;
lowerTextArea.setText("Comenzando rutina de verificación probabilística de primos de Rabin.");
BigNbrToBigInt(N);
exp = N.subtract(BigInt1).getLowestSetBit();
GetMontgomeryParms();
Base = 1;
nbrBases = N.bitLength() / 2;
for (baseNbr = 0; baseNbr < nbrBases; baseNbr++)
{
if (Base < 3)
{
Base++;
}
else
{
calculate_new_prime4 : for (;;)
{
Base += 2;
for (Q = 3; Q * Q <= Base; Q += 2)
{ /* Check if Base is prime */
if (Base % Q == 0)
{
continue calculate_new_prime4; /* Composite */
}
}
break; /* Prime found */
}
} /* end if */
lowerTextArea.setText(
"Rutina de verificación probabilística de primos de Rabin\n\nBase utilizada: "
+ Base
+ " ("
+ baseNbr * 100 / nbrBases
+ "%)");
System.arraycopy(MontgomeryMultR1, 0, biN, 0, NumberLength);
index = NumberLength - 1;
mask = 0x40000000L;
for (k = NumberLength * 31; k > exp; k--)
{
MontgomeryMult(biN, biN, biT);
if ((TestNbr[index] & mask) != 0)
{
MultBigNbrByLongModN(biT, Base, biT);
}
System.arraycopy(biT, 0, biN, 0, NumberLength);
mask /= 2;
if (mask == 0)
{
index--;
mask = 0x40000000L;
}
}
for (j = 0; j < NumberLength; j++)
{
if (biN[j] != MontgomeryMultR1[j])
{
break;
}
}
if (j == NumberLength)
{
continue;
} /* Probable prime, go to next base */
for (k = 0; k < exp; k++)
{
AddBigNbr(biN, MontgomeryMultR1, biT);
for (j = 0; j < NumberLength; j++)
{
if (biT[j] != TestNbr[j])
{
break;
}
}
if (j == NumberLength)
{
break;
} /* Probable prime, go to next base */
MontgomeryMult(biN, biN, biT);
System.arraycopy(biT, 0, biN, 0, NumberLength);
}
if (k == exp)
{
for (j = 0; j < NumberLength; j++)
{
if (biN[j] != MontgomeryMultR1[j])
{
break;
}
}
if (j < NumberLength)
{
return 1;
} /* Composite number */
}
}
return 0; /* Indicate probable prime */
}
// Compare Nbr1^2 vs. Nbr2
int CompareSquare(long Nbr1[], long Nbr2[])
{
int I, k;
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, TestNbr, biTmp);
if (BigNbrIsZero(biTmp))
{
return 0;
} // Nbr1^2 == Nbr2
if (biTmp[NumberLength - 1] >= 0)
{
return 1;
} // Nbr1^2 > Nbr2
return -1; // Nbr1^2 < Nbr2
}
// Perform JS <- JS ^ E
void JS_E(int PK, int PL, int PM, int P)
{
int I, J, K;
long Mask;
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 = 0x40000000L;
for (;;)
{
if ((biExp[I] & Mask) != 0)
{
break;
}
Mask /= 2;
}
do
{
JS_2(PK, PL, PM, P);
Mask /= 2;
if (Mask == 0)
{
Mask = 0x40000000L;
I--;
}
if ((biExp[I] & Mask) != 0)
{
JS_JW(PK, PL, PM, P);
}
}
while (I > 0 || Mask != 1);
}
// Perform JS <- JS * JW
void JS_JW(int PK, int PL, int PM, int P)
{
int I, J, K;
for (I = 0; I < PL; I++)
{
for (J = 0; J < PL; J++)
{
K = (I + J) % PK;
MontgomeryMult(aiJS[I], aiJW[J], biTmp);
AddBigNbrModN(aiJX[K], biTmp, aiJX[K]);
}
}
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJS[I][J] = aiJX[I][J];
aiJX[I][J] = 0;
}
}
NormalizeJS(PK, PL, PM, P);
}
// Perform JS <- JS ^ 2
void JS_2(int PK, int PL, int PM, int P)
{
int I, J, K;
for (I = 0; I < PL; I++)
{
K = 2 * I % PK;
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);
AddBigNbrModN(aiJX[K], biTmp, aiJX[K]);
}
}
for (I = 0; I < PK; I++)
{
for (J = 0; J < NumberLength; J++)
{
aiJS[I][J] = aiJX[I][J];
aiJX[I][J] = 0;
}
}
NormalizeJS(PK, PL, PM, P);
}
// Normalize coefficient of JS
void NormalizeJS(int PK, int PL, int PM, int P)
{
int I, J;
for (I = PL; I < PK; I++)
{
if (!BigNbrIsZero(aiJS[I]))
{
for (J = 0; J < NumberLength; 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 < NumberLength; J++)
{
aiJS[I][J] = 0;
}
}
}
}
// Normalize coefficient of JW
void NormalizeJW(int PK, int PL, int PM, int P)
{
int I, J;
for (I = PL; I < PK; I++)
{
if (!BigNbrIsZero(aiJW[I]))
{
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;
}
}
}
}
void JacobiSum(int A, int B, int P, int PK, int PL, int PM, int Q)
{
int I, J, K;
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], MontgomeryMultR1, aiJ0[J]);
}
else
{
for (K = 1; K < P; K++)
{
SubtractBigNbrModN(
aiJ0[J - K * PM],
MontgomeryMultR1,
aiJ0[J - K * PM]);
}
}
}
}
BigInteger fnECM(BigInteger N, int FactorIndex)
{
int I, J, Pass, Qaux;
long L1, L2, LS, P, Q, IP, Paux = 1;
long[] A0 = new long[NLen];
long[] A02 = new long[NLen];
long[] A03 = new long[NLen];
long[] AA = new long[NLen];
long[] DX = new long[NLen];
long[] DZ = new long[NLen];
long[] GD = new long[NLen];
long[] M = new long[NLen];
long[] TX = new long[NLen];
fieldTX = TX;
long[] TZ = new long[NLen];
fieldTZ = TZ;
long[] UX = new long[NLen];
fieldUX = UX;
long[] UZ = new long[NLen];
fieldUZ = UZ;
long[] W1 = new long[NLen];
long[] W2 = new long[NLen];
long[] W3 = new long[NLen];
long[] W4 = new long[NLen];
long[] WX = new long[NLen];
long[] WZ = new long[NLen];
long[] X = new long[NLen];
long[] Z = new long[NLen];
long[] Aux1 = new long[NLen];
fieldAux1 = Aux1;
long[] Aux2 = new long[NLen];
fieldAux2 = Aux2;
long[] Aux3 = new long[NLen];
fieldAux3 = Aux3;
long[] Aux4 = new long[NLen];
fieldAux4 = Aux4;
long[] Xaux = new long[NLen];
long[] Zaux = new long[NLen];
long[][] root = new long[480][NLen];
byte[] sieve = new byte[23100];
byte[] sieve2310 = new byte[2310];
int[] sieveidx = new int[480];
String UpperLine;
String LowerLine;
String primalityString;
int Prob, i, j, u;
BigInteger NN;
boolean PrevCurveECMd = false;
fieldAA = AA;
BigNbrToBigInt(N);
GetMontgomeryParms();
for (I = 0; I < NumberLength; I++)
{
M[I] = DX[I] = DZ[I] = W3[I] = W4[I] = GD[I] = 0;
}
textAreaContents = "";
StringToLabel = "Factorizando ";
insertBigNbr(N);
addStringToLabel("(" + N.toString().length() + " dígitos)");
EC--;
SmallPrime[0] = 2;
P = 3;
indexM = 1;
for (indexM = 1; indexM < SmallPrime.length; indexM++)
{
SmallPrime[indexM] = (int) P; /* Store prime */
calculate_new_prime1 : for (;;)
{
P += 2;
for (Q = 3; Q * Q <= P; Q += 2)
{ /* Check if P is prime */
if (P % Q == 0)
{
continue calculate_new_prime1; /* Composite */
}
}
break; /* Prime found */
}
}
foundByLehman = false;
do
{
new_curve : for (;;)
{
if (NextEC > 0)
{
EC = NextEC;
NextEC = -1;
if (EC >= TYP_SIQS)
{
return BigInt1;
}
}
else
{
EC++;
NN = Lehman(NumberToFactor, EC);
if (!NN.equals(BigInt1))
{ // Factor found.
foundByLehman = true;
return NN;
}
L1 = N.toString().length(); // Get number of digits.
if (L1 > 30 && L1 <= 90 && // If between 30 and 90 digits...
(digitsInGroup & 0x400) == 0)
{ // Switch to SIQS checkbox is set.
int limit = limits[((int)L1 - 31) / 5];
if (EC % 50000000 > limit && !PrevCurveECMd ||
EC % 50000000 == limit && PrevCurveECMd)
{ // Switch to SIQS.
EC += TYP_SIQS;
return BigInt1;
}
}
}
PrevCurveECMd = true;
Typ[FactorIndex] = EC;
L1 = 2000;
L2 = 200000;
LS = 45;
Paux = EC;
nbrPrimes = 303; /* Number of primes less than 2000 */
if (EC > 25)
{
if (EC < 326)
{
L1 = 50000;
L2 = 5000000;
LS = 224;
Paux = EC - 24;
nbrPrimes = 5133; /* Number of primes less than 50000 */
}
else
{
if (EC < 2000)
{
L1 = 1000000;
L2 = 100000000;
LS = 1001;
Paux = EC - 299;
nbrPrimes = 78498; /* Number of primes less than 1000000 */
}
else
{
L1 = 11000000;
L2 = 1100000000;
LS = 3316;
Paux = EC - 1900;
nbrPrimes = 726517; /* Number of primes less than 11000000 */
}
}
}
primalityString =
textAreaContents
+ StringToLabel
+ "\nLímite (B1="
+ L1
+ "; B2="
+ L2
+ ") Curva ";
UpperLine = "Dígitos en factor: ";
LowerLine = "Probabilidad: ";
for (I = 0; I < 6; I++)
{
UpperLine += " >= " + (I * 5 + 15);
Prob =
(int) Math.round(
100
* (1 - Math.exp(- ((double) L1 * (double) Paux) / ProbArray[I])));
if (Prob == 100)
{
LowerLine += " 100% ";
}
else
{
if (Prob >= 10)
{
LowerLine += " " + Prob + "% ";
}
else
{
LowerLine += " " + Prob + "% ";
}
}
} /* end for */
lowerTextArea.setText(
primalityString + EC + "\n" + UpperLine + "\n" + LowerLine);
LongToBigNbr(2 * (EC + 1), Aux1);
LongToBigNbr(3 * (EC + 1) * (EC + 1) - 1, Aux2);
ModInvBigNbr(Aux2, Aux2, TestNbr);
MultBigNbrModN(Aux1, Aux2, Aux3);
MultBigNbrModN(Aux3, MontgomeryMultR1, A0);
MontgomeryMult(A0, A0, A02);
MontgomeryMult(A02, A0, A03);
SubtractBigNbrModN(A03, A0, Aux1);
MultBigNbrByLongModN(A02, 9, Aux2);
SubtractBigNbrModN(Aux2, MontgomeryMultR1, Aux2);
MontgomeryMult(Aux1, Aux2, Aux3);
if (BigNbrIsZero(Aux3))
{
continue;
}
MultBigNbrByLongModN(A0, 4, Z);
MultBigNbrByLongModN(A02, 6, Aux1);
SubtractBigNbrModN(MontgomeryMultR1, Aux1, Aux1);
MontgomeryMult(A02, A02, Aux2);
MultBigNbrByLongModN(Aux2, 3, Aux2);
SubtractBigNbrModN(Aux1, Aux2, Aux1);
MultBigNbrByLongModN(A03, 4, Aux2);
ModInvBigNbr(Aux2, Aux2, TestNbr);
MontgomeryMult(Aux2, MontgomeryMultAfterInv, Aux3);
MontgomeryMult(Aux1, Aux3, A0);
AddBigNbrModN(A0, MontgomeryMultR2, Aux1);
LongToBigNbr(4, Aux2);
ModInvBigNbr(Aux2, Aux3, TestNbr);
MultBigNbrModN(Aux3, MontgomeryMultR1, Aux2);
MontgomeryMult(Aux1, Aux2, AA);
MultBigNbrByLongModN(A02, 3, Aux1);
AddBigNbrModN(Aux1, MontgomeryMultR1, X);
/**************/
/* First step */
/**************/
System.arraycopy(X, 0, Xaux, 0, NumberLength);
System.arraycopy(Z, 0, Zaux, 0, NumberLength);
System.arraycopy(MontgomeryMultR1, 0, GcdAccumulated, 0, NumberLength);
for (Pass = 0; Pass < 2; Pass++)
{
/* For powers of 2 */
indexPrimes = 0;
StepECM = 1;
for (I = 1; I <= L1; I <<= 1)
{
duplicate(X, Z, X, Z);
}
for (I = 3; I <= L1; I *= 3)
{
duplicate(W1, W2, X, Z);
add3(X, Z, X, Z, W1, W2, X, Z);
}
if (Pass == 0)
{
MontgomeryMult(GcdAccumulated, Z, Aux1);
System.arraycopy(Aux1, 0, GcdAccumulated, 0, NumberLength);
}
else
{
GcdBigNbr(Z, TestNbr, GD);
if (!BigNbrAreEqual(GD, BigNbr1))
{
break new_curve;
}
}
/* for powers of odd primes */
indexM = 1;
do
{
indexPrimes++;
P = SmallPrime[indexM];
for (IP = P; IP <= L1; IP *= P)
{
prac((int) P, X, Z, W1, W2, W3, W4);
}
indexM++;
if (Pass == 0)
{
MontgomeryMult(GcdAccumulated, Z, Aux1);
System.arraycopy(Aux1, 0, GcdAccumulated, 0, NumberLength);
}
else
{
GcdBigNbr(Z, TestNbr, GD);
if (!BigNbrAreEqual(GD, BigNbr1))
{
break new_curve;
}
}
}
while (SmallPrime[indexM - 1] <= LS);
P += 2;
/* Initialize sieve2310[n]: 1 if gcd(P+2n,2310) > 1, 0 otherwise */
u = (int) P;
for (i = 0; i < 2310; i++)
{
sieve2310[i] =
(u % 3 == 0
|| u % 5 == 0
|| u % 7 == 0
|| u % 11 == 0 ? (byte) 1 : (byte) 0);
u += 2;
}
do
{
/* Generate sieve */
GenerateSieve((int) P, sieve, sieve2310, SmallPrime);
/* Walk through sieve */
for (i = 0; i < 23100; i++)
{
if (sieve[i] != 0)
continue; /* Do not process composites */
if (P + 2 * i > L1)
break;
indexPrimes++;
prac((int) (P + 2 * i), X, Z, W1, W2, W3, W4);
if (Pass == 0)
{
MontgomeryMult(GcdAccumulated, Z, Aux1);
System.arraycopy(Aux1, 0, GcdAccumulated, 0, NumberLength);
}
else
{
GcdBigNbr(Z, TestNbr, GD);
if (!BigNbrAreEqual(GD, BigNbr1))
{
break new_curve;
}
}
}
P += 46200;
}
while (P < L1);
if (Pass == 0)
{
if (BigNbrIsZero(GcdAccumulated))
{ // If GcdAccumulated is
System.arraycopy(Xaux, 0, X, 0, NumberLength);
System.arraycopy(Zaux, 0, Z, 0, NumberLength);
continue; // multiple of TestNbr, continue.
}
GcdBigNbr(GcdAccumulated, TestNbr, GD);
if (!BigNbrAreEqual(GD, BigNbr1))
{
break new_curve;
}
break;
}
} /* end for Pass */
/******************************************************/
/* Second step (using improved standard continuation) */
/******************************************************/
StepECM = 2;
j = 0;
for (u = 1; u < 2310; u += 2)
{
if (u % 3 == 0 || u % 5 == 0 || u % 7 == 0 || u % 11 == 0)
{
sieve2310[u / 2] = (byte) 1;
}
else
{
sieve2310[(sieveidx[j++] = u / 2)] = (byte) 0;
}
}
System.arraycopy(sieve2310, 0, sieve2310, 1155, 1155);
System.arraycopy(X, 0, Xaux, 0, NumberLength); // (X:Z) -> Q (output
System.arraycopy(Z, 0, Zaux, 0, NumberLength); // from step 1)
for (Pass = 0; Pass < 2; Pass++)
{
System.arraycopy(
MontgomeryMultR1,
0,
GcdAccumulated,
0,
NumberLength);
System.arraycopy(X, 0, UX, 0, NumberLength);
System.arraycopy(Z, 0, UZ, 0, NumberLength); // (UX:UZ) -> Q
ModInvBigNbr(Z, Aux2, TestNbr);
MontgomeryMult(Aux2, MontgomeryMultAfterInv, Aux1);
MontgomeryMult(Aux1, X, root[0]); // root[0] <- X/Z (Q)
J = 0;
AddBigNbrModN(X, Z, Aux1);
MontgomeryMult(Aux1, Aux1, W1);
SubtractBigNbrModN(X, Z, Aux1);
MontgomeryMult(Aux1, Aux1, W2);
MontgomeryMult(W1, W2, TX);
SubtractBigNbrModN(W1, W2, Aux1);
MontgomeryMult(Aux1, AA, Aux2);
AddBigNbrModN(Aux2, W2, Aux3);
MontgomeryMult(Aux1, Aux3, TZ); // (TX:TZ) -> 2Q
SubtractBigNbrModN(X, Z, Aux1);
AddBigNbrModN(TX, TZ, Aux2);
MontgomeryMult(Aux1, Aux2, W1);
AddBigNbrModN(X, Z, Aux1);
SubtractBigNbrModN(TX, TZ, Aux2);
MontgomeryMult(Aux1, Aux2, W2);
AddBigNbrModN(W1, W2, Aux1);
MontgomeryMult(Aux1, Aux1, Aux2);
MontgomeryMult(Aux2, UZ, X);
SubtractBigNbrModN(W1, W2, Aux1);
MontgomeryMult(Aux1, Aux1, Aux2);
MontgomeryMult(Aux2, UX, Z); // (X:Z) -> 3Q
for (I = 5; I < 2310; I += 2)
{
System.arraycopy(X, 0, WX, 0, NumberLength);
System.arraycopy(Z, 0, WZ, 0, NumberLength);
SubtractBigNbrModN(X, Z, Aux1);
AddBigNbrModN(TX, TZ, Aux2);
MontgomeryMult(Aux1, Aux2, W1);
AddBigNbrModN(X, Z, Aux1);
SubtractBigNbrModN(TX, TZ, Aux2);
MontgomeryMult(Aux1, Aux2, W2);
AddBigNbrModN(W1, W2, Aux1);
MontgomeryMult(Aux1, Aux1, Aux2);
MontgomeryMult(Aux2, UZ, X);
SubtractBigNbrModN(W1, W2, Aux1);
MontgomeryMult(Aux1, Aux1, Aux2);
MontgomeryMult(Aux2, UX, Z); // (X:Z) -> 5Q, 7Q, ...
if (Pass == 0)
{
MontgomeryMult(GcdAccumulated, Aux1, Aux2);
System.arraycopy(Aux2, 0, GcdAccumulated, 0, NumberLength);
}
else
{
GcdBigNbr(Aux1, TestNbr, GD);
if (!BigNbrAreEqual(GD, BigNbr1))
{
break new_curve;
}
}
if (I == 1155)
{
System.arraycopy(X, 0, DX, 0, NumberLength);
System.arraycopy(Z, 0, DZ, 0, NumberLength); // (DX:DZ) -> 1155Q
}
if (I % 3 != 0 && I % 5 != 0 && I % 7 != 0 && I % 11 != 0)
{
J++;
ModInvBigNbr(Z, Aux2, TestNbr);
MontgomeryMult(Aux2, MontgomeryMultAfterInv, Aux1);
MontgomeryMult(Aux1, X, root[J]); // root[J] <- X/Z
}
System.arraycopy(WX, 0, UX, 0, NumberLength); // (UX:UZ) <-
System.arraycopy(WZ, 0, UZ, 0, NumberLength); // Previous (X:Z)
} /* end for I */
AddBigNbrModN(DX, DZ, Aux1);
MontgomeryMult(Aux1, Aux1, W1);
SubtractBigNbrModN(DX, DZ, Aux1);
MontgomeryMult(Aux1, Aux1, W2);
MontgomeryMult(W1, W2, X);
SubtractBigNbrModN(W1, W2, Aux1);
MontgomeryMult(Aux1, AA, Aux2);
AddBigNbrModN(Aux2, W2, Aux3);
MontgomeryMult(Aux1, Aux3, Z);
System.arraycopy(X, 0, UX, 0, NumberLength);
System.arraycopy(Z, 0, UZ, 0, NumberLength); // (UX:UZ) -> 2310Q
AddBigNbrModN(X, Z, Aux1);
MontgomeryMult(Aux1, Aux1, W1);
SubtractBigNbrModN(X, Z, Aux1);
MontgomeryMult(Aux1, Aux1, W2);
MontgomeryMult(W1, W2, TX);
SubtractBigNbrModN(W1, W2, Aux1);
MontgomeryMult(Aux1, AA, Aux2);
AddBigNbrModN(Aux2, W2, Aux3);
MontgomeryMult(Aux1, Aux3, TZ); // (TX:TZ) -> 2*2310Q
SubtractBigNbrModN(X, Z, Aux1);
AddBigNbrModN(TX, TZ, Aux2);
MontgomeryMult(Aux1, Aux2, W1);
AddBigNbrModN(X, Z, Aux1);
SubtractBigNbrModN(TX, TZ, Aux2);
MontgomeryMult(Aux1, Aux2, W2);
AddBigNbrModN(W1, W2, Aux1);
MontgomeryMult(Aux1, Aux1, Aux2);
MontgomeryMult(Aux2, UZ, X);
SubtractBigNbrModN(W1, W2, Aux1);
MontgomeryMult(Aux1, Aux1, Aux2);
MontgomeryMult(Aux2, UX, Z); // (X:Z) -> 3*2310Q
Qaux = (int) (L1 / 4620);
maxIndexM = (int) (L2 / 4620);
for (indexM = 0; indexM <= maxIndexM; indexM++)
{
if (indexM >= Qaux)
{ // If inside step 2 range...
if (indexM == 0)
{
ModInvBigNbr(UZ, Aux2, TestNbr);
MontgomeryMult(Aux2, MontgomeryMultAfterInv, Aux3);
MontgomeryMult(UX, Aux3, Aux1); // Aux1 <- X/Z (2310Q)
}
else
{
ModInvBigNbr(Z, Aux2, TestNbr);
MontgomeryMult(Aux2, MontgomeryMultAfterInv, Aux3);
MontgomeryMult(X, Aux3, Aux1); // Aux1 <- X/Z (3,5,*
} // 2310Q)
/* Generate sieve */
if (indexM % 10 == 0 || indexM == Qaux)
{
GenerateSieve(
indexM / 10 * 46200 + 1,
sieve,
sieve2310,
SmallPrime);
}
/* Walk through sieve */
J = 1155 + (indexM % 10) * 2310;
for (i = 0; i < 480; i++)
{
j = sieveidx[i]; // 0 < J < 1155
if (sieve[J + j] != 0 && sieve[J - 1 - j] != 0)
{
continue; // Do not process if both are composite numbers.
}
SubtractBigNbrModN(Aux1, root[i], M);
MontgomeryMult(GcdAccumulated, M, Aux2);
System.arraycopy(Aux2, 0, GcdAccumulated, 0, NumberLength);
}
if (Pass != 0)
{
GcdBigNbr(GcdAccumulated, TestNbr, GD);
if (!BigNbrAreEqual(GD, BigNbr1))
{
break new_curve;
}
}
}
if (indexM != 0)
{ // Update (X:Z)
System.arraycopy(X, 0, WX, 0, NumberLength);
System.arraycopy(Z, 0, WZ, 0, NumberLength);
SubtractBigNbrModN(X, Z, Aux1);
AddBigNbrModN(TX, TZ, Aux2);
MontgomeryMult(Aux1, Aux2, W1);
AddBigNbrModN(X, Z, Aux1);
SubtractBigNbrModN(TX, TZ, Aux2);
MontgomeryMult(Aux1, Aux2, W2);
AddBigNbrModN(W1, W2, Aux1);
MontgomeryMult(Aux1, Aux1, Aux2);
MontgomeryMult(Aux2, UZ, X);
SubtractBigNbrModN(W1, W2, Aux1);
MontgomeryMult(Aux1, Aux1, Aux2);
MontgomeryMult(Aux2, UX, Z);
System.arraycopy(WX, 0, UX, 0, NumberLength);
System.arraycopy(WZ, 0, UZ, 0, NumberLength);
}
} // end for Q
if (Pass == 0)
{
if (BigNbrIsZero(GcdAccumulated))
{ // If GcdAccumulated is
System.arraycopy(Xaux, 0, X, 0, NumberLength);
System.arraycopy(Zaux, 0, Z, 0, NumberLength);
continue; // multiple of TestNbr, continue.
}
GcdBigNbr(GcdAccumulated, TestNbr, GD);
if (BigNbrAreEqual(GD, TestNbr))
{
break;
}
if (!BigNbrAreEqual(GD, BigNbr1))
{
break new_curve;
}
break;
}
} /* end for Pass */
performLehman = true;
} /* End curve calculation */
}
while (BigNbrAreEqual(GD, TestNbr));
lowerTextArea.setText("");
StepECM = 0; /* do not show pass number on screen */
return BigIntToBigNbr(GD);
}
/**********************/
/* Auxiliary routines */
/**********************/
static void GenerateSieve(
int initial,
byte[] sieve,
byte[] sieve2310,
int[] SmallPrime)
{
int i, j, Q;
for (i = 0; i < 23100; i += 2310)
{
System.arraycopy(sieve2310, 0, sieve, i, 2310);
}
j = 5;
Q = 13; /* Point to prime 13 */
do
{
if (initial > Q * Q)
{
for (i = (int) (((long) initial * ((Q - 1) / 2)) % Q);
i < 23100;
i += Q)
{
sieve[i] = 1; /* Composite */
}
}
else
{
i = Q * Q - initial;
if (i < 46200)
{
for (i = i / 2; i < 23100; i += Q)
{
sieve[i] = 1; /* Composite */
}
}
else
{
break;
}
}
Q = SmallPrime[++j];
}
while (Q < 5000);
}
void BigNbrToBigInt(BigInteger N)
{
byte[] Result;
long[] Temp;
int i, j;
long mask, p;
Result = N.toByteArray();
NumberLength = (Result.length * 8 + 30)/31;
Temp = new long[NumberLength+1];
yieldFreq = 1000000 / (NumberLength * NumberLength);
if (yieldFreq > 100000)
yieldFreq = yieldFreq / 100000 * 100000;
else if (yieldFreq > 10000)
yieldFreq = yieldFreq / 10000 * 10000;
else if (yieldFreq > 1000)
yieldFreq = yieldFreq / 1000 * 1000;
else if (yieldFreq > 100)
yieldFreq = yieldFreq / 100 * 100;
j = 0;
mask = 1;
p = 0;
for (i = Result.length - 1; i >= 0; i--)
{
p += mask * (long) (Result[i] >= 0 ? Result[i] : Result[i] + 256);
mask *= 0x100;
if (mask == DosALa32)
{
Temp[j++] = p;
mask = 1;
p = 0;
}
}
Temp[j] = p;
Convert32To31Bits(Temp, TestNbr);
if (TestNbr[NumberLength - 1] > Mi)
{
TestNbr[NumberLength] = 0;
NumberLength++;
}
TestNbr[NumberLength] = 0;
}
/*********************************************************/
/* Start of code "borrowed" from Paul Zimmermann's ECM4C */
/*********************************************************/
final static int ADD = 6; /* number of multiplications in an addition */
final static int DUP = 5; /* number of multiplications in a duplicate */
/* returns the number of modular multiplications */
static int lucas_cost(int n, double v)
{
int c, d, e, r;
d = n;
r = (int) ((double) d / v + 0.5);
if (r >= n)
return (ADD * n);
d = n - r;
e = 2 * r - n;
c = DUP + ADD; /* initial duplicate and final addition */
while (d != e)
{
if (d < e)
{
r = d;
d = e;
e = r;
}
if (4 * d <= 5 * e && ((d + e) % 3) == 0)
{ /* condition 1 */
r = (2 * d - e) / 3;
e = (2 * e - d) / 3;
d = r;
c += 3 * ADD; /* 3 additions */
}
else if (4 * d <= 5 * e && (d - e) % 6 == 0)
{ /* condition 2 */
d = (d - e) / 2;
c += ADD + DUP; /* one addition, one duplicate */
}
else if (d <= (4 * e))
{ /* condition 3 */
d -= e;
c += ADD; /* one addition */
}
else if ((d + e) % 2 == 0)
{ /* condition 4 */
d = (d - e) / 2;
c += ADD + DUP; /* one addition, one duplicate */
}
else if (d % 2 == 0)
{ /* condition 5 */
d /= 2;
c += ADD + DUP; /* one addition, one duplicate */
}
else if (d % 3 == 0)
{ /* condition 6 */
d = d / 3 - e;
c += 3 * ADD + DUP; /* three additions, one duplicate */
}
else if ((d + e) % 3 == 0)
{ /* condition 7 */
d = (d - 2 * e) / 3;
c += 3 * ADD + DUP; /* three additions, one duplicate */
}
else if ((d - e) % 3 == 0)
{ /* condition 8 */
d = (d - e) / 3;
c += 3 * ADD + DUP; /* three additions, one duplicate */
}
else if (e % 2 == 0)
{ /* condition 9 */
e /= 2;
c += ADD + DUP; /* one addition, one duplicate */
}
}
return (c);
}
/* computes nP from P=(x:z) and puts the result in (x:z). Assumes n>2. */
void prac(
int n,
long[] x,
long[] z,
long[] xT,
long[] zT,
long[] xT2,
long[] zT2)
{
int d, e, r, i;
long[] t;
long[] xA = x, zA = z;
long[] xB = fieldAux1, zB = fieldAux2;
long[] xC = fieldAux3, zC = fieldAux4;
double v[] =
{
1.61803398875,
1.72360679775,
1.618347119656,
1.617914406529,
1.612429949509,
1.632839806089,
1.620181980807,
1.580178728295,
1.617214616534,
1.38196601125 };
/* chooses the best value of v */
r = lucas_cost(n, v[0]);
i = 0;
for (d = 1; d < 10; d++)
{
e = lucas_cost(n, v[d]);
if (e < r)
{
r = e;
i = d;
}
}
d = n;
r = (int) ((double) d / v[i] + 0.5);
/* first iteration always begins by Condition 3, then a swap */
d = n - r;
e = 2 * r - n;
System.arraycopy(xA, 0, xB, 0, NumberLength); // B = A
System.arraycopy(zA, 0, zB, 0, NumberLength);
System.arraycopy(xA, 0, xC, 0, NumberLength); // C = A
System.arraycopy(zA, 0, zC, 0, NumberLength);
duplicate(xA, zA, xA, zA); /* A=2*A */
while (d != e)
{
if (d < e)
{
r = d;
d = e;
e = r;
t = xA;
xA = xB;
xB = t;
t = zA;
zA = zB;
zB = t;
}
/* do the first line of Table 4 whose condition qualifies */
if (4 * d <= 5 * e && ((d + e) % 3) == 0)
{ /* condition 1 */
r = (2 * d - e) / 3;
e = (2 * e - d) / 3;
d = r;
add3(xT, zT, xA, zA, xB, zB, xC, zC); /* T = f(A,B,C) */
add3(xT2, zT2, xT, zT, xA, zA, xB, zB); /* T2 = f(T,A,B) */
add3(xB, zB, xB, zB, xT, zT, xA, zA); /* B = f(B,T,A) */
t = xA;
xA = xT2;
xT2 = t;
t = zA;
zA = zT2;
zT2 = t; /* swap A and T2 */
}
else if (4 * d <= 5 * e && (d - e) % 6 == 0)
{ /* condition 2 */
d = (d - e) / 2;
add3(xB, zB, xA, zA, xB, zB, xC, zC); /* B = f(A,B,C) */
duplicate(xA, zA, xA, zA); /* A = 2*A */
}
else if (d <= (4 * e))
{ /* condition 3 */
d -= e;
add3(xT, zT, xB, zB, xA, zA, xC, zC); /* T = f(B,A,C) */
t = xB;
xB = xT;
xT = xC;
xC = t;
t = zB;
zB = zT;
zT = zC;
zC = t; /* circular permutation (B,T,C) */
}
else if ((d + e) % 2 == 0)
{ /* condition 4 */
d = (d - e) / 2;
add3(xB, zB, xB, zB, xA, zA, xC, zC); /* B = f(B,A,C) */
duplicate(xA, zA, xA, zA); /* A = 2*A */
}
else if (d % 2 == 0)
{ /* condition 5 */
d /= 2;
add3(xC, zC, xC, zC, xA, zA, xB, zB); /* C = f(C,A,B) */
duplicate(xA, zA, xA, zA); /* A = 2*A */
}
else if (d % 3 == 0)
{ /* condition 6 */
d = d / 3 - e;
duplicate(xT, zT, xA, zA); /* T1 = 2*A */
add3(xT2, zT2, xA, zA, xB, zB, xC, zC); /* T2 = f(A,B,C) */
add3(xA, zA, xT, zT, xA, zA, xA, zA); /* A = f(T1,A,A) */
add3(xT, zT, xT, zT, xT2, zT2, xC, zC); /* T1 = f(T1,T2,C) */
t = xC;
xC = xB;
xB = xT;
xT = t;
t = zC;
zC = zB;
zB = zT;
zT = t; /* circular permutation (C,B,T) */
}
else if ((d + e) % 3 == 0)
{ /* condition 7 */
d = (d - 2 * e) / 3;
add3(xT, zT, xA, zA, xB, zB, xC, zC); /* T1 = f(A,B,C) */
add3(xB, zB, xT, zT, xA, zA, xB, zB); /* B = f(T1,A,B) */
duplicate(xT, zT, xA, zA);
add3(xA, zA, xA, zA, xT, zT, xA, zA); /* A = 3*A */
}
else if ((d - e) % 3 == 0)
{ /* condition 8 */
d = (d - e) / 3;
add3(xT, zT, xA, zA, xB, zB, xC, zC); /* T1 = f(A,B,C) */
add3(xC, zC, xC, zC, xA, zA, xB, zB); /* C = f(A,C,B) */
t = xB;
xB = xT;
xT = t;
t = zB;
zB = zT;
zT = t; /* swap B and T */
duplicate(xT, zT, xA, zA);
add3(xA, zA, xA, zA, xT, zT, xA, zA); /* A = 3*A */
}
else if (e % 2 == 0)
{ /* condition 9 */
e /= 2;
add3(xC, zC, xC, zC, xB, zB, xA, zA); /* C = f(C,B,A) */
duplicate(xB, zB, xB, zB); /* B = 2*B */
}
}
add3(x, z, xA, zA, xB, zB, xC, zC);
}
/* adds Q=(x2:z2) and R=(x1:z1) and puts the result in (x3:z3),
using 5/6 mul, 6 add/sub and 6 mod. One assumes that Q-R=P or R-Q=P where P=(x:z).
Uses the following global variables:
- n : number to factor
- x, z : coordinates of P
- u, v, w : auxiliary variables
Modifies: x3, z3, u, v, w.
(x3,z3) may be identical to (x2,z2) and to (x,z)
*/
void add3(
long[] x3,
long[] z3,
long[] x2,
long[] z2,
long[] x1,
long[] z1,
long[] x,
long[] z)
{
long[] t = fieldTX;
long[] u = fieldTZ;
long[] v = fieldUX;
long[] w = fieldUZ;
SubtractBigNbrModN(x2, z2, v); // v = x2-z2
AddBigNbrModN(x1, z1, w); // w = x1+z1
MontgomeryMult(v, w, u); // u = (x2-z2)*(x1+z1)
AddBigNbrModN(x2, z2, w); // w = x2+z2
SubtractBigNbrModN(x1, z1, t); // t = x1-z1
MontgomeryMult(t, w, v); // v = (x2+z2)*(x1-z1)
AddBigNbrModN(u, v, t); // t = 2*(x1*x2-z1*z2)
MontgomeryMult(t, t, w); // w = 4*(x1*x2-z1*z2)^2
SubtractBigNbrModN(u, v, t); // t = 2*(x2*z1-x1*z2)
MontgomeryMult(t, t, v); // v = 4*(x2*z1-x1*z2)^2
if (BigNbrAreEqual(x, x3))
{
System.arraycopy(x, 0, u, 0, NumberLength);
System.arraycopy(w, 0, t, 0, NumberLength);
MontgomeryMult(z, t, w);
MontgomeryMult(v, u, z3);
System.arraycopy(w, 0, x3, 0, NumberLength);
}
else
{
MontgomeryMult(w, z, x3); // x3 = 4*z*(x1*x2-z1*z2)^2
MontgomeryMult(x, v, z3); // z3 = 4*x*(x2*z1-x1*z2)^2
}
}
/* computes 2P=(x2:z2) from P=(x1:z1), with 5 mul, 4 add/sub, 5 mod.
Uses the following global variables:
- n : number to factor
- b : (a+2)/4 mod n
- u, v, w : auxiliary variables
Modifies: x2, z2, u, v, w
*/
void duplicate(long[] x2, long[] z2, long[] x1, long[] z1)
{
long[] u = fieldUZ;
long[] v = fieldTX;
long[] w = fieldTZ;
AddBigNbrModN(x1, z1, w); // w = x1+z1
MontgomeryMult(w, w, u); // u = (x1+z1)^2
SubtractBigNbrModN(x1, z1, w); // w = x1-z1
MontgomeryMult(w, w, v); // v = (x1-z1)^2
MontgomeryMult(u, v, x2); // x2 = u*v = (x1^2 - z1^2)^2
SubtractBigNbrModN(u, v, w); // w = u-v = 4*x1*z1
MontgomeryMult(fieldAA, w, u);
AddBigNbrModN(u, v, u); // u = (v+b*w)
MontgomeryMult(w, u, z2); // z2 = (w*u)
}
/* End of code "borrowed" from Paul Zimmermann's ECM4C */
BigInteger BigIntToBigNbr(long[] GD)
{
byte[] Result;
long[] Temp;
int i, NL;
long digit;
Temp = new long[NumberLength];
Convert31To32Bits(GD, Temp);
NL = NumberLength * 4;
Result = new byte[NL];
for (i = 0; i < NumberLength; i++)
{
digit = Temp[i];
Result[NL - 1 - 4 * i] = (byte) (digit & 0xFF);
Result[NL - 2 - 4 * i] = (byte) (digit / 0x100 & 0xFF);
Result[NL - 3 - 4 * i] = (byte) (digit / 0x10000 & 0xFF);
Result[NL - 4 - 4 * i] = (byte) (digit / 0x1000000 & 0xFF);
}
return (new BigInteger(Result));
}
void LongToBigNbr(long Nbr, long Out[])
{
int i;
Out[0] = Nbr & 0x7FFFFFFFL;
Out[1] = (Nbr >> 31) & 0x7FFFFFFFL;
for (i = 2; i < NumberLength; i++)
{
Out[i] = (Nbr < 0 ? 0x7FFFFFFFL : 0);
}
}
boolean BigNbrIsZero(long Nbr[])
{
for (int i = 0; i < NumberLength; i++)
{
if (Nbr[i] != 0)
{
return false;
}
}
return true;
}
boolean BigNbrAreEqual(long Nbr1[], long Nbr2[])
{
for (int i = 0; i < NumberLength; i++)
{
if (Nbr1[i] != Nbr2[i])
{
return false;
}
}
return true;
}
void ChSignBigNbr(long Nbr[])
{
int NumberLength = this.NumberLength;
long carry = 0;
for (int i = 0; i < NumberLength; i++)
{
carry = (carry >> 31) - Nbr[i];
Nbr[i] = carry & 0x7FFFFFFFL;
}
}
void AddBigNbr(long Nbr1[], long Nbr2[], long Sum[])
{
int NumberLength = this.NumberLength;
long carry = 0;
for (int i = 0; i < NumberLength; i++)
{
carry = (carry >> 31) + Nbr1[i] + Nbr2[i];
Sum[i] = carry & 0x7FFFFFFFL;
}
}
void SubtractBigNbr(long Nbr1[], long Nbr2[], long Diff[])
{
int NumberLength = this.NumberLength;
long carry = 0;
for (int i = 0; i < NumberLength; i++)
{
carry = (carry >> 31) + Nbr1[i] - Nbr2[i];
Diff[i] = carry & 0x7FFFFFFFL;
}
}
void AddBigNbr32(long Nbr1[], long Nbr2[], long Sum[])
{
int NumberLength = this.NumberLength;
long carry = 0;
for (int i = 0; i < NumberLength; i++)
{
carry = (carry >> 32) + Nbr1[i] + Nbr2[i];
Sum[i] = carry & 0xFFFFFFFFL;
}
}
void SubtractBigNbr32(long Nbr1[], long Nbr2[], long Diff[])
{
int NumberLength = this.NumberLength;
long carry = 0;
for (int i = 0; i < NumberLength; i++)
{
carry = (carry >> 32) + Nbr1[i] - Nbr2[i];
Diff[i] = carry & 0xFFFFFFFFL;
}
}
void MultBigNbr(long Nbr1[], long Nbr2[], long Prod[])
{
int NumberLength = this.NumberLength;
long MaxUInt = 0x7FFFFFFFL;
long carry, Pr;
int i, j;
carry = Pr = 0;
for (i = 0; i < NumberLength; i++)
{
Pr = carry & MaxUInt;
carry >>>= 31;
for (j = 0; j <= i; j++)
{
Pr += Nbr1[j] * Nbr2[i - j];
carry += (Pr >>> 31);
Pr &= MaxUInt;
}
Prod[i] = Pr;
}
}
void MultBigNbrByLong(long Nbr1[], long Nbr2, long Prod[])
{
int NumberLength = this.NumberLength;
long MaxUInt = 0x7FFFFFFFL;
long Pr;
int i;
Pr = 0;
for (i = 0; i < NumberLength; i++)
{
Pr = (Pr >> 31) + Nbr2 * Nbr1[i];
Prod[i] = Pr & MaxUInt;
}
}
long BigNbrModLong(long Nbr1[], long Nbr2)
{
int i;
long Rem = 0;
for (i = NumberLength - 1; i >= 0; i--)
{
Rem = ((Rem << 31) + Nbr1[i]) % Nbr2;
}
return Rem;
}
private final void AddBigNbrModN(long Nbr1[], long Nbr2[], long Sum[])
{
int NumberLength = this.NumberLength;
long MaxUInt = 0x7FFFFFFFL;
long carry = 0;
int i;
for (i = 0; i < NumberLength; i++)
{
carry = (carry >> 31) + Nbr1[i] + Nbr2[i] - TestNbr[i];
Sum[i] = carry & MaxUInt;
}
if (carry < 0)
{
carry = 0;
for (i = 0; i < NumberLength; i++)
{
carry = (carry >> 31) + Sum[i] + TestNbr[i];
Sum[i] = carry & MaxUInt;
}
}
}
private final void SubtractBigNbrModN(long Nbr1[], long Nbr2[], long Diff[])
{
int NumberLength = this.NumberLength;
long MaxUInt = 0x7FFFFFFFL;
long carry = 0;
int i;
for (i = 0; i < NumberLength; i++)
{
carry = (carry >> 31) + Nbr1[i] - Nbr2[i];
Diff[i] = carry & MaxUInt;
}
if (carry < 0)
{
carry = 0;
for (i = 0; i < NumberLength; i++)
{
carry = (carry >> 31) + Diff[i] + TestNbr[i];
Diff[i] = carry & MaxUInt;
}
}
}
void MontgomeryMult(long Nbr1[], long Nbr2[], long Prod[])
{
long New;
int NumberLength = this.NumberLength;
String EcmInfo;
if (TerminateThread)
{
throw new ArithmeticException();
}
if (lModularMult >= 0)
{
lModularMult++;
if ((lModularMult % yieldFreq) == 0)
{
Thread.yield();
New = System.currentTimeMillis();
if (OldTimeElapsed >= 0
&& OldTimeElapsed / 1000 != (OldTimeElapsed + New - Old) / 1000)
{
OldTimeElapsed += New - Old;
Old = New;
switch (StepECM)
{
case 1 :
EcmInfo = "Paso 1: " + (indexPrimes * 100 / nbrPrimes) + "%";
break;
case 2 :
EcmInfo =
"Paso 2: "
+ (maxIndexM == 0 ? 0 : (indexM * 100 / maxIndexM))
+ "%";
break;
default :
EcmInfo = "";
}
labelStatus.setText(
"Transcurrió: "
+ GetDHMS(OldTimeElapsed / 1000)
+ " mult mod: "
+ (lModularMult >= 0 ? "" + lModularMult : "No lo sé")
+ " "
+ EcmInfo);
}
}
}
switch (NumberLength)
{
case 2 :
MontgomeryMult2(Nbr1, Nbr2, Prod);
break;
case 3 :
MontgomeryMult3(Nbr1, Nbr2, Prod);
break;
case 4 :
MontgomeryMult4(Nbr1, Nbr2, Prod);
break;
case 5 :
MontgomeryMult5(Nbr1, Nbr2, Prod);
break;
case 6 :
MontgomeryMult6(Nbr1, Nbr2, Prod);
break;
case 7 :
MontgomeryMult7(Nbr1, Nbr2, Prod);
break;
case 8 :
MontgomeryMult8(Nbr1, Nbr2, Prod);
break;
case 9 :
MontgomeryMult9(Nbr1, Nbr2, Prod);
break;
case 10 :
MontgomeryMult10(Nbr1, Nbr2, Prod);
break;
case 11 :
MontgomeryMult11(Nbr1, Nbr2, Prod);
break;
default:
if (KARATSUBA_ENABLED == false || NumberLength < KARATSUBA_CUTOFF)
{
LargeMontgomeryMult(Nbr1, Nbr2, Prod);
}
else
{
KaratsubaMontgomeryMult(Nbr1, Nbr2, Prod);
}
break;
}
}
void MontgomeryMult2(long Nbr1[], long Nbr2[], long Prod[])
{
long Pr, Nbr, MontDig;
long Prod0, Prod1;
Prod0 = Prod1 = 0;
long TestNbr0 = TestNbr[0];
long TestNbr1 = TestNbr[1];
long Nbr2_0 = Nbr2[0];
long Nbr2_1 = Nbr2[1];
for (int i=0; i<2; i++)
{
Pr = (Nbr = Nbr1[i]) * Nbr2_0 + Prod0;
MontDig = ((int) Pr * MontgomeryMultN) & 0x7FFFFFFFL;
Prod0 = (Pr = ((MontDig * TestNbr0 + Pr) >>> 31) +
MontDig * TestNbr1 + Nbr * Nbr2_1 + Prod1) & 0x7FFFFFFFL;
Prod1 = Pr >>> 31;
}
if (Prod1 > TestNbr1 || Prod1 == TestNbr1 && (Prod0 >= TestNbr0))
{
Prod0 = (Pr = Prod0 - TestNbr0) & 0x7FFFFFFFL;
Prod1 = ((Pr >> 31) + Prod1 - TestNbr1) & 0x7FFFFFFFL;
}
Prod[0] = Prod0;
Prod[1] = Prod1;
}
void MontgomeryMult3(long Nbr1[], long Nbr2[], long Prod[])
{
long Pr, Nbr, MontDig;
long Prod0, Prod1, Prod2;
Prod0 = Prod1 = Prod2 = 0;
long TestNbr0 = TestNbr[0];
long TestNbr1 = TestNbr[1];
long TestNbr2 = TestNbr[2];
long Nbr2_0 = Nbr2[0];
long Nbr2_1 = Nbr2[1];
long Nbr2_2 = Nbr2[2];
for (int i=0; i<3; i++)
{
Pr = (Nbr = Nbr1[i]) * Nbr2_0 + Prod0;
MontDig = ((int) Pr * MontgomeryMultN) & 0x7FFFFFFFL;
Prod0 = (Pr = ((MontDig * TestNbr0 + Pr) >>> 31) +
MontDig * TestNbr1 + Nbr * Nbr2_1 + Prod1) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >>> 31) +
MontDig * TestNbr2 + Nbr * Nbr2_2 + Prod2) & 0x7FFFFFFFL;
Prod2 = Pr >>> 31;
}
if (Prod2 > TestNbr2
|| Prod2 == TestNbr2
&& (Prod1 > TestNbr1 || Prod1 == TestNbr1 && (Prod0 >= TestNbr0)))
{
Prod0 = (Pr = Prod0 - TestNbr0) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >> 31) + Prod1 - TestNbr1) & 0x7FFFFFFFL;
Prod2 = ((Pr >> 31) + Prod2 - TestNbr2) & 0x7FFFFFFFL;
}
Prod[0] = Prod0;
Prod[1] = Prod1;
Prod[2] = Prod2;
}
void MontgomeryMult4(long Nbr1[], long Nbr2[], long Prod[])
{
long Pr, Nbr, MontDig;
long Prod0, Prod1, Prod2, Prod3;
Prod0 = Prod1 = Prod2 = Prod3 = 0;
long TestNbr0 = TestNbr[0];
long TestNbr1 = TestNbr[1];
long TestNbr2 = TestNbr[2];
long TestNbr3 = TestNbr[3];
long Nbr2_0 = Nbr2[0];
long Nbr2_1 = Nbr2[1];
long Nbr2_2 = Nbr2[2];
long Nbr2_3 = Nbr2[3];
for (int i=0; i<4; i++)
{
Pr = (Nbr = Nbr1[i]) * Nbr2_0 + Prod0;
MontDig = ((int) Pr * MontgomeryMultN) & 0x7FFFFFFFL;
Prod0 = (Pr = ((MontDig * TestNbr0 + Pr) >>> 31) +
MontDig * TestNbr1 + Nbr * Nbr2_1 + Prod1) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >>> 31) +
MontDig * TestNbr2 + Nbr * Nbr2_2 + Prod2) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >>> 31) +
MontDig * TestNbr3 + Nbr * Nbr2_3 + Prod3) & 0x7FFFFFFFL;
Prod3 = Pr >>> 31;
}
if (Prod3 > TestNbr3
|| Prod3 == TestNbr3
&& (Prod2 > TestNbr2
|| Prod2 == TestNbr2
&& (Prod1 > TestNbr1 || Prod1 == TestNbr1 && (Prod0 >= TestNbr0))))
{
Prod0 = (Pr = Prod0 - TestNbr0) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >> 31) + Prod1 - TestNbr1) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >> 31) + Prod2 - TestNbr2) & 0x7FFFFFFFL;
Prod3 = ((Pr >> 31) + Prod3 - TestNbr3) & 0x7FFFFFFFL;
}
Prod[0] = Prod0;
Prod[1] = Prod1;
Prod[2] = Prod2;
Prod[3] = Prod3;
}
void MontgomeryMult5(long Nbr1[], long Nbr2[], long Prod[])
{
long Pr, Nbr, MontDig;
long Prod0, Prod1, Prod2, Prod3, Prod4;
Prod0 = Prod1 = Prod2 = Prod3 = Prod4 = 0;
long TestNbr0 = TestNbr[0];
long TestNbr1 = TestNbr[1];
long TestNbr2 = TestNbr[2];
long TestNbr3 = TestNbr[3];
long TestNbr4 = TestNbr[4];
long Nbr2_0 = Nbr2[0];
long Nbr2_1 = Nbr2[1];
long Nbr2_2 = Nbr2[2];
long Nbr2_3 = Nbr2[3];
long Nbr2_4 = Nbr2[4];
for (int i=0; i<5; i++)
{
Pr = (Nbr = Nbr1[i]) * Nbr2_0 + Prod0;
MontDig = ((int) Pr * MontgomeryMultN) & 0x7FFFFFFFL;
Prod0 = (Pr = ((MontDig * TestNbr0 + Pr) >>> 31) +
MontDig * TestNbr1 + Nbr * Nbr2_1 + Prod1) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >>> 31) +
MontDig * TestNbr2 + Nbr * Nbr2_2 + Prod2) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >>> 31) +
MontDig * TestNbr3 + Nbr * Nbr2_3 + Prod3) & 0x7FFFFFFFL;
Prod3 = (Pr = (Pr >>> 31) +
MontDig * TestNbr4 + Nbr * Nbr2_4 + Prod4) & 0x7FFFFFFFL;
Prod4 = Pr >>> 31;
}
if (Prod4 > TestNbr4
|| Prod4 == TestNbr4
&& (Prod3 > TestNbr3
|| Prod3 == TestNbr3
&& (Prod2 > TestNbr2
|| Prod2 == TestNbr2
&& (Prod1 > TestNbr1 || Prod1 == TestNbr1 && (Prod0 >= TestNbr0)))))
{
Prod0 = (Pr = Prod0 - TestNbr0) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >> 31) + Prod1 - TestNbr1) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >> 31) + Prod2 - TestNbr2) & 0x7FFFFFFFL;
Prod3 = (Pr = (Pr >> 31) + Prod3 - TestNbr3) & 0x7FFFFFFFL;
Prod4 = ((Pr >> 31) + Prod4 - TestNbr4) & 0x7FFFFFFFL;
}
Prod[0] = Prod0;
Prod[1] = Prod1;
Prod[2] = Prod2;
Prod[3] = Prod3;
Prod[4] = Prod4;
}
void MontgomeryMult6(long Nbr1[], long Nbr2[], long Prod[])
{
long Pr, Nbr, MontDig;
long Prod0, Prod1, Prod2, Prod3, Prod4, Prod5;
Prod0 = Prod1 = Prod2 = Prod3 = Prod4 = Prod5 = 0;
long TestNbr0 = TestNbr[0];
long TestNbr1 = TestNbr[1];
long TestNbr2 = TestNbr[2];
long TestNbr3 = TestNbr[3];
long TestNbr4 = TestNbr[4];
long TestNbr5 = TestNbr[5];
long Nbr2_0 = Nbr2[0];
long Nbr2_1 = Nbr2[1];
long Nbr2_2 = Nbr2[2];
long Nbr2_3 = Nbr2[3];
long Nbr2_4 = Nbr2[4];
long Nbr2_5 = Nbr2[5];
for (int i=0; i<6; i++)
{
Pr = (Nbr = Nbr1[i]) * Nbr2_0 + Prod0;
MontDig = ((int) Pr * MontgomeryMultN) & 0x7FFFFFFFL;
Prod0 = (Pr = ((MontDig * TestNbr0 + Pr) >>> 31) +
MontDig * TestNbr1 + Nbr * Nbr2_1 + Prod1) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >>> 31) +
MontDig * TestNbr2 + Nbr * Nbr2_2 + Prod2) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >>> 31) +
MontDig * TestNbr3 + Nbr * Nbr2_3 + Prod3) & 0x7FFFFFFFL;
Prod3 = (Pr = (Pr >>> 31) +
MontDig * TestNbr4 + Nbr * Nbr2_4 + Prod4) & 0x7FFFFFFFL;
Prod4 = (Pr = (Pr >>> 31) +
MontDig * TestNbr5 + Nbr * Nbr2_5 + Prod5) & 0x7FFFFFFFL;
Prod5 = Pr >>> 31;
}
if (Prod5 > TestNbr5
|| Prod5 == TestNbr5
&& (Prod4 > TestNbr4
|| Prod4 == TestNbr4
&& (Prod3 > TestNbr3
|| Prod3 == TestNbr3
&& (Prod2 > TestNbr2
|| Prod2 == TestNbr2
&& (Prod1 > TestNbr1
|| Prod1 == TestNbr1
&& (Prod0 >= TestNbr0))))))
{
Prod0 = (Pr = Prod0 - TestNbr0) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >> 31) + Prod1 - TestNbr1) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >> 31) + Prod2 - TestNbr2) & 0x7FFFFFFFL;
Prod3 = (Pr = (Pr >> 31) + Prod3 - TestNbr3) & 0x7FFFFFFFL;
Prod4 = (Pr = (Pr >> 31) + Prod4 - TestNbr4) & 0x7FFFFFFFL;
Prod5 = ((Pr >> 31) + Prod5 - TestNbr5) & 0x7FFFFFFFL;
}
Prod[0] = Prod0;
Prod[1] = Prod1;
Prod[2] = Prod2;
Prod[3] = Prod3;
Prod[4] = Prod4;
Prod[5] = Prod5;
}
void MontgomeryMult7(long Nbr1[], long Nbr2[], long Prod[])
{
long Pr, Nbr;
int MontDig;
int Prod0, Prod1, Prod2, Prod3, Prod4, Prod5, Prod6;
Prod0 = Prod1 = Prod2 = Prod3 = Prod4 = Prod5 = Prod6 = 0;
int TestNbr0 = (int)TestNbr[0];
int TestNbr1 = (int)TestNbr[1];
int TestNbr2 = (int)TestNbr[2];
int TestNbr3 = (int)TestNbr[3];
int TestNbr4 = (int)TestNbr[4];
int TestNbr5 = (int)TestNbr[5];
int TestNbr6 = (int)TestNbr[6];
int Nbr2_0 = (int)Nbr2[0];
int Nbr2_1 = (int)Nbr2[1];
int Nbr2_2 = (int)Nbr2[2];
int Nbr2_3 = (int)Nbr2[3];
int Nbr2_4 = (int)Nbr2[4];
int Nbr2_5 = (int)Nbr2[5];
int Nbr2_6 = (int)Nbr2[6];
int Sum;
for (int i=0; i<7; i++)
{
Pr = (Nbr = Nbr1[i]) * (long)Nbr2_0 + Prod0;
MontDig = ((int) Pr * (int)MontgomeryMultN) & 0x7FFFFFFF;
Prod0 = (int)(Pr = ((MontDig * (long)TestNbr0 + Pr) >>> 31) +
MontDig * (long)TestNbr1 + Nbr * (long)Nbr2_1 + Prod1) & 0x7FFFFFFF;
Prod1 = (int)(Pr = (Pr >>> 31) +
MontDig * (long)TestNbr2 + Nbr * (long)Nbr2_2 + Prod2) & 0x7FFFFFFF;
Prod2 = (int)(Pr = (Pr >>> 31) +
MontDig * (long)TestNbr3 + Nbr * (long)Nbr2_3 + Prod3) & 0x7FFFFFFF;
Prod3 = (int)(Pr = (Pr >>> 31) +
MontDig * (long)TestNbr4 + Nbr * (long)Nbr2_4 + Prod4) & 0x7FFFFFFF;
Prod4 = (int)(Pr = (Pr >>> 31) +
MontDig * (long)TestNbr5 + Nbr * (long)Nbr2_5 + Prod5) & 0x7FFFFFFF;
Prod5 = (int)(Pr = (Pr >>> 31) +
MontDig * (long)TestNbr6 + Nbr * (long)Nbr2_6 + Prod6) & 0x7FFFFFFF;
Prod6 = (int)(Pr >>> 31);
}
if (Prod6 > TestNbr6
|| Prod6 == TestNbr6
&& (Prod5 > TestNbr5
|| Prod5 == TestNbr5
&& (Prod4 > TestNbr4
|| Prod4 == TestNbr4
&& (Prod3 > TestNbr3
|| Prod3 == TestNbr3
&& (Prod2 > TestNbr2
|| Prod2 == TestNbr2
&& (Prod1 > TestNbr1
|| Prod1 == TestNbr1
&& (Prod0 >= TestNbr0)))))))
{
Prod0 = (Sum = Prod0 - TestNbr0) & 0x7FFFFFFF;
Prod1 = (Sum = (Sum >> 31) + (Prod1 - TestNbr1)) & 0x7FFFFFFF;
Prod2 = (Sum = (Sum >> 31) + (Prod2 - TestNbr2)) & 0x7FFFFFFF;
Prod3 = (Sum = (Sum >> 31) + (Prod3 - TestNbr3)) & 0x7FFFFFFF;
Prod4 = (Sum = (Sum >> 31) + (Prod4 - TestNbr4)) & 0x7FFFFFFF;
Prod5 = (Sum = (Sum >> 31) + (Prod5 - TestNbr5)) & 0x7FFFFFFF;
Prod6 = ((Sum >> 31) + (Prod6 - TestNbr6)) & 0x7FFFFFFF;
}
Prod[0] = Prod0;
Prod[1] = Prod1;
Prod[2] = Prod2;
Prod[3] = Prod3;
Prod[4] = Prod4;
Prod[5] = Prod5;
Prod[6] = Prod6;
}
void MontgomeryMult8(long Nbr1[], long Nbr2[], long Prod[])
{
long Pr, Nbr, MontDig;
long Prod0, Prod1, Prod2, Prod3, Prod4, Prod5, Prod6, Prod7;
Prod0 = Prod1 = Prod2 = Prod3 = Prod4 = Prod5 = Prod6 = Prod7 = 0;
long TestNbr0 = TestNbr[0];
long TestNbr1 = TestNbr[1];
long TestNbr2 = TestNbr[2];
long TestNbr3 = TestNbr[3];
long TestNbr4 = TestNbr[4];
long TestNbr5 = TestNbr[5];
long TestNbr6 = TestNbr[6];
long TestNbr7 = TestNbr[7];
long Nbr2_0 = Nbr2[0];
long Nbr2_1 = Nbr2[1];
long Nbr2_2 = Nbr2[2];
long Nbr2_3 = Nbr2[3];
long Nbr2_4 = Nbr2[4];
long Nbr2_5 = Nbr2[5];
long Nbr2_6 = Nbr2[6];
long Nbr2_7 = Nbr2[7];
for (int i=0; i<8; i++)
{
Pr = (Nbr = Nbr1[i]) * Nbr2_0 + Prod0;
MontDig = ((int) Pr * MontgomeryMultN) & 0x7FFFFFFFL;
Prod0 = (Pr = ((MontDig * TestNbr0 + Pr) >>> 31) +
MontDig * TestNbr1 + Nbr * Nbr2_1 + Prod1) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >>> 31) +
MontDig * TestNbr2 + Nbr * Nbr2_2 + Prod2) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >>> 31) +
MontDig * TestNbr3 + Nbr * Nbr2_3 + Prod3) & 0x7FFFFFFFL;
Prod3 = (Pr = (Pr >>> 31) +
MontDig * TestNbr4 + Nbr * Nbr2_4 + Prod4) & 0x7FFFFFFFL;
Prod4 = (Pr = (Pr >>> 31) +
MontDig * TestNbr5 + Nbr * Nbr2_5 + Prod5) & 0x7FFFFFFFL;
Prod5 = (Pr = (Pr >>> 31) +
MontDig * TestNbr6 + Nbr * Nbr2_6 + Prod6) & 0x7FFFFFFFL;
Prod6 = (Pr = (Pr >>> 31) +
MontDig * TestNbr7 + Nbr * Nbr2_7 + Prod7) & 0x7FFFFFFFL;
Prod7 = Pr >>> 31;
}
if (Prod7 > TestNbr7
|| Prod7 == TestNbr7
&& (Prod6 > TestNbr6
|| Prod6 == TestNbr6
&& (Prod5 > TestNbr5
|| Prod5 == TestNbr5
&& (Prod4 > TestNbr4
|| Prod4 == TestNbr4
&& (Prod3 > TestNbr3
|| Prod3 == TestNbr3
&& (Prod2 > TestNbr2
|| Prod2 == TestNbr2
&& (Prod1 > TestNbr1
|| Prod1 == TestNbr1
&& (Prod0 >= TestNbr0))))))))
{
Prod0 = (Pr = Prod0 - TestNbr0) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >> 31) + Prod1 - TestNbr1) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >> 31) + Prod2 - TestNbr2) & 0x7FFFFFFFL;
Prod3 = (Pr = (Pr >> 31) + Prod3 - TestNbr3) & 0x7FFFFFFFL;
Prod4 = (Pr = (Pr >> 31) + Prod4 - TestNbr4) & 0x7FFFFFFFL;
Prod5 = (Pr = (Pr >> 31) + Prod5 - TestNbr5) & 0x7FFFFFFFL;
Prod6 = (Pr = (Pr >> 31) + Prod6 - TestNbr6) & 0x7FFFFFFFL;
Prod7 = ((Pr >> 31) + Prod7 - TestNbr7) & 0x7FFFFFFFL;
}
Prod[0] = Prod0;
Prod[1] = Prod1;
Prod[2] = Prod2;
Prod[3] = Prod3;
Prod[4] = Prod4;
Prod[5] = Prod5;
Prod[6] = Prod6;
Prod[7] = Prod7;
}
void MontgomeryMult9(long Nbr1[], long Nbr2[], long Prod[])
{
long Pr, Nbr, MontDig;
long Prod0, Prod1, Prod2, Prod3, Prod4, Prod5, Prod6, Prod7, Prod8;
Prod0 =
Prod1 = Prod2 = Prod3 = Prod4 = Prod5 = Prod6 = Prod7 = Prod8 = 0;
long TestNbr0 = TestNbr[0];
long TestNbr1 = TestNbr[1];
long TestNbr2 = TestNbr[2];
long TestNbr3 = TestNbr[3];
long TestNbr4 = TestNbr[4];
long TestNbr5 = TestNbr[5];
long TestNbr6 = TestNbr[6];
long TestNbr7 = TestNbr[7];
long TestNbr8 = TestNbr[8];
long Nbr2_0 = Nbr2[0];
long Nbr2_1 = Nbr2[1];
long Nbr2_2 = Nbr2[2];
long Nbr2_3 = Nbr2[3];
long Nbr2_4 = Nbr2[4];
long Nbr2_5 = Nbr2[5];
long Nbr2_6 = Nbr2[6];
long Nbr2_7 = Nbr2[7];
long Nbr2_8 = Nbr2[8];
for (int i=0; i<9; i++)
{
Pr = (Nbr = Nbr1[i]) * Nbr2_0 + Prod0;
MontDig = ((int) Pr * MontgomeryMultN) & 0x7FFFFFFFL;
Prod0 = (Pr = ((MontDig * TestNbr0 + Pr) >>> 31) +
MontDig * TestNbr1 + Nbr * Nbr2_1 + Prod1) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >>> 31) +
MontDig * TestNbr2 + Nbr * Nbr2_2 + Prod2) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >>> 31) +
MontDig * TestNbr3 + Nbr * Nbr2_3 + Prod3) & 0x7FFFFFFFL;
Prod3 = (Pr = (Pr >>> 31) +
MontDig * TestNbr4 + Nbr * Nbr2_4 + Prod4) & 0x7FFFFFFFL;
Prod4 = (Pr = (Pr >>> 31) +
MontDig * TestNbr5 + Nbr * Nbr2_5 + Prod5) & 0x7FFFFFFFL;
Prod5 = (Pr = (Pr >>> 31) +
MontDig * TestNbr6 + Nbr * Nbr2_6 + Prod6) & 0x7FFFFFFFL;
Prod6 = (Pr = (Pr >>> 31) +
MontDig * TestNbr7 + Nbr * Nbr2_7 + Prod7) & 0x7FFFFFFFL;
Prod7 = (Pr = (Pr >>> 31) +
MontDig * TestNbr8 + Nbr * Nbr2_8 + Prod8) & 0x7FFFFFFFL;
Prod8 = Pr >>> 31;
}
if (Prod8 > TestNbr8
|| Prod8 == TestNbr8
&& (Prod7 > TestNbr7
|| Prod7 == TestNbr7
&& (Prod6 > TestNbr6
|| Prod6 == TestNbr6
&& (Prod5 > TestNbr5
|| Prod5 == TestNbr5
&& (Prod4 > TestNbr4
|| Prod4 == TestNbr4
&& (Prod3 > TestNbr3
|| Prod3 == TestNbr3
&& (Prod2 > TestNbr2
|| Prod2 == TestNbr2
&& (Prod1 > TestNbr1
|| Prod1 == TestNbr1
&& (Prod0 >= TestNbr0)))))))))
{
Prod0 = (Pr = Prod0 - TestNbr0) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >> 31) + Prod1 - TestNbr1) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >> 31) + Prod2 - TestNbr2) & 0x7FFFFFFFL;
Prod3 = (Pr = (Pr >> 31) + Prod3 - TestNbr3) & 0x7FFFFFFFL;
Prod4 = (Pr = (Pr >> 31) + Prod4 - TestNbr4) & 0x7FFFFFFFL;
Prod5 = (Pr = (Pr >> 31) + Prod5 - TestNbr5) & 0x7FFFFFFFL;
Prod6 = (Pr = (Pr >> 31) + Prod6 - TestNbr6) & 0x7FFFFFFFL;
Prod7 = (Pr = (Pr >> 31) + Prod7 - TestNbr7) & 0x7FFFFFFFL;
Prod8 = ((Pr >> 31) + Prod8 - TestNbr8) & 0x7FFFFFFFL;
}
Prod[0] = Prod0;
Prod[1] = Prod1;
Prod[2] = Prod2;
Prod[3] = Prod3;
Prod[4] = Prod4;
Prod[5] = Prod5;
Prod[6] = Prod6;
Prod[7] = Prod7;
Prod[8] = Prod8;
}
void MontgomeryMult10(long Nbr1[], long Nbr2[], long Prod[])
{
long Pr, Nbr, MontDig;
long Prod0, Prod1, Prod2, Prod3, Prod4, Prod5, Prod6, Prod7, Prod8,
Prod9;
Prod0 = Prod1 =
Prod2 = Prod3 = Prod4 = Prod5 = Prod6 = Prod7 = Prod8 = Prod9 = 0;
long TestNbr0 = TestNbr[0];
long TestNbr1 = TestNbr[1];
long TestNbr2 = TestNbr[2];
long TestNbr3 = TestNbr[3];
long TestNbr4 = TestNbr[4];
long TestNbr5 = TestNbr[5];
long TestNbr6 = TestNbr[6];
long TestNbr7 = TestNbr[7];
long TestNbr8 = TestNbr[8];
long TestNbr9 = TestNbr[9];
long Nbr2_0 = Nbr2[0];
long Nbr2_1 = Nbr2[1];
long Nbr2_2 = Nbr2[2];
long Nbr2_3 = Nbr2[3];
long Nbr2_4 = Nbr2[4];
long Nbr2_5 = Nbr2[5];
long Nbr2_6 = Nbr2[6];
long Nbr2_7 = Nbr2[7];
long Nbr2_8 = Nbr2[8];
long Nbr2_9 = Nbr2[9];
for (int i=0; i<10; i++)
{
Pr = (Nbr = Nbr1[i]) * Nbr2_0 + Prod0;
MontDig = ((int) Pr * MontgomeryMultN) & 0x7FFFFFFFL;
Prod0 = (Pr = ((MontDig * TestNbr0 + Pr) >>> 31) +
MontDig * TestNbr1 + Nbr * Nbr2_1 + Prod1) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >>> 31) +
MontDig * TestNbr2 + Nbr * Nbr2_2 + Prod2) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >>> 31) +
MontDig * TestNbr3 + Nbr * Nbr2_3 + Prod3) & 0x7FFFFFFFL;
Prod3 = (Pr = (Pr >>> 31) +
MontDig * TestNbr4 + Nbr * Nbr2_4 + Prod4) & 0x7FFFFFFFL;
Prod4 = (Pr = (Pr >>> 31) +
MontDig * TestNbr5 + Nbr * Nbr2_5 + Prod5) & 0x7FFFFFFFL;
Prod5 = (Pr = (Pr >>> 31) +
MontDig * TestNbr6 + Nbr * Nbr2_6 + Prod6) & 0x7FFFFFFFL;
Prod6 = (Pr = (Pr >>> 31) +
MontDig * TestNbr7 + Nbr * Nbr2_7 + Prod7) & 0x7FFFFFFFL;
Prod7 = (Pr = (Pr >>> 31) +
MontDig * TestNbr8 + Nbr * Nbr2_8 + Prod8) & 0x7FFFFFFFL;
Prod8 = (Pr = (Pr >>> 31) +
MontDig * TestNbr9 + Nbr * Nbr2_9 + Prod9) & 0x7FFFFFFFL;
Prod9 = Pr >>> 31;
}
if (Prod9 > TestNbr9
|| Prod9 == TestNbr9
&& (Prod8 > TestNbr8
|| Prod8 == TestNbr8
&& (Prod7 > TestNbr7
|| Prod7 == TestNbr7
&& (Prod6 > TestNbr6
|| Prod6 == TestNbr6
&& (Prod5 > TestNbr5
|| Prod5 == TestNbr5
&& (Prod4 > TestNbr4
|| Prod4 == TestNbr4
&& (Prod3 > TestNbr3
|| Prod3 == TestNbr3
&& (Prod2 > TestNbr2
|| Prod2 == TestNbr2
&& (Prod1 > TestNbr1
|| Prod1 == TestNbr1
&& (Prod0 >= TestNbr0))))))))))
{
Prod0 = (Pr = Prod0 - TestNbr0) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >> 31) + Prod1 - TestNbr1) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >> 31) + Prod2 - TestNbr2) & 0x7FFFFFFFL;
Prod3 = (Pr = (Pr >> 31) + Prod3 - TestNbr3) & 0x7FFFFFFFL;
Prod4 = (Pr = (Pr >> 31) + Prod4 - TestNbr4) & 0x7FFFFFFFL;
Prod5 = (Pr = (Pr >> 31) + Prod5 - TestNbr5) & 0x7FFFFFFFL;
Prod6 = (Pr = (Pr >> 31) + Prod6 - TestNbr6) & 0x7FFFFFFFL;
Prod7 = (Pr = (Pr >> 31) + Prod7 - TestNbr7) & 0x7FFFFFFFL;
Prod8 = (Pr = (Pr >> 31) + Prod8 - TestNbr8) & 0x7FFFFFFFL;
Prod9 = ((Pr >> 31) + Prod9 - TestNbr9) & 0x7FFFFFFFL;
}
Prod[0] = Prod0;
Prod[1] = Prod1;
Prod[2] = Prod2;
Prod[3] = Prod3;
Prod[4] = Prod4;
Prod[5] = Prod5;
Prod[6] = Prod6;
Prod[7] = Prod7;
Prod[8] = Prod8;
Prod[9] = Prod9;
}
void MontgomeryMult11(long Nbr1[], long Nbr2[], long Prod[])
{
long Pr, Nbr, MontDig;
long Prod0, Prod1, Prod2, Prod3, Prod4, Prod5, Prod6, Prod7, Prod8,
Prod9, Prod10;
Prod0 = Prod1 = Prod2 = Prod3 =
Prod4 = Prod5 = Prod6 = Prod7 = Prod8 = Prod9 = Prod10 = 0;
long TestNbr0 = TestNbr[0];
long TestNbr1 = TestNbr[1];
long TestNbr2 = TestNbr[2];
long TestNbr3 = TestNbr[3];
long TestNbr4 = TestNbr[4];
long TestNbr5 = TestNbr[5];
long TestNbr6 = TestNbr[6];
long TestNbr7 = TestNbr[7];
long TestNbr8 = TestNbr[8];
long TestNbr9 = TestNbr[9];
long TestNbr10 = TestNbr[10];
long Nbr2_0 = Nbr2[0];
long Nbr2_1 = Nbr2[1];
long Nbr2_2 = Nbr2[2];
long Nbr2_3 = Nbr2[3];
long Nbr2_4 = Nbr2[4];
long Nbr2_5 = Nbr2[5];
long Nbr2_6 = Nbr2[6];
long Nbr2_7 = Nbr2[7];
long Nbr2_8 = Nbr2[8];
long Nbr2_9 = Nbr2[9];
long Nbr2_10 = Nbr2[10];
for (int i=0; i<11; i++)
{
Pr = (Nbr = Nbr1[i]) * Nbr2_0 + Prod0;
MontDig = ((int) Pr * MontgomeryMultN) & 0x7FFFFFFFL;
Prod0 = (Pr = ((MontDig * TestNbr0 + Pr) >>> 31) +
MontDig * TestNbr1 + Nbr * Nbr2_1 + Prod1) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >>> 31) +
MontDig * TestNbr2 + Nbr * Nbr2_2 + Prod2) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >>> 31) +
MontDig * TestNbr3 + Nbr * Nbr2_3 + Prod3) & 0x7FFFFFFFL;
Prod3 = (Pr = (Pr >>> 31) +
MontDig * TestNbr4 + Nbr * Nbr2_4 + Prod4) & 0x7FFFFFFFL;
Prod4 = (Pr = (Pr >>> 31) +
MontDig * TestNbr5 + Nbr * Nbr2_5 + Prod5) & 0x7FFFFFFFL;
Prod5 = (Pr = (Pr >>> 31) +
MontDig * TestNbr6 + Nbr * Nbr2_6 + Prod6) & 0x7FFFFFFFL;
Prod6 = (Pr = (Pr >>> 31) +
MontDig * TestNbr7 + Nbr * Nbr2_7 + Prod7) & 0x7FFFFFFFL;
Prod7 = (Pr = (Pr >>> 31) +
MontDig * TestNbr8 + Nbr * Nbr2_8 + Prod8) & 0x7FFFFFFFL;
Prod8 = (Pr = (Pr >>> 31) +
MontDig * TestNbr9 + Nbr * Nbr2_9 + Prod9) & 0x7FFFFFFFL;
Prod9 = (Pr = (Pr >>> 31) +
MontDig * TestNbr10 + Nbr * Nbr2_10 + Prod10) & 0x7FFFFFFFL;
Prod10 = Pr >>> 31;
}
if (Prod10 > TestNbr10
|| Prod10 == TestNbr10
&& (Prod9 > TestNbr9
|| Prod9 == TestNbr9
&& (Prod8 > TestNbr8
|| Prod8 == TestNbr8
&& (Prod7 > TestNbr7
|| Prod7 == TestNbr7
&& (Prod6 > TestNbr6
|| Prod6 == TestNbr6
&& (Prod5 > TestNbr5
|| Prod5 == TestNbr5
&& (Prod4 > TestNbr4
|| Prod4 == TestNbr4
&& (Prod3 > TestNbr3
|| Prod3 == TestNbr3
&& (Prod2 > TestNbr2
|| Prod2 == TestNbr2
&& (Prod1 > TestNbr1
|| Prod1 == TestNbr1
&& (Prod0 >= TestNbr0)))))))))))
{
Prod0 = (Pr = Prod0 - TestNbr0) & 0x7FFFFFFFL;
Prod1 = (Pr = (Pr >> 31) + Prod1 - TestNbr1) & 0x7FFFFFFFL;
Prod2 = (Pr = (Pr >> 31) + Prod2 - TestNbr2) & 0x7FFFFFFFL;
Prod3 = (Pr = (Pr >> 31) + Prod3 - TestNbr3) & 0x7FFFFFFFL;
Prod4 = (Pr = (Pr >> 31) + Prod4 - TestNbr4) & 0x7FFFFFFFL;
Prod5 = (Pr = (Pr >> 31) + Prod5 - TestNbr5) & 0x7FFFFFFFL;
Prod6 = (Pr = (Pr >> 31) + Prod6 - TestNbr6) & 0x7FFFFFFFL;
Prod7 = (Pr = (Pr >> 31) + Prod7 - TestNbr7) & 0x7FFFFFFFL;
Prod8 = (Pr = (Pr >> 31) + Prod8 - TestNbr8) & 0x7FFFFFFFL;
Prod9 = (Pr = (Pr >> 31) + Prod9 - TestNbr9) & 0x7FFFFFFFL;
Prod10 = ((Pr >> 31) + Prod10 - TestNbr10) & 0x7FFFFFFFL;
}
Prod[0] = Prod0;
Prod[1] = Prod1;
Prod[2] = Prod2;
Prod[3] = Prod3;
Prod[4] = Prod4;
Prod[5] = Prod5;
Prod[6] = Prod6;
Prod[7] = Prod7;
Prod[8] = Prod8;
Prod[9] = Prod9;
Prod[10] = Prod10;
}
void LargeMontgomeryMult(long Nbr1[], long Nbr2[], long Prod[])
{
long Pr, Nbr, MontDig;
long Prod0, Prod1, Prod2, Prod3, Prod4, Prod5, Prod6, Prod7, Prod8,
Prod9, Prod10;
Prod0 = Prod1 = Prod2 = Prod3 =
Prod4 = Prod5 = Prod6 = Prod7 = Prod8 = Prod9 = Prod10 = 0;
long TestNbr0 = TestNbr[0];
long TestNbr1 = TestNbr[1];
long TestNbr2 = TestNbr[2];
long TestNbr3 = TestNbr[3];
long TestNbr4 = TestNbr[4];
long TestNbr5 = TestNbr[5];
long TestNbr6 = TestNbr[6];
long TestNbr7 = TestNbr[7];
long TestNbr8 = TestNbr[8];
long TestNbr9 = TestNbr[9];
long TestNbr10 = TestNbr[10];
long Nbr2_0 = Nbr2[0];
long Nbr2_1 = Nbr2[1];
long Nbr2_2 = Nbr2[2];
long Nbr2_3 = Nbr2[3];
long Nbr2_4 = Nbr2[4];
long Nbr2_5 = Nbr2[5];
long Nbr2_6 = Nbr2[6];
long Nbr2_7 = Nbr2[7];
long Nbr2_8 = Nbr2[8];
long Nbr2_9 = Nbr2[9];
long Nbr2_10 = Nbr2[10];
int j;
for (j = 11; j < NumberLength; j++)
{
Prod[j] = 0;
}
for (int i=0; i