Loading ...
Sorry, an error occurred while loading the content.

Help with Gaussian elimination mod 2 in the Quadratic Sieve

Expand Messages
  • vijaysomu
    Hi, I am writing a java program to factor large number and I was just wondering if anyone can help me by checking if the code below does the gaussian row
    Message 1 of 11 , Nov 23, 2003
    • 0 Attachment
      Hi,

      I am writing a java program to factor large number and I was just
      wondering if anyone can help me by checking if the code below does
      the gaussian row reduction correctly.

      public void gaussian_elim(int[][] matrix, int rows, int cols)
      {
      int i, j, k, t, nonzero_row, nonzero_col, next_row = 0, piv_row = 0;
      int[] row1 = new int[cols];

      for (i = 0; i < cols; i++)
      {
      for (j = next_row; j < rows; j++)
      {
      if (matrix[j][i] == 1)
      {
      nonzero_col = i;
      nonzero_row = j;


      System.arraycopy(matrix[nonzero_row], 0, row1, 0,cols);
      System.arraycopy(matrix[next_row], 0, matrix
      [nonzero_row], 0, cols);
      System.arraycopy(row1, 0, matrix[next_row], 0, cols);


      for (k = nonzero_row + 1; k < rows; k++)
      {
      if (matrix[k][nonzero_col] == 1)
      {
      for (t = 0; t < cols; t++)
      {
      matrix[k][t] = matrix[k][t] ^ matrix[next_row]
      [t];
      }
      }
      }
      next_row++;
      j = rows;
      }
      }
      }

      for (i = 0; i < rows; i++)
      {
      for (j = i+1; j < cols; j++)
      {
      if(j < rows)
      piv_row = j;

      if (matrix[i][j] == 1)
      {
      matrix[i][j] = matrix[i][j] ^ matrix[piv_row]
      [j];
      }
      }
      }

      for(i = 0; i < rows; i++){
      for(j = 0; j < cols; j++)
      System.out.print(matrix[i][j]);
      System.out.println(" ");
      }
      }


      Thanks for your time and help.
      -VJ
    • elevensmooth
      ... Are you aware of Dario Alejandro Alpern s Java Factoring program? It does algebraic factorization, then Cunningham Lookup, then trial factorization, then
      Message 2 of 11 , Nov 23, 2003
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "vijaysomu" <vijaysomu@y...>
        > I am writing a java program to factor large number

        Are you aware of Dario Alejandro Alpern's Java Factoring program? It
        does algebraic factorization, then Cunningham Lookup, then trial
        factorization, then ECM, and finally, for sufficiently small numbers,
        finishes with SIQS. He's been optimizing the code, so it's fast. It
        handles numbers up to 10,000 digits.

        http://www.alpertron.com.ar/ECM.HTM

        --
        ===========================================================
        ElevenSmooth: Distributed Factoring of 2^3326400-1
        http://www.mersenneforum.org/elevensmooth
      • vijaysomu
        Hi, Thats true but I am writing this as part of my course work and I am supposed to implement Dixon s Quadratic Sieve. Thanks, -VJ ... It ... numbers, ... It
        Message 3 of 11 , Nov 24, 2003
        • 0 Attachment
          Hi,

          Thats true but I am writing this as part of my course work and I am
          supposed to implement Dixon's Quadratic Sieve.

          Thanks,
          -VJ
          --- In primenumbers@yahoogroups.com, "elevensmooth"
          <elevensmooth@y...> wrote:
          > --- In primenumbers@yahoogroups.com, "vijaysomu" <vijaysomu@y...>
          > > I am writing a java program to factor large number
          >
          > Are you aware of Dario Alejandro Alpern's Java Factoring program?
          It
          > does algebraic factorization, then Cunningham Lookup, then trial
          > factorization, then ECM, and finally, for sufficiently small
          numbers,
          > finishes with SIQS. He's been optimizing the code, so it's fast.
          It
          > handles numbers up to 10,000 digits.
          >
          > http://www.alpertron.com.ar/ECM.HTM
          >
          > --
          > ===========================================================
          > ElevenSmooth: Distributed Factoring of 2^3326400-1
          > http://www.mersenneforum.org/elevensmooth
        Your message has been successfully submitted and would be delivered to recipients shortly.