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

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
• ... 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

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.