ellipticcurve.java

factorization.zip

              BigNumOps.AddBigNbrModN(X, Z, Aux1);
              BigNumOps.SubtractBigNbrModN(TX, TZ, Aux2);
              MontgomeryParams.MontgomeryMult(Aux1, Aux2, W2);
              BigNumOps.AddBigNbrModN(W1, W2, Aux1);
              MontgomeryParams.MontgomeryMult(Aux1, Aux1, Aux2);
              MontgomeryParams.MontgomeryMult(Aux2, UZ, X);
              BigNumOps.SubtractBigNbrModN(W1, W2, Aux1);
              MontgomeryParams.MontgomeryMult(Aux1, Aux1, Aux2);
              MontgomeryParams.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 (BigNumOps.BigNbrIsZero(GcdAccumulated)) { // If GcdAccumulated is
              System.arraycopy(Xaux,0,X,0,NumberLength);
              System.arraycopy(Zaux,0,Z,0,NumberLength);
              continue;                        // multiple of TestNbr, continue.
            }
            GCD.GcdBigNbr(GcdAccumulated, TestNbr, GD);
            if (BigNumOps.BigNbrAreEqual(GD, TestNbr) == true) {
              break;
            }
            if (BigNumOps.BigNbrAreEqual(GD, BigNbr1) == false) {
              break new_curve;
            }
            break;
          }
        }                        // end for Pass
      } while (true);            // end curve calculation

    } while (BigNumOps.BigNbrAreEqual(GD, TestNbr) == true);
/* */
    StepECM = 0;                   // do not show pass number on screen

    return BigNumOps.BigIntToBigNbr(GD);
  }


/*********************************************************/
/* 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 NumberLength = Factorizer.NumberLength;

   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)
{
   int NumberLength = Factorizer.NumberLength;

   long [] t = fieldTX;
   long [] u = fieldTZ;
   long [] v = fieldUX;
   long [] w = fieldUZ;
   BigNumOps.SubtractBigNbrModN(x2,z2,v);        // v = x2-z2
   BigNumOps.AddBigNbrModN(x1,z1,w);             // w = x1+z1
   MontgomeryParams.MontgomeryMult(v,w,u);              // u = (x2-z2)*(x1+z1)
   BigNumOps.AddBigNbrModN(x2,z2,w);             // w = x2+z2
   BigNumOps.SubtractBigNbrModN(x1,z1,t);        // t = x1-z1
   MontgomeryParams.MontgomeryMult(t,w,v);              // v = (x2+z2)*(x1-z1)
   BigNumOps.AddBigNbrModN(u,v,t);               // t = 2*(x1*x2-z1*z2)
   MontgomeryParams.MontgomeryMult(t,t,w);              // w = 4*(x1*x2-z1*z2)^2
   BigNumOps.SubtractBigNbrModN(u,v,t);          // t = 2*(x2*z1-x1*z2)
   MontgomeryParams.MontgomeryMult(t,t,v);              // v = 4*(x2*z1-x1*z2)^2
   if (BigNumOps.BigNbrAreEqual(x,x3)) {
     System.arraycopy(x,0,u,0,NumberLength);
     System.arraycopy(w,0,t,0,NumberLength);
     MontgomeryParams.MontgomeryMult(z,t,w);
     MontgomeryParams.MontgomeryMult(v,u,z3);
     System.arraycopy(w,0,x3,0,NumberLength);
   }
   else {
     MontgomeryParams.MontgomeryMult(w,z,x3);           // x3 = 4*z*(x1*x2-z1*z2)^2
     MontgomeryParams.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;
   BigNumOps.AddBigNbrModN(x1,z1,w);             // w = x1+z1
   MontgomeryParams.MontgomeryMult(w,w,u);              // u = (x1+z1)^2
   BigNumOps.SubtractBigNbrModN(x1,z1,w);        // w = x1-z1
   MontgomeryParams.MontgomeryMult(w,w,v);              // v = (x1-z1)^2
   MontgomeryParams.MontgomeryMult(u,v,x2);             // x2 = u*v
   BigNumOps.SubtractBigNbrModN(u,v,w);          // w = u-v = 4*x1*z1
   MontgomeryParams.MontgomeryMult(fieldAA,w,u);
   BigNumOps.AddBigNbrModN(u,v,u);               // u = (v+b*w)
   MontgomeryParams.MontgomeryMult(w,u,z2);             // z2 = (w*u)
}
/* End of code "borrowed" from Paul Zimmermann's ECM4C */

      static String getEllipticCurveTotals() {
            String totals = "";
            if (lModularMult >= 0) {
                  totals = "\nECM: " + (lModularMult - primeModMult) + " modular multiplications\nPrime checking: " +
                        primeModMult + " modular multiplications";
            }
            return totals;
      }
}