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

MPQS again (after a few months to think about it...)

Expand Messages
  • holidaymaker17@yahoo.co.uk
    I ve been experimenting with MPQS, and seem to have spotted a disadvantage in the merging of partials and double-partial relations to create full relations.
    Message 1 of 3 , Aug 1, 2001
    • 0 Attachment
      I've been experimenting with MPQS, and seem to have spotted a
      disadvantage in the merging of partials and double-partial relations
      to create full relations. I'd be pleased if you could advise me or
      cast any light on this procedure.

      Here's what I'm doing, just using a single polynomial (effectively
      Dixon)

      N is composite, suspected of being composed of just 2 large primes ...
      S = int(sqrt(N))
      T = int(sqrt(N*2))
      R = (S+1)^2 (mod N)
      A = 1
      B = 2 * S
      C = R - 1 - B

      U(x) = A*x+B
      W(x) = A*A + A*B*x + C

      F is a factor base 2 to 131071 (because I'm using UBASIC, and it's
      built in !!)

      I start with a suspected large prime LP = (T-S), and test if probable
      prime with bases 3 to 19, if not then LP = LP - 1 and try again until
      I found a prime.

      Solve W(x) == 0 mod LP, obtaining two roots x1 and x2. If no roots
      are found, then go back to previous step of LP selection.

      If I got roots, then plug the roots into U(x) and W(x), to arrive at
      two sets of values for U(x), W(x) with the LP common to both W(x).

      U(x1) == W(x1) where W(x1) = some small primes SP1, my large prime LP
      and maybe some other large primes / composites QP1

      U(x2) == W(x2) where W(x2) = some small primes SP2, my large prime LP
      and maybe some other large primes / composites QP2

      Then I look at QP1 and QP2 ...

      If QP1 is 1, then keep.
      If QP1 is a large prime LESS THAN LP, then keep.
      Otherwise reject and go back to LP selection stage above.

      Ditto for QP2 ...

      So if I'm here, I now have the following possibilities ...

      U(x1) * U(x2) == SP1 * SP2 * LP * LP * 1 * 1 ==> whoopee, I got a
      full relation

      U(x1) * U(x2) == SP1 * SP2 * LP * LP * 1 * QP2 ==> okay, I got a
      partial relation with QP1 less than LP

      U(x1) * U(x2) == SP1 * SP2 * LP * LP * QP1 * QP2 ==> hmm, I got a
      double partial relation with QP1 and QP2 less than LP

      As I collect these, full relations I store to disk, and the partials
      and double partials I analyse further substituting each QP1 and QP2
      into LP, and running the above procedures again ... the goal being to
      each time reduce the QP1 and QP2 until they eventually fall within my
      factor base F and become full relations.

      So after a while, I got a disk file of full relations. The magnitude
      of numbers I'm testing mean I don't need any Gaussian or Lanczos
      elimination ... usually I load into a spreadsheet, sort by different
      columns and the potentials make themselves apparent pretty quickly.

      And here in comes the crunch ... combining any two full relations is
      supposed to give a factor in 50% of the cases

      i.e.

      When x2 - y2 = kN, and x <> y mod N, we get a factor
      When x2 - y2 = kN, and x == y mod N, we don't get a factor

      But my test results are leading me to believe that every time I
      combine two partials to make one full relation, or combine two double-
      partials to make one partial relation, effectively I'm again halving
      the change that I will eventually find a factor.

      So if I used 4 sets of partial relations, combine to get 2 full
      relations, then combine to get an x2 and y2, I only have 12.5% chance
      of getting a factor, rather than 50% !!

      Wose still, if I used 8 sets of double-partial relations, combine to
      get 4 partial relations, combine to get 2 full relations, then
      combine to get an x2 and y2, I only have a 0.78125% chance of getting
      a factor !!

      Am I missing something here, or is my evaluation correct. If the
      latter is true then any benefit of using PMPQS or PPMPQS is surely
      outweighed by the fact that the eventual chance of finding a factor
      is not 50% but maybe 12.5% or even as low as 0.78125% ?

      Dave
    • Paul Leyland
      ... It s conventional to divide the quadratic residue by the large prime once relations have been combined in this manner. Divide , of course, means
      Message 2 of 3 , Aug 1, 2001
      • 0 Attachment
        > Am I missing something here, or is my evaluation correct. If the
        > latter is true then any benefit of using PMPQS or PPMPQS is surely
        > outweighed by the fact that the eventual chance of finding a factor
        > is not 50% but maybe 12.5% or even as low as 0.78125% ?

        It's conventional to "divide" the quadratic residue by the large prime
        once relations have been combined in this manner. "Divide", of course,
        means "multiply by the multiplactive inverse". Having performed this
        operation, discard both identical copies of the large prime from the
        combined relation.

        You should find that this returns the probability back to 50%. Think
        about it!


        Paul
      • Satoshi TOMABECHI
        Your claim is that partials and partial-partials yield a little full relations. It is right in a sense. But experiments show that PMPQS or PPMPQS yield more
        Message 3 of 3 , Aug 1, 2001
        • 0 Attachment
          Your claim is that partials and partial-partials yield
          a little full relations. It is right in a sense.
          But experiments show that PMPQS or PPMPQS yield more full relations
          than MPQS for over 70 digits.
          You have to notice that the probability yielding full relations
          >from partials is not lenear to the number of partials.
          Have you ever heard about birthday paradox?

          Satoshi Tomabechi.
        Your message has been successfully submitted and would be delivered to recipients shortly.