The order of growth of the Fermat test in SICP

Question

The fermat-test procedure presented by Structure and Interpretation of Computer Programs has a theta-of-log(n) order of growth, which has been verified by me and many other people's experiments.

What confuses me is the random primitive procedure in its definition. Does this imply that the order of growth of random is at most theta of log(n)? After some searching work, I'm still not sure whether it's possible to write a pseudorandom number generator whose order of growth is no more than theta of log(n).

Here is the code:

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  ; Wait a second! What's the order of growth of `random`?
  (try-it (+ 1 (random (- n 1)))))

, where expmod has a theta-of-log(n) order of growth:

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m)))) 

Could you explain this to me?

• If such a pseudorandom number generator does exist, please show me how it works.
• If such a pseudorandom number generator does not exist, please tell me how can fermat-test still have a theta-of-log(n) order of growth.

Answer 1

Fermat's Little Theorem reads as follows:

If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.

So the idea here is that given some number n, we choose any number a such that a < n and then we compute the expression aⁿ % n == a. If this expression returns false, then we know that n is not prime. However, if this expression return true, then there's a good chance that n is prime.

From this theorem, we're able to derive the function that you've listed above:

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

In your post, you've made it clear that you understand the Θ(lg n) growth & asymptotic time complexity is derived from the expmod function, so we just need to understand how random works in Scheme to know if its order of growth is constant or not.

In Scheme, you're able to generate pseudorandom numbers using the random function. From the Scheme documentation, we know that

The current implementation is a “subtract-with-carry” random-number generator, based on the algorithm from A New Class of Random Number Generators, George Marsaglia and Arif Zaman, The Annals of Applied Probability, Vol. 1, No. 3, 1991

If you're interested in reading more about this particular implementation, you're more than welcome to read more about them, but the important part here is to understand that we're able to generate pseudorandom numbers in constant time with constant space, therefore making the order of growth is unchanged by this function call.

As a quick aside, if you're genuinely interested in learning more about pseudorandom number generators in particular, the Scheme documentation makes a point to suggest that there are probably better and more efficient generators out there besides its current general purpose algorithm — so you might want to check out other generator algorithms as well.