chapter  6
12 Pages

Pseudoprimes

In this chapter we will see how Fermat’s theorem can be used to show that a number is composite in a way that avoids all searches for factors. The chapter closes with a discussion of the strategies that various computer algebra systems use to check whether a number is prime or composite.