**1.** If *d _{k}* isn’t prime, its prime factors are cast out before

**2.** No; the algorithm would fail if *p*_{t−1} = *p _{t}*, 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.1–11,

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

where the function ...

Start Free Trial

No credit card required