Overview

Content

Primality: Fermat test, Miller-Rabin test

?Primality: Carmichael numbers, Solovay-Strassen test

?Factorization: rho method, p - 1 method, elliptic curve method

?Discrete logarithm: baby steps - giant steps, Pohlig-Hellman

This chapter is a continuation of the previous one. Here we see that prime numbers can be efficiently generated, while factorization is intractable to date. We also study the discrete logarithm problem. These are basic tools in public-key cryptography.