O'Reilly logo

Art of Computer Programming, Volume 2, The: Seminumerical Algorithms by Donald E. Knuth

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Section 4.5.4

1. If dk isn’t prime, its prime factors are cast out before dk is tried.

2. No; the algorithm would fail if pt−1 = pt, giving “1” as a spurious prime factor.

3. Let P be the product of the first 168 primes. [Note: Although P = 19590 . . . 5910 is a 416-digit number, such a gcd can be computed in much less time than it would take to do 168 divisions, if we just want to test whether or not n is prime.]

4. In the notation of exercise 3.111,

Image

where f(l) = ∑1≤λ≤l2⌈ lg max(l+1–λ,λ)⌉. If l = 2k+θ, where 0 < θ ≤ 1, we have

Image

where the function ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required