ABSTRACT
Modern cryptosystems are invariably based on an assumption that some problem is hard. This chapter introduces various problems believed to be “hard,” and presents conjectured one-way functions based on those problems. It also introduces a class of cryptographic hardness assumptions in cyclic groups. The problem of efficiently determining whether a given number is prime has a long history. In the 1970s the first efficient algorithms for testing primality were developed. These algorithms were probabilistic and had the following guarantee: if the input p were a prime number, the algorithm would always output “prime.” A deterministic polynomial-time algorithm for testing primality was demonstrated in a breakthrough result in 2002. The key to the Miller-Rabin algorithm is to find a property that distinguishes primes and composites.
