1.2.5 · Testing for primality

A fast passing test is evidence with a boundary.

Count trial divisors, run repeated modular exponentiation checks, and use a Carmichael number to compare probable-prime signals with exact factoring.

Guiding question

What does each primality procedure establish, and what can still remain undecided after it returns true?

Stop trial division once the candidate divisor exceeds the square root boundary
Count tested divisors separately from the final prime or composite answer
Reuse fast modular exponentiation inside a Fermat congruence check
Combine several selected bases into one probable-prime result
Recognize a Carmichael number as a counterexample to naive Fermat confidence

Trial division asks whether any integer from 2 through the square-root boundary divides n. If none does, a larger nontrivial factor cannot exist without a smaller partner. The first program counts only the divisor checks actually performed, so the answer and the amount of finite work remain separate observations.

The Fermat program checks whether a^n is congruent to a modulo n for a selected list of bases. Prime 7 passes, composite 15 fails quickly, and composite 561 passes the three coprime bases while trial division finds a factor. The displayed result therefore records a probable-prime judgment under the selected Fermat procedure.

SICP code527 of 1,048,576 UTF-8 bytes

(begin
  (define divisor-tests 0)
  (define (divides? divisor n)
    (set! divisor-tests (+ divisor-tests 1))
    (= (remainder n divisor) 0))
  (define (find-divisor n candidate)
    (cond ((> (* candidate candidate) n) n)
          ((divides? candidate n) candidate)
          (else (find-divisor n (+ candidate 1)))))
  (define (measure n)
    (set! divisor-tests 0)
    (let ((divisor (find-divisor n 2)))
      (list n divisor (= n divisor) divisor-tests)))
  (list (measure 29)
        (measure 35)
        (measure 97)))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The trial program returns ((29 29 #t 4) (35 5 #f 4) (97 97 #t 8)). The Fermat comparison returns ((prime-7 #t #t) (composite-15 #f #f) (carmichael-561 #f #t)).

Trace focus

Count each divides? application and locate the point where candidate squared becomes larger than n. In expmod, follow exponent halving and modular reduction. For 561, compare the trial-division path that discovers a factor with the selected Fermat paths that all return true; the trace records those finite bases only.

Try it yourself

Change the program and compare the result.

Add 1105 to the comparison, choose at least three bases coprime to it, and compare the Fermat result with trial division. Then explain how each additional base changes the probable-prime result while trial division supplies an exact factor classification.

Show hint

1105 is another Carmichael number. Keep the selected base list visible in the source and report both procedures separately.

Complete this lesson

0 of 18 lessons complete in this chapter0%