📄 ellipticcurve.java
字号:
package javax.math.factorization;
/**
* <p>Title: Factorization Library</p>
* <p>Description: </p>
* <p>Copyright: Copyright (c) 2004</p>
* <p>Company: </p>
* @author Vladimir Silva
* @version 1.0
*/
import java.math.BigInteger;
/**
* I am truly sorry about all this awful spagethi code
* I got it from: Dario Alejandro Alpern (Buenos Aires - Argentina)
* Last updated October 16th, 2003. See http://www.alpertron.com.ar/ECM.HTM
* I am not to blame for its crappy design and implementation, but....
* what the hell. it works!
* I modified it though, to make it less horrible (extracted the pieces i needed)
* If you are a brave soul, try to port this stuff to an object oriented, well-designed
* structure. I tried, but just gave up....
*/
public class EllipticCurve
{
/* ECM limits for 30, 35, ..., 75 digits */
static final int limits[] = {5, 8, 15, 25, 27, 32, 43, 70, 150, 300, 350};
final int SmallPrime[] = new int[670]; /* Primes < 5000 */
final double ProbArray[] = new double[6];
final long GcdAccumulated[] = new long[Constants.MP_INITIAL_SIZE];
long[] fieldAA, fieldTX, fieldTZ, fieldUX, fieldUZ;
long[] fieldAux1, fieldAux2, fieldAux3, fieldAux4;
static int EC; /* Elliptic Curve number */
static int NextEC = -1;
int StepECM;
int indexM,maxIndexM;
int digitsInGroup = 6;
int NbrPrimes, indexPrimes;
// Spaghetti stuff (not mine)...
static long lModularMult;
static long primeModMult;
// why this?...no idea
final long[] BigNbr1 = new long[Constants.MP_INITIAL_SIZE];
/**
*
*/
public EllipticCurve() { // int[] types) {
// Don't know what is this for...
BigNbr1[0] = 1;
for (int i = 1; i < Constants.MP_INITIAL_SIZE; i++) { BigNbr1[i] = 0; }
// Typ = types;
ProbArray[0] = 5E4;
ProbArray[1] = 9.9E5;
ProbArray[2] = 1.5E7;
ProbArray[3] = 1.75E8;
ProbArray[4] = 1.8E9;
ProbArray[5] = 1.53E10;
}
BigInteger fnECM(BigInteger N, int FactorIndex) {
int I,J,Pass,Qaux;
long L1,L2,LS,P,Q,K,IP,Paux=1;
long [] A0 = new long[Constants.MP_INITIAL_SIZE];
long [] A02 = new long[Constants.MP_INITIAL_SIZE];
long [] A03 = new long[Constants.MP_INITIAL_SIZE];
long [] AA = new long[Constants.MP_INITIAL_SIZE];
long [] DX = new long[Constants.MP_INITIAL_SIZE];
long [] DZ = new long[Constants.MP_INITIAL_SIZE];
long [] GD = new long[Constants.MP_INITIAL_SIZE];
long [] M = new long[Constants.MP_INITIAL_SIZE];
long [] N1 = new long[Constants.MP_INITIAL_SIZE];
long [] N2 = new long[Constants.MP_INITIAL_SIZE];
long [] TX = new long[Constants.MP_INITIAL_SIZE]; fieldTX = TX;
long [] TZ = new long[Constants.MP_INITIAL_SIZE]; fieldTZ = TZ;
long [] UX = new long[Constants.MP_INITIAL_SIZE]; fieldUX = UX;
long [] UZ = new long[Constants.MP_INITIAL_SIZE]; fieldUZ = UZ;
long [] W0 = new long[Constants.MP_INITIAL_SIZE];
long [] W1 = new long[Constants.MP_INITIAL_SIZE];
long [] W2 = new long[Constants.MP_INITIAL_SIZE];
long [] W3 = new long[Constants.MP_INITIAL_SIZE];
long [] W4 = new long[Constants.MP_INITIAL_SIZE];
long [] WX = new long[Constants.MP_INITIAL_SIZE];
long [] WZ = new long[Constants.MP_INITIAL_SIZE];
long [] X = new long[Constants.MP_INITIAL_SIZE];
long [] Z = new long[Constants.MP_INITIAL_SIZE];
long [] Aux1 = new long[Constants.MP_INITIAL_SIZE]; fieldAux1 = Aux1;
long [] Aux2 = new long[Constants.MP_INITIAL_SIZE]; fieldAux2 = Aux2;
long [] Aux3 = new long[Constants.MP_INITIAL_SIZE]; fieldAux3 = Aux3;
long [] Aux4 = new long[Constants.MP_INITIAL_SIZE]; fieldAux4 = Aux4;
long [] Xaux = new long[Constants.MP_INITIAL_SIZE];
long [] Zaux = new long[Constants.MP_INITIAL_SIZE];
long [][] root = new long[480][Constants.MP_INITIAL_SIZE];
byte [] Result;
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;
fieldAA = AA;
BigNumOps.BigNbrToBigInt(N);
int NumberLength = Factorizer.NumberLength;
long[] TestNbr = Factorizer.TestNbr;
MontgomeryParams.GetMontgomeryParams();
long[] MontgomeryMultR1 = MontgomeryParams.getR1();
long[] MontgomeryMultR2 = MontgomeryParams.getR2();
long[] MontgomeryMultAfterInv = MontgomeryParams.getAfterInv();
for (I=0; I<NumberLength; I++) {
M[I] = DX[I] = DZ[I] = W3[I] = W4[I] = GD[I] = 0;
}
Util.verbose("Factoring " + N + "(" + N.toString().length()+" digits)");
EC--;
SmallPrime[0] = 2;
P = 3;
indexM = 1;
for (indexM = 1; indexM < SmallPrime.length; indexM++) {
SmallPrime[indexM] = (int)P; /* Store prime */
calculate_new_prime1:
do {
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 */
} while (true);
}
do {
new_curve:
do {
if (NextEC > 0) {
EC = NextEC;
NextEC = -1;
}
else {
EC++;
L1 = N.bitLength();
if (L1 > 100 && L1 < 266) {
if (EC == limits[((int)L1-100)*3/50] && (digitsInGroup & 0x400) == 0) {
EC += Constants.TYPE_SIQS;
return Constants.BigInt1;
}
}
}
Factorizer._types[FactorIndex] = EC; // 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 = "\nLimit (B1="+L1+"; B2="+L2+") Curve ";
UpperLine = "Digits in factor: ";
LowerLine = "Probability: ";
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
Util.verbose(primalityString + EC + "\n" + UpperLine + "\n" + LowerLine);
BigNumOps.LongToBigNbr(2*(EC+1), Aux1);
BigNumOps.LongToBigNbr(3*(EC+1)*(EC+1)-1, Aux2);
GCD.ModInvBigNbr(Aux2, Aux2, TestNbr);
BigNumOps.MultBigNbrModN(Aux1, Aux2, Aux3);
BigNumOps.MultBigNbrModN(Aux3,MontgomeryMultR1,A0);
MontgomeryParams.MontgomeryMult(A0, A0, A02);
MontgomeryParams.MontgomeryMult(A02, A0, A03);
BigNumOps.SubtractBigNbrModN(A03, A0, Aux1);
BigNumOps.MultBigNbrByLongModN(A02, 9, Aux2);
BigNumOps.SubtractBigNbrModN(Aux2, MontgomeryMultR1, Aux2);
MontgomeryParams.MontgomeryMult(Aux1, Aux2, Aux3);
if (BigNumOps.BigNbrIsZero(Aux3)) {
continue;
}
BigNumOps.MultBigNbrByLongModN(A0, 4, Z);
BigNumOps.MultBigNbrByLongModN(A02, 6, Aux1);
BigNumOps.SubtractBigNbrModN(MontgomeryMultR1, Aux1, Aux1);
MontgomeryParams.MontgomeryMult(A02, A02, Aux2);
BigNumOps.MultBigNbrByLongModN(Aux2, 3, Aux2);
BigNumOps.SubtractBigNbrModN(Aux1, Aux2, Aux1);
BigNumOps.MultBigNbrByLongModN(A03, 4, Aux2);
GCD.ModInvBigNbr(Aux2, Aux2, TestNbr);
MontgomeryParams.MontgomeryMult(Aux2, MontgomeryMultAfterInv, Aux3);
MontgomeryParams.MontgomeryMult(Aux1, Aux3, A0);
BigNumOps.AddBigNbrModN(A0, MontgomeryMultR2, Aux1);
BigNumOps.LongToBigNbr(4, Aux2);
GCD.ModInvBigNbr(Aux2, Aux3, TestNbr);
BigNumOps.MultBigNbrModN(Aux3,MontgomeryMultR1,Aux2);
MontgomeryParams.MontgomeryMult(Aux1, Aux2, AA);
BigNumOps.MultBigNbrByLongModN(A02, 3, Aux1);
BigNumOps.AddBigNbrModN(Aux1, MontgomeryMultR1, X);
//
// First step
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -