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

Re: [PrimeNumbers] Factoring N with MPQS

Expand Messages
  • S.Tomabechi
    Sorry, my reply is too late. On Wed, 18 Apr 2001 18:21:10 -0000 ... 2^32-1 is too big. ... ... I suppose that manufacturing relations process is not
    Message 1 of 2 , May 1, 2001
    View Source
    • 0 Attachment
      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
    Your message has been successfully submitted and would be delivered to recipients shortly.