- 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 - vijaysomu wrote:
>

Heh, looks like I wrote message 9449.

> 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

>

In that message I wasn't assuming any transpose of the original matrix.

> 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

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