SICP: малая теорема Ферма

Кусочек кода с распознаванием простых чисел по Малой Теореме Ферма.

; Разное встроенное
(define (even? x) (= (% x 2)))
(define (square x) (* x x))
(define (prime? p) (= (first (factor p)) p))

; Вычисляет (% (pow a b) p)
(define (expmod a b p)
  (cond ((= b) 1)
        ((even? b) (% (square (expmod a (/ b 2) p)) p))
        (true (% (* a (expmod a (dec b) p)) p))))

; Проверяет число на простоту 1 раз
(define (fermat-test p)
  (let (n (+ (rand (- p 1)) 1))
    (= (expmod n p p) n)))

; Проверяет число на простоту много раз
(define (fast-prime p (n 1))
  (local (f)
    (while (and (set 'f (fermat-test p)) (!= (dec n))))
    f))

; Проверяет число на принадлежность к Кармайкловым Числам.
(define (carmaicl? x)
  (and (not (prime? x))
       (apply and (map (fn (n) (= (expmod n x x) n)) (sequence 1 (- x 1))))))

Функция carmaicl? работает довольно медленно. Чтобы прогнать её на числах от 2 до 5 000 потребовалось несколько минут. При этом на проверку 2х функция затрачивает примерно в 2 раза больше времени, чем на проверку х. То есть, если я правильно понимаю, на проверку диапазона 5k-10k уйдёт в три раза больше времени, чем на проверку диапазона 0k-5k.