Sorry, my reply is too late.

On Wed, 18 Apr 2001 18:21:10 -0000

Dave

holidaymaker17@... wrote:

> For the formula F(x) = a2x2 + 2abx + c, where b2 - N = a2c, and

> checking over the range x = 0 to x = 2^32-1 ...

2^32-1 is too big.

> First I look for F(n) where it is the product of small primes x one

> large prime P (proved by pseudo-primality testing on a few bases),

>

> For each P, I find the two roots n1,n2 == 0 mod P for F(x),

>

> For n1,n2, then n1+P, n2+P, n1+2P, n2+2P, n1+3P etc I checked F(m)

> where it is product of small primes x P x one other large prime Q

> (again proved by pseudo-primality testing),

>

> Then I scan through the resulting list looking for two results with

> different n and P, and the same Q ...

>

> So I end up with some Partial Relations thus

>

> f ---> some small primes x P1

> g ---> some small primes x P2

> h ---> some small primes x P1 x Q

> j ---> some small primes x P2 x Q

>

> And a bit of work ...

>

> Uf = a2f + b, Vf = a2 x some small primes x P1

> Ug = a2g + b, Vg = a2 x some small primes x P2

> Uh = a2h + b, Vh = a2 x some small primes x P1 x Q

> Uj = a2j + b, Vj = a2 x some small primes x P2 x Q

>

> Then, multiplying the relations together ...

>

> Uf.Uf.Ug.Ug.Uh.Uh.Uj.Uj == a2.a2.a2.a2.lots of small primes

> multiplied together.P1.P2.P1.P2.Q.Q (mod N)

>

<snip>

> I suspect my process of "manufacturing relations" is flawed, can

> anyone advise what I'm doing wrong ?

I suppose that "manufacturing relations" process is not good

and the size of factor base is too small.

>From my experience, you got many trivial relations or same relations.

Trivail relation means that Uf.Uf.Ug.Ug.Uh.Uh.Uj.Uj itself is a

perfect square number. It is not useful and not to be included in

the matrix, because it is a zero vector.

In case that the size of factor base is small, it is likely that

"manufacturing relations" makes many trivial relations or same

relations. Check the matrix constructed from the fully factored

relations, and compute its rank. Probably the rank of matrix is

small. In this case, the solition gained by the elimination does not

yield any factor of N.

It is better to merge realtions which represent the same integer.

Satoshi TOMABECHI