O'Reilly logo

A Comprehensive Course in Number Theory by Alan Baker

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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.

Start Free Trial

No credit card required