ellipticcurve.java

factorization.zip

        //
        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) {
            MontgomeryParams.MontgomeryMult(GcdAccumulated, Z, Aux1);
            System.arraycopy(Aux1,0,GcdAccumulated,0,NumberLength);
          }
          else {
            GCD.GcdBigNbr(Z, TestNbr, GD);
            if (BigNumOps.BigNbrAreEqual(GD, BigNbr1) == false) {
              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) {
              MontgomeryParams.MontgomeryMult(GcdAccumulated, Z, Aux1);
              System.arraycopy(Aux1,0,GcdAccumulated,0,NumberLength);
            }
            else {
              GCD.GcdBigNbr(Z, TestNbr, GD);
              if (BigNumOps.BigNbrAreEqual(GD, BigNbr1) == false) {
                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
            Util.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) {
                MontgomeryParams.MontgomeryMult(GcdAccumulated, Z, Aux1);
                System.arraycopy(Aux1,0,GcdAccumulated,0,NumberLength);
              }
              else {
                GCD.GcdBigNbr(Z, TestNbr, GD);
                if (BigNumOps.BigNbrAreEqual(GD, BigNbr1) == false) {
                  break new_curve;
                }
              }
            }
            P += 46200;
          } while (P<L1);
          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, BigNbr1) == false) {
              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
          GCD.ModInvBigNbr(Z, Aux2, TestNbr);
          MontgomeryParams.MontgomeryMult(Aux2, MontgomeryMultAfterInv, Aux1);
          MontgomeryParams.MontgomeryMult(Aux1, X, root[0]);           // root[0] <- X/Z (Q)
          J = 0;
          BigNumOps.AddBigNbrModN(X, Z, Aux1);
          MontgomeryParams.MontgomeryMult(Aux1, Aux1, W1);
          BigNumOps.SubtractBigNbrModN(X, Z, Aux1);
          MontgomeryParams.MontgomeryMult(Aux1, Aux1, W2);
          MontgomeryParams.MontgomeryMult(W1, W2, TX);
          BigNumOps.SubtractBigNbrModN(W1, W2, Aux1);
          MontgomeryParams.MontgomeryMult(Aux1, AA, Aux2);
          BigNumOps.AddBigNbrModN(Aux2, W2, Aux3);
          MontgomeryParams.MontgomeryMult(Aux1, Aux3, TZ);             // (TX:TZ) -> 2Q
          BigNumOps.SubtractBigNbrModN(X, Z, Aux1);
          BigNumOps.AddBigNbrModN(TX, TZ, Aux2);
          MontgomeryParams.MontgomeryMult(Aux1, Aux2, W1);
          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);                // (X:Z) -> 3Q
          for (I=5; I<2310; I+=2) {
            System.arraycopy(X,0,WX,0,NumberLength);
            System.arraycopy(Z,0,WZ,0,NumberLength);
            BigNumOps.SubtractBigNbrModN(X, Z, Aux1);
            BigNumOps.AddBigNbrModN(TX, TZ, Aux2);
            MontgomeryParams.MontgomeryMult(Aux1, Aux2, W1);
            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);           // (X:Z) -> 5Q, 7Q, ...
            if (Pass == 0) {
              MontgomeryParams.MontgomeryMult(GcdAccumulated, Aux1, Aux2);
              System.arraycopy(Aux2,0,GcdAccumulated,0,NumberLength);
            }
            else {
              GCD.GcdBigNbr(Aux1, TestNbr, GD);
              if (BigNumOps.BigNbrAreEqual(GD, BigNbr1) == false) {
                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++;
              GCD.ModInvBigNbr(Z, Aux2, TestNbr);
              MontgomeryParams.MontgomeryMult(Aux2, MontgomeryMultAfterInv, Aux1);
              MontgomeryParams.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
          BigNumOps.AddBigNbrModN(DX, DZ, Aux1);
          MontgomeryParams.MontgomeryMult(Aux1, Aux1, W1);
          BigNumOps.SubtractBigNbrModN(DX, DZ, Aux1);
          MontgomeryParams.MontgomeryMult(Aux1, Aux1, W2);
          MontgomeryParams.MontgomeryMult(W1, W2, X);
          BigNumOps.SubtractBigNbrModN(W1, W2, Aux1);
          MontgomeryParams.MontgomeryMult(Aux1, AA, Aux2);
          BigNumOps.AddBigNbrModN(Aux2, W2, Aux3);
          MontgomeryParams.MontgomeryMult(Aux1, Aux3, Z);
          System.arraycopy(X,0,UX,0,NumberLength);
          System.arraycopy(Z,0,UZ,0,NumberLength);    // (UX:UZ) -> 2310Q
          BigNumOps.AddBigNbrModN(X, Z, Aux1);
          MontgomeryParams.MontgomeryMult(Aux1, Aux1, W1);
          BigNumOps.SubtractBigNbrModN(X, Z, Aux1);
          MontgomeryParams.MontgomeryMult(Aux1, Aux1, W2);
          MontgomeryParams.MontgomeryMult(W1, W2, TX);
          BigNumOps.SubtractBigNbrModN(W1, W2, Aux1);
          MontgomeryParams.MontgomeryMult(Aux1, AA, Aux2);
          BigNumOps.AddBigNbrModN(Aux2, W2, Aux3);
          MontgomeryParams.MontgomeryMult(Aux1, Aux3, TZ);             // (TX:TZ) -> 2*2310Q
          BigNumOps.SubtractBigNbrModN(X, Z, Aux1);
          BigNumOps.AddBigNbrModN(TX, TZ, Aux2);
          MontgomeryParams.MontgomeryMult(Aux1, Aux2, W1);
          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);                // (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) {
                GCD.ModInvBigNbr(UZ, Aux2, TestNbr);
                MontgomeryParams.MontgomeryMult(Aux2, MontgomeryMultAfterInv, Aux3);
                MontgomeryParams.MontgomeryMult(UX, Aux3, Aux1);         // Aux1 <- X/Z (2310Q)
                }
              else {
                GCD.ModInvBigNbr(Z, Aux2, TestNbr);
                MontgomeryParams.MontgomeryMult(Aux2, MontgomeryMultAfterInv, Aux3);
                MontgomeryParams.MontgomeryMult(X, Aux3, Aux1);          // Aux1 <- X/Z (3,5,*
                }                                       //              2310Q)

               // Generate sieve
              if (indexM % 10 == 0 || indexM == Qaux) {
                Util.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.
                  }
                BigNumOps.SubtractBigNbrModN(Aux1, root[i], M);
                MontgomeryParams.MontgomeryMult(GcdAccumulated, M, Aux2);
                System.arraycopy(Aux2,0,GcdAccumulated,0,NumberLength);
              }
              if (Pass != 0) {
                GCD.GcdBigNbr(GcdAccumulated, TestNbr, GD);
                if (BigNumOps.BigNbrAreEqual(GD, BigNbr1) == false) {
                  break new_curve;
                }
              }
            }
            if (indexM != 0) {      // Update (X:Z)
              System.arraycopy(X,0,WX,0,NumberLength);
              System.arraycopy(Z,0,WZ,0,NumberLength);
              BigNumOps.SubtractBigNbrModN(X, Z, Aux1);
              BigNumOps.AddBigNbrModN(TX, TZ, Aux2);
              MontgomeryParams.MontgomeryMult(Aux1, Aux2, W1);