9

Factorization and primality testing

**9.1 Fermat pseudoprimes**

By a primality test we mean a criterion which, if it is not satisfied, guarantees that a natural number *n* is composite. If the number passes several of these tests – that is, if it satisfies the criterion in each case – then it is likely, though in general not certain, that it is a prime. It turns out that in cryptography it is often enough to know that a number is ‘probably’ a prime and this is where the concept originates. A method which definitely establishes that a number is a prime is called deterministic; otherwise it is called probabilistic.The simplest example of a deterministic method is based on the criterion that *n* be not divisible by any integer between 2 and √*n*; if *n*

Start Free Trial

No credit card required