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.]
where f(l) = ∑1≤λ≤l2⌈ lg max(l+1–λ,λ)⌉. If l = 2k+θ, where 0 < θ ≤ 1, we have
where the function ...