O'Reilly logo

A Course in Mathematical Cryptography by Gerhard Rosenberger, Martin Kreuzer, Benjamin Fine, Gilbert Baumslag

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

Therefore n − 1 is a sum of an even number of terms of the same parity so n − 1 must be even. It follows that 2p divides n − 1. Hence b2p − 1 is a divisor of bn-1 − 1. However

image

Therefore n is a pseudoprime to the base b proving the theorem. □

Although there are infinitely many pseudoprimes they are not that common. It has been shown for example that there are only 21 853 pseudoprimes to the base 2 among the first 25 000 000 000 integers. Hence there is a good chance that if a number, especially a large number, passes a test as a pseudoprime, then it is really a prime. The question becomes how to make this chance, or probability, precise. Lists ...

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