primechecker.java

factorization.zip

            else {
              if (K == 1) {
                BigNumOps.MultBigNbrByLongModN( MontgomeryMultR1,Q,aiJ00[0]); //
                for (J=0; J<Factorizer.NumberLength; J++) {
                  aiJ01[0][J] = MontgomeryMultR1[J];
                }
              }
              else {
                if (K == 2) {
                  if (VK == 1) {
                    for (J=0; J<Factorizer.NumberLength; J++) {
                      aiJ01[0][J] = MontgomeryMultR1[J];
                    }
                  }
                  for (J=0; J<Factorizer.NumberLength; J++) {
                    aiJS[0][J] = aiJ0[0][J];
                    aiJS[1][J] = aiJ0[1][J];
                  }
                  BigNumOps.JS_2(PK, PL, PM, P);
                  if (VK == 3) {
                    for (J=0; J<Factorizer.NumberLength; J++) {
                      aiJ01[0][J] = aiJS[0][J];
                      aiJ01[1][J] = aiJS[1][J];
                    }
                  }
                  BigNumOps.MultBigNbrByLongModN(aiJS[0], Q, aiJ00[0]);
                  BigNumOps.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<Factorizer.NumberLength; J++) {
                          aiJS[I][J] = aiJ1[I][J];
                        }
                      }
                      if (X%8 == 5 || X%8 == 7) {continue;}
                      if (IV == 0) {
                        BigNumOps.LongToBigNbr(X, biExp);
                      }
                      else {
                        BigNumOps.LongToBigNbr(VK * X / PK, biExp);
                        if (VK * X / PK == 0) {continue;}
                      }
                      BigNumOps.JS_E(PK, PL, PM, P);
                      for (I=0; I<PK; I++) {
                        for (J=0; J<Factorizer.NumberLength; J++) {
                          aiJW[I][J] = 0;
                        }
                      }
                      InvX = aiInv[X];
                      for (I=0; I<PK; I++) {
                        J = I*InvX%PK;
                        BigNumOps.AddBigNbrModN(aiJW[J], aiJS[I], aiJW[J]);
                      }
                      BigNumOps.NormalizeJW(PK, PL, PM, P);
                      if (IV == 0) {
                        for (I=0; I<PK; I++) {
                          for (J=0; J<Factorizer.NumberLength; J++) {
                            aiJS[I][J] = aiJ00[I][J];
                          }
                        }
                      }
                      else {
                        for (I=0; I<PK; I++) {
                          for (J=0; J<Factorizer.NumberLength; J++) {
                            aiJS[I][J] = aiJ01[I][J];
                          }
                        }
                      }
                      BigNumOps.NormalizeJS(PK, PL, PM, P);
                      BigNumOps.JS_JW(PK, PL, PM, P);
                      if (IV == 0) {
                        for (I=0; I<PK; I++) {
                          for (J=0; J<Factorizer.NumberLength; J++) {
                            aiJ00[I][J] = aiJS[I][J];
                          }
                        }
                      }
                      else {
                        for (I=0; I<PK; I++) {
                          for (J=0; J<Factorizer.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<Factorizer.NumberLength; J++) {
                        aiJW[I][J] = aiJ2[I][J];
                        aiJS[I][J] = aiJ01[I][J];
                      }
                    }
                    for (; I<PK; I++) {
                      for (J=0; J<Factorizer.NumberLength; J++) {
                        aiJW[I][J] = aiJS[I][J] = 0;
                      }
                    }
                    BigNumOps.JS_JW(PK, PL, PM, P);
                    for (I=0; I<PM; I++) {
                      for (J=0; J<Factorizer.NumberLength; J++) {
                        aiJ01[I][J] = aiJS[I][J];
                      }
                    }
                  }              // end for IV
                }
              }
            }
            for (I=0; I<PL; I++) {
              for (J=0; J<Factorizer.NumberLength; J++) {
                aiJS[I][J] = aiJ00[I][J];
              }
            }
            for (; I<PK; I++) {
              for (J=0; J<Factorizer.NumberLength; J++) {
                aiJS[I][J] = 0;
              }
            }
            BigNumOps.DivBigNbrByLong(Factorizer.TestNbr, PK, biExp);
            BigNumOps.JS_E(PK, PL, PM, P);
            for (I=0; I<PK; I++) {
              for (J=0; J<Factorizer.NumberLength; J++) {
                aiJW[I][J] = 0;
              }
            }
            for (I=0; I<PL; I++) {
              for (J=0; J<PL; J++) {
                //MontgomeryMult(aiJS[I], aiJ01[J], biTmp);
                MontgomeryParams.MontgomeryMult(aiJS[I], aiJ01[J], biTmp);
                BigNumOps.AddBigNbrModN(biTmp, aiJW[(I+J)%PK], aiJW[(I+J)%PK]);
              }
            }
            BigNumOps.NormalizeJW(PK, PL, PM, P);
            MatchingRoot:
              do {
              H = -1;
              W = 0;
              for (I=0; I<PL; I++) {
                if ( BigNumOps.BigNbrIsZero(aiJW[I]) == false) {
                  if (H == -1 &&
                      BigNumOps.BigNbrAreEqual(aiJW[I], MontgomeryMultR1) == true) {
                    H = I;
                  }
                  else {
                    H = -2;
                    BigNumOps.AddBigNbrModN(aiJW[I], MontgomeryMultR1, biTmp);
                    if (BigNumOps.BigNbrIsZero(biTmp)) {W++;}
                  }
                }
              }
              if (H >= 0) {
                break MatchingRoot;
              }
              if (W != P-1) {
                return 1;                 // Not prime
              }
              for (I=0; I<PM; I++) {
                BigNumOps.AddBigNbrModN(aiJW[I], MontgomeryMultR1, biTmp);
                if (BigNumOps.BigNbrIsZero(biTmp) == true) {
                  break;
                }
              }
              if (I == PM) {
                return 1;                 // Not prime
              }
              for (J=1; J<=P-2; J++) {
                BigNumOps.AddBigNbrModN(aiJW[I+J*PM], MontgomeryMultR1, biTmp);
                if (BigNumOps.BigNbrIsZero(biTmp) == false) {
                  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 ((Factorizer.TestNbr[0] & 3) == 1) {
                SW = 1;
              }
              continue;
            }
            // if (Q^((N-1)/2) mod N != N-1), N is not prime.

            BigNumOps.MultBigNbrByLongModN(MontgomeryMultR1, Q, biTmp);
            for (I = 0; I < Factorizer.NumberLength; I++) {
              biR[I] = biTmp[I];
            }
            I = Factorizer.NumberLength - 1;
            Mask = Constants.DosALa31;
            while ((Factorizer.TestNbr[I] & Mask) == 0) {
              Mask /= 2;
              if (Mask == 0) {
                I--;
                Mask = Constants.DosALa31;
              }
            }
            do {
              Mask /= 2;
              if (Mask == 0) {
                I--;
                Mask = Constants.DosALa31;
              }
              //MontgomeryMult(biR,biR,biT);
              MontgomeryParams.MontgomeryMult(biR,biR,biT);

              for (J=0; J<Factorizer.NumberLength; J++) {
                biR[J] = biT[J];
              }
              if ((Factorizer.TestNbr[I] & Mask) != 0) {
                //MontgomeryMult(biR,biTmp,biT);
                MontgomeryParams.MontgomeryMult(biR,biTmp,biT);

                for (J=0; J<Factorizer.NumberLength; J++) {
                  biR[J] = biT[J];
                }
              }
            } while (I>0 || Mask>2);
            BigNumOps.AddBigNbrModN(biR, MontgomeryMultR1, biTmp);

            if (BigNumOps.BigNbrIsZero(biTmp) == false) {
              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 {
                BigNumOps.MultBigNbrByLong(biS, Q, biS);
                U /= Q;
              } while (U%Q == 0);
              continue;          // Retry
            }
            LEVELnow++;
            if (LEVELnow==MAX_LEVEL) {
              return ProbabilisticPrimeTest(N);         // Cannot tell
            }
            T = aiT[LEVELnow];
            NP = aiNP[LEVELnow];
            biS[0] = 2;
            for (J=1; J<Factorizer.NumberLength; J++) {
              biS[J] = 0;
            }
            for (J=0; J<=aiNQ[LEVELnow]; J++) {
              Q = aiQ[J];
              U = T*Q;
              do {
                BigNumOps.MultBigNbrByLong(biS, Q, biS);
                U /= Q;
              } while (U%Q == 0);
              if (BigNumOps.CompareSquare(biS, Factorizer.TestNbr) > 0) {
                TestingQs = J;
                continue MainStart;   // Retry from the beginning
              }
            }                 // end for J
            return ProbabilisticPrimeTest(N);         // Program error
          }                   // end if
          break;
        } while (true);       // end do
      }                      // end for i

      // Final Test

      LengthN = Factorizer.NumberLength;
      for (I=0; I<Factorizer.NumberLength; I++) {
        biN[I] = Factorizer.TestNbr[I];
        Factorizer.TestNbr[I] = biS[I];
        biR[I] = 0;
      }
      while (true) {
        if (Factorizer.TestNbr[Factorizer.NumberLength-1] != 0) {break;}
        Factorizer.NumberLength--;
      }
      Factorizer.dN = (double)Factorizer.TestNbr[Factorizer.NumberLength-1];
      if (Factorizer.NumberLength > 1) {
        Factorizer.dN += (double)Factorizer.TestNbr[Factorizer.NumberLength-2]/Constants.dDosALa32;
      }
      if (Factorizer.NumberLength > 2) {
        Factorizer.dN += (double)Factorizer.TestNbr[Factorizer.NumberLength-3]/Constants.dDosALa64;
      }
      LengthS = Factorizer.NumberLength;
      dS = Factorizer.dN;
      MontgomeryMultR1[0] = 1;
      for (I=1; I<Factorizer.NumberLength; I++) {
        MontgomeryMultR1[I] = 0;
      }

      biR[0] = 1;
      BigNumOps.BigNbrModN(biN, LengthN, biT);            // Compute N mod S
      for (J=1; J<=T; J++) {
        BigNumOps.MultBigNbrModN(biR, biT, biTmp);
        for (i=Factorizer.NumberLength-1; i>0; i--) {
          if (biTmp[i] != 0)
          {
            break;
          }
        }
        if (i==0 && biTmp[0] != 1) {
          return 0;                             // Number is prime
        }
        while (true) {
          if (biTmp[Factorizer.NumberLength-1] != 0) {break;}
          Factorizer.NumberLength--;
        }
        for (I=0; I<Factorizer.NumberLength; I++) {
          Factorizer.TestNbr[I] = biTmp[I];
        }
        Factorizer.dN = (double)Factorizer.TestNbr[Factorizer.NumberLength-1];
        if (Factorizer.NumberLength > 1) {
          Factorizer.dN += (double)Factorizer.TestNbr[Factorizer.NumberLength-2]/Constants.dDosALa32;
        }
        if (Factorizer.NumberLength > 2) {
          Factorizer.dN += (double)Factorizer.TestNbr[Factorizer.NumberLength-3]/Constants.dDosALa64; // DTWO_POWER64;
        }
        for (i=Factorizer.NumberLength-1; i>0; i--) {
          if (Factorizer.TestNbr[i] != biTmp[i]) {
            break;
          }
        }
        if (Factorizer.TestNbr[i] > biTmp[i]) {
          BigNumOps.BigNbrModN(biN, LengthN, biTmp);         // Compute N mod R
          if (BigNumOps.BigNbrIsZero(biTmp) == true) {       // If N is multiple of R..
            return 1;                              // Number is composite
          }
        }
        Factorizer.dN = dS;
        Factorizer.NumberLength = LengthS;
        for (I=0; I<Factorizer.NumberLength; I++) {
          biR[I] = Factorizer.TestNbr[I];
          Factorizer.TestNbr[I] = biS[I];
        }
      }                                       // End for J
      return 0;                                 // Number is prime
    } while (true);
  }

      /**
       * For testing
       */
      public static void main(String[] args) {
            System.gc();

	    PrimeChecker pc = new PrimeChecker();
            int ret = pc.AprtCle(new BigInteger("27014431793413285841747"));

            System.out.println("Prime(0)=" + ret);

//            System.out.println("Ret=" + pc.AprtCle(new BigInteger("128")));
//            System.out.println("Ret=" + pc.AprtCle(new BigInteger("17")));
//            System.out.println("Ret=" + pc.AprtCle(new BigInteger("1734342343")));
            System.gc();

      }

}