RE: [PrimeNumbers] QS multipliers
- --- Paul Leyland <pleyland@...> wrote:
> In the immortal phrase: "I think you'll find it in Knuth." In particular, Section 4.5.4 (p 383Yuppers. I guessed it might be, even though I was aware of the absence of QS.
> 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.
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
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.