## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required