The order of growth of the Fermat test in SICP

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.