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

11246RE: [PrimeNumbers] QS multipliers

Expand Messages
  • Phil Carmody
    Feb 3, 2003
    • 0 Attachment
      --- Paul Leyland <pleyland@...> wrote:
      > In the immortal phrase: "I think you'll find it in Knuth." In particular, Section 4.5.4 (p 383
      > in the 2nd edition) and Ex. 28 in that section.
      > The analysis there is described in terms of optimizing CFRAC but the problem and its solution
      > are exactly the same for QS and its variants.

      Yuppers. I guessed it might be, even though I was aware of the absence of QS.

      Edition 3 has CFRAC on 397-398, but the explanation of the Schroeppel
      multiplier on 400. However, the magical function is left as an exercise
      (Exercise 28).

      Fortunately it's both instructive and easy to write a simply GP script that
      will print out counts of divisors for each residue for each small prime.
      I've done this for my Fermat-with-sieves-alike, and it was a _real_
      eye-opener. (I even found a way to visualise themin 2D, and some very
      interesting (but obvious in retrospect) patterns emerged. I don't remember
      the results, but they were trivial to reproduce so I'm not worried about
      that. (And who needs GP - I did those in Perl!). I'd hope that the (p-1)
      in the formula will drop out immediately from actually counting them!


      Shuttle mystery solved - at this speed, you'd disintegrate too!
      (Yes, the same trustworthy news source as american_geography.jpg)

      Do you Yahoo!?
      Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
    • Show all 4 messages in this topic