Re: [PrimeNumbers] Factoring N with MPQS
- View SourceSorry, 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, and2^32-1 is too big.
> checking over the range x = 0 to x = 2^32-1 ...
> First I look for F(n) where it is the product of small primes x one<snip>
> 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)
> I suspect my process of "manufacturing relations" is flawed, canI suppose that "manufacturing relations" process is not good
> anyone advise what I'm doing wrong ?
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.