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

Reg Quadratic Sieve.

Expand Messages
  • vijaysomu
    I have one question... Suppose if the number of columns in my factorbase is 6 and the number of rows is 5 (FBASE - 1) as assumed by one guy at
    Message 1 of 2 , Nov 30, 2003
    • 0 Attachment
      I have one question...

      Suppose if the number of columns in my factorbase is 6 and the
      number of rows is 5 (FBASE - 1) as assumed by one guy at
      http://groups.yahoo.com/group/primenumbers/message/9449

      Once we do the mod 2 and then transpose the matrix suppose we
      obtained this matrix(6 X 5) :
      0, 0, 1, 1, 0
      1, 1, 0, 1, 0
      1, 1, 1, 0, 1
      1, 0, 0, 0, 0
      1, 0, 0, 0, 0
      1, 1, 1, 0, 1

      We now append the Identity matrix and obtain a 6 X 11 matrix. We
      then do the gauss on this and obtain the following:

      1, 0, 0, 0, 0 : 0, 0, 0, 1, 0, 0
      0, 1, 0, 1, 0 : 0, 1, 0, 1, 0, 0
      0, 0, 1, 1, 0 : 1, 0, 0, 0, 0, 0
      0, 0, 0, 0, 1 : 1, 1, 1, 0, 0, 0
      0, 0, 0, 0, 0 : 0, 0, 0, 1, 1, 0
      0, 0, 0, 0, 0 : 0, 0, 1, 0, 0, 1
      r3 r6

      I need to multiply the values of X_i,B_i for row 3 and row 6 ....but
      my question is, our original matrix is 5 X 6 then how do I find row
      6.

      Then i tried taking number of rows = FBASE +1 this time too I face
      the same problem.
      Its only when I take rows = FBASE , I can find one.

      I am thinking in a wrong way.....

      Thanks,
      -VJ
    • David Cleaver
      ... Heh, looks like I wrote message 9449. ... In that message I wasn t assuming any transpose of the original matrix. The way I was thinking about the problem
      Message 2 of 2 , Nov 30, 2003
      • 0 Attachment
        vijaysomu wrote:
        >
        > I have one question...
        >
        > Suppose if the number of columns in my factorbase is 6 and the
        > number of rows is 5 (FBASE - 1) as assumed by one guy at
        > http://groups.yahoo.com/group/primenumbers/message/9449

        Heh, looks like I wrote message 9449.

        >
        > Once we do the mod 2 and then transpose the matrix suppose we
        > obtained this matrix(6 X 5) :
        > 0, 0, 1, 1, 0
        > 1, 1, 0, 1, 0
        > 1, 1, 1, 0, 1
        > 1, 0, 0, 0, 0
        > 1, 0, 0, 0, 0
        > 1, 1, 1, 0, 1

        In that message I wasn't assuming any transpose of the original matrix.
        The way I was thinking about the problem was to let each column
        represent a factor in your factorbase and to let each row represent the
        exponent vector of your smooth number that you get from your sieving.

        One quick example: say in sieving you get 2^4 * 3^2 * 5^3 * 7^1 * 11^0,
        now, that would give us 5 columns and would represent one row in our
        matrix. In fact, it represents the first row of the above matrix
        because mod 2 it looks like 0, 0, 1, 1, 0.

        Now, in order for the gaussian elimination to have a good chance at
        being successful (and by "successful" I mean having zero filled rows at
        the bottom of our matrix), we need to have more rows than columns. When
        we do the gaussian elimination and get our zero filled rows on the Left
        Hand Side (lhs) of our new matrix, then we look at the Right Hand Side
        (rhs) to see which rows of our original matrix to multiply together to
        get our squares to gcd with our test num.

        So, on the bottom lhs we have a zero row and on the rhs we have:
        0, 0, 1, 0, 0, 1. This means to multiply row 3 and row 6, from the
        original (pre-gauss-elim) matrix, together. Now, what that means is
        that we need to multiply the two numbers together that originally gave
        us row 3 and row 6. When we multiply those two numbers together, we
        will have a square mod N (the number to be factored).

        I hope that helps. If any of it was unclear I'd be happy to clarify.

        -David C.

        >
        > We now append the Identity matrix and obtain a 6 X 11 matrix. We
        > then do the gauss on this and obtain the following:
        >
        > 1, 0, 0, 0, 0 : 0, 0, 0, 1, 0, 0
        > 0, 1, 0, 1, 0 : 0, 1, 0, 1, 0, 0
        > 0, 0, 1, 1, 0 : 1, 0, 0, 0, 0, 0
        > 0, 0, 0, 0, 1 : 1, 1, 1, 0, 0, 0
        > 0, 0, 0, 0, 0 : 0, 0, 0, 1, 1, 0
        > 0, 0, 0, 0, 0 : 0, 0, 1, 0, 0, 1
        > r3 r6
        >
        > I need to multiply the values of X_i,B_i for row 3 and row 6 ....but
        > my question is, our original matrix is 5 X 6 then how do I find row
        > 6.
        >
        > Then i tried taking number of rows = FBASE +1 this time too I face
        > the same problem.
        > Its only when I take rows = FBASE , I can find one.
        >
        > I am thinking in a wrong way.....
        >
        > Thanks,
        > -VJ
      Your message has been successfully submitted and would be delivered to recipients shortly.