Finding large primes

In order to make finding large primes tractable we have to relax our confidence level from "sure" to "with high probability". There exist very efficient probabilistic algorithms for probability testing.

As it is very convenient to code such algorithms in a functional programming language an brief introduction to Scheme was given making it able to read Scheme functions.

It is known from number theory (Fermat's Little Theorem) that: If n is a prime and a is any positive integer less than n, then a raised to the n:th power is congruent to a modulo n. Further, if n is not prime, then in general more than half of the numbers a < n will not satisfy the above relation.

There are numbers, the so called Carmichael numbers (561, 1105,...) that fool the Fermat test. These are extremely rare (255 below 100 000 000), so the test can be considered "safe enough" for random choices of big n.