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

Re: [PrimeNumbers] Reg Quadratic Sieve.

Expand Messages
  • 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 1 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.