quadraticsieve.java

factorization.zip

          else {
            Divid = 0;
            if (biR[Factorizer.NumberLength-1] < Constants.DosALa31) {    // Positive
              for (index=1; index<NbrPrimes; index++) {
                while (true) {
                  Divisor = prime[index];
                  Rem = 0;
                  switch (Factorizer.NumberLength) {
                    case 6:
                      Rem = (biR5 + (Rem << 32)) % Divisor;
                    case 5:
                      Rem = (biR4 + (Rem << 32)) % Divisor;
                    case 4:
                      Rem = (biR3 + (Rem << 32)) % Divisor;
                    case 3:
                      Rem = (biR2 + (Rem << 32)) % Divisor;
                      Rem = (biR1 + (Rem << 32)) % Divisor;
                      Rem = (biR0 + (Rem << 32)) % Divisor;
                    }
                  if (Rem != 0) {
                    break;
                    }
                  switch (Factorizer.NumberLength) {
                    case 6:
                      Divid = biR5 + (Rem << 32);
                      Rem = Divid % Divisor;
                      biR5 = Divid / Divisor;
                    case 5:
                      Divid = biR4 + (Rem << 32);
                      Rem = Divid % Divisor;
                      biR4 = Divid / Divisor;
                    case 4:
                      Divid = biR3 + (Rem << 32);
                      Rem = Divid % Divisor;
                      biR3 = Divid / Divisor;
                    case 3:
                      Divid = biR2 + (Rem << 32);
                      Rem = Divid % Divisor;
                      biR2 = Divid / Divisor;
                      Divid = biR1 + (Rem << 32);
                      biR1 = Divid / Divisor;
                      biR0 = (biR0 + ((Divid % Divisor) << 32)) / Divisor;
                    }
                  switch (Factorizer.NumberLength) {
                    case 6:
                      cond = (biR5 == 0 && biR4 < Constants.DosALa31);
                      break;
                    case 5:
                      cond = (biR4 == 0 && biR3 < Constants.DosALa31);
                      break;
                    case 4:
                      cond = (biR3 == 0 && biR2 < Constants.DosALa31);
                      break;
                    case 3:
                      cond = (biR2 == 0 && biR1 < Constants.DosALa31);
                      break;
                    }
                  if (cond) {
                    Factorizer.NumberLength--;
                    if (Factorizer.NumberLength == 2) {
                      Divid = (biR1 << 32) | biR0;
                      for (; index<NbrPrimes; index++) {
                        Divisor = prime[index];
                        while (Divid % Divisor == 0) {
                          Divid /= Divisor;
                          }
                        }
                      break;
                      }
                    }
                  }
                }
              }
            else {                                     // Negative
              for (index=1; index<NbrPrimes; index++) {
                while (true) {
                  Divisor = prime[index];
                  Rem = Divisor - 1;
                  switch (Factorizer.NumberLength) {
                    case 6:
                      Rem = (biR5 + (Rem << 32)) % Divisor;
                    case 5:
                      Rem = (biR4 + (Rem << 32)) % Divisor;
                    case 4:
                      Rem = (biR3 + (Rem << 32)) % Divisor;
                    case 3:
                      Rem = (biR2 + (Rem << 32)) % Divisor;
                      Rem = (biR1 + (Rem << 32)) % Divisor;
                      Rem = (biR0 + (Rem << 32)) % Divisor;
                    }
                  if (Rem != 0) {
                    break;
                    }
                  Rem = Divisor - 1;
                  switch (Factorizer.NumberLength) {
                    case 6:
                      Divid = biR5 + (Rem << 32);
                      Rem = Divid % Divisor;
                      biR5 = Divid / Divisor;
                    case 5:
                      Divid = biR4 + (Rem << 32);
                      Rem = Divid % Divisor;
                      biR4 = Divid / Divisor;
                    case 4:
                      Divid = biR3 + (Rem << 32);
                      Rem = Divid % Divisor;
                      biR3 = Divid / Divisor;
                    case 3:
                      Divid = biR2 + (Rem << 32);
                      Rem = Divid % Divisor;
                      biR2 = Divid / Divisor;
                      Divid = biR1 + (Rem << 32);
                      biR1 = Divid / Divisor;
                      biR0 = (biR0 + ((Divid % Divisor) << 32)) / Divisor;
                    }
                  switch (Factorizer.NumberLength) {
                    case 6:
                      cond = (biR5 == Constants.MaxUInt && biR4 >= Constants.DosALa31);
                      break;
                    case 5:
                      cond = (biR4 == Constants.MaxUInt && biR3 >= Constants.DosALa31);
                      break;
                    case 4:
                      cond = (biR3 == Constants.MaxUInt && biR2 >= Constants.DosALa31);
                      break;
                    case 3:
                      cond = (biR2 == Constants.MaxUInt && biR1 >= Constants.DosALa31);
                      break;
                    }
                  if (cond) {
                    Factorizer.NumberLength--;
                    if (Factorizer.NumberLength == 2) {
                      Divid = (biR1 << 32) | biR0;
                      for (; index<NbrPrimes; index++) {
                        Divisor = prime[index];
                        while (Divid % Divisor == 0) {
                          Divid /= Divisor;
                          }
                        }
                      break;
                      }
                    }
                  }
                }
              }
            }                 // end if
          F2 = Factorizer.NumberLength; Factorizer.NumberLength = F;
          if (F2==2 && (Divid==1 || Divid == -1)) { // Smooth relation found.
            if (Divid == -1) {
              rowMatrixB[nbrColumns++] = 0;       // Insert -1 as a factor.
              }
            // factor biT (backup) storing in BiR the square part
            BigNumOps.LongToBigNbr(1, biR);
            while (BigNumOps.RemDivBigNbrByLong(biT, 3*3)==0) {
              BigNumOps.DivBigNbrByLong(biT, 3*3, biT);
              if (BigNumOps.RemDivBigNbrByLong(Factorizer.TestNbr, 3) == 0) {
                BigNumOps.DivBigNbrByLong(biU, 3, biU);
                }
              else {
                BigNumOps.MultBigNbrByLong(biR, 3, biR);
                }
              }
            for (index=5; index<100; index+=4) {
              while (BigNumOps.RemDivBigNbrByLong(biT, index*index)==0) {
                BigNumOps.DivBigNbrByLong(biT, index*index, biT);
                if (BigNumOps.RemDivBigNbrByLong(Factorizer.TestNbr, index) == 0) {
                  BigNumOps.DivBigNbrByLong(biU, index, biU);
                  }
                else {
                  BigNumOps.MultBigNbrByLong(biR, index, biR);
                  }
                }
              index += 2;
              while (BigNumOps.RemDivBigNbrByLong(biR, index*index)==0) {
                BigNumOps.DivBigNbrByLong(biR, index*index, biR);
                if (BigNumOps.RemDivBigNbrByLong(Factorizer.TestNbr, index) == 0) {
                  BigNumOps.DivBigNbrByLong(biU, index, biU);
                  }
                else {
                  BigNumOps.MultBigNbrByLong(biR, index, biR);
                  }
                }
              }
            BigNumOps.MultBigNbrByLong(biS, index2 - SieveLimit, biU);
            BigNumOps.AddBigNbr(biU, biN, biU);
            for (index=1; index<NbrPrimes; index++) {
              expParity = 0;
              D = prime[index];
              while (BigNumOps.RemDivBigNbrByLong(biT, D)==0) {
                BigNumOps.DivBigNbrByLong(biT, D, biT);
                expParity = 1 - expParity;
                if (expParity == 0) {
                  if (BigNumOps.RemDivBigNbrByLong(Factorizer.TestNbr, D) == 0) {
                    BigNumOps.DivBigNbrByLong(biU, D, biU);
                    }
                  else {
                    BigNumOps.MultBigNbrByLong(biR, D, biR);
                    }
                  }
                }
              if (expParity != 0) {
                rowMatrixB[nbrColumns++] = index;
                expParity = 0;
                }
              }

            if (InsertNewRelation(biR, biT, biU, nbrColumns, matrixB, rowMatrixB, pp,
                              vectLeftHandSide)) {
              smoothsFound++;
              pp++;
              ShowSIQSStatus(pp, matrixB.length, startTime);
              if (pp == matrixB.length) {
                i = EraseSingletons(matrixB, vectLeftHandSide, vectExpParity);
                if (i!=0) {
                  Util.verbose(i + " singletons discarded");
                  pp -= i;
                  }
                else {
                  Util.verbose("Solving congruence matrix using Block Lanczos algorithm");
                  if (LinearAlgebraPhase(NbrPrimes, matrixB, prime,
                         biT, biR, biU, vectExpParity, vectLeftHandSide)) {
                    return BigNumOps.BigIntToBigNbr(biT);        // Factor found
                    }
                  else {
                    Util.verbose("Linear dependences were found. Discarding 50 congruences...");
                    pp -= 50;               // Factor not found
                    }
                  }
                }
              }
            continue;                     // Continue sieving
            }
          else {
            if (F2==2 && (Divid<64*FactorBase && Divid > -64*FactorBase)) {
                                               // Partial relation found.
              totalPartials++;
              // Check if there is already another relation with the same
              // factor outside the prime base.
                  // Calculate hash index
              i = matrixPartialHashIndex[(int)(Divid & 0x7FE)/2];
              prev = -1;
              while (i >= 0) {
                if ((int)Divid == matrixPartial[i][0]) {
                                                 // Match of partials.
                  for (index=0; index<Factorizer.NumberLength; index++) {
                    biV[index] = matrixPartial[i][index+2] & Constants.MaxUInt;
                    }
                  BigNumOps.MultBigNbr(biV, biV, biT);
                  BigNumOps.SubtractBigNbr(biT, Factorizer.TestNbr, biT);

                   // factor biT

                  D = (long)matrixPartial[i][0];
                  E = BigNumOps.RemDivBigNbrByLong(Factorizer.TestNbr, D);
                  t1 = D;
                  t2 = E;
                  while (t1 != 0) {
                    t3 = t2%t1;
                    t2 = t1;
                    t1 = t3;
                    }               // t2 = GCD(D, E)
                  BigNumOps.LongToBigNbr(D, biR);
                  if (D<0) {
                    BigNumOps.AddBigNbr(biR, Factorizer.TestNbr, biR);
                    }
                  if (t2 < 0) {t2=-t2;}
                  if (t2 != 1) {
                    BigNumOps.DivBigNbrByLong(Factorizer.TestNbr, t2<0?-t2:t2, biU);
                    BigNumOps.AddBigNbrModN(biR, biU, biR);
                    }
                  if (kk>1) {
                    while (BigNumOps.RemDivBigNbrByLong(biT, kk*kk)==0) {
                      BigNumOps.DivBigNbrByLong(biT, kk*kk, biT);
                      Factorizer.NumberLength--;
                      BigNumOps.MultBigNbrByLongModN(biR, kk, biR);
                      Factorizer.NumberLength++;
                      if (BigNumOps.RemDivBigNbrByLong(Factorizer.TestNbr, kk) == 0) {
                        BigNumOps.DivBigNbrByLong(Factorizer.TestNbr, kk, biU);
                        BigNumOps.AddBigNbrModN(biR, biU, biR);
                        }
                      }
                    }
                  nbrColumns = 0;
                  for (index=1; index<NbrPrimes; index++) {
                    D = prime[index];
                    expParity = 0;
                    while (BigNumOps.RemDivBigNbrByLong(biT, D)==0) {
                      expParity = 1 - expParity;
                      BigNumOps.DivBigNbrByLong(biT, D, biT);
                      if (expParity == 0) {
                        Factorizer.NumberLength--;
                        BigNumOps.MultBigNbrByLongModN(biR, D, biR);
                        Factorizer.NumberLength++;
                        if (BigNumOps.RemDivBigNbrByLong(Factorizer.TestNbr, D) == 0) {
                          BigNumOps.DivBigNbrByLong(Factorizer.TestNbr, D, biU);
                          BigNumOps.AddBigNbrModN(biR, biU, biR);
                          }
                        }
                      }
                    if (expParity != 0) {
                      rowMatrixB[nbrColumns++] = index;
                      }
                    }

                  BigNumOps.MultBigNbrByLong(biS, index2 - SieveLimit, biT);
                  BigNumOps.AddBigNbr(biT, biN, biW);
                  BigNumOps.MultBigNbr(biW, biW, biT);
                  BigNumOps.SubtractBigNbr(biT, Factorizer.TestNbr, biT);

                   // factor biT

                  if (kk>1) {
                    while (BigNumOps.RemDivBigNbrByLong(biT, kk*kk)==0) {
                      BigNumOps.DivBigNbrByLong(biT, kk*kk, biT);
                      Factorizer.NumberLength--;
                      BigNumOps.MultBigNbrByLongModN(biR, kk, biR);
                      Factorizer.NumberLength++;
                      if (BigNumOps.RemDivBigNbrByLong(Factorizer.TestNbr, kk) == 0) {
                        BigNumOps.DivBigNbrByLong(Factorizer.TestNbr, kk, biU);
                        BigNumOps.AddBigNbrModN(biR, biU, biR);
                        }
                      }
                    }
                  for (index=1; index<NbrPrimes; index++) {
                    expParity = 0;
                    D = prime[index];
                    while (BigNumOps.RemDivBigNbrByLong(biT, D)==0) {
                      expParity = 1 - expParity;
                      BigNumOps.DivBigNbrByLong(biT, D, biT);
                      if (expParity == 0) {
                        Factorizer.NumberLength--;
                        BigNumOps.MultBigNbrByLongModN(biR, D, biR);
                        Factorizer.NumberLength++;
                        if (BigNumOps.RemDivBigNbrByLong(Factorizer.TestNbr, D) == 0) {
                          BigNumOps.DivBigNbrByLong(Factorizer.TestNbr, D, biU);