timed-prime-test procedure of
exercise 1.22 to use
Fermat method), and test each of the 12 primes you found in that
exercise. Since the Fermat test has Θ(
log n) growth, how
would you expect the time to test primes near 1,000,000 to compare
with the time needed to test primes near 1000? Do your data bear this
out? Can you explain any discrepancy you find?