TABLE OF CONTENTS This section deals with the prime number generation problem. We first try to distinguish prime numbers from composite ones by primality tests.
We first recall the intuitive method depicted in Fig. 7.1. This algorithm tries to divide the input n by every integer. At each iteration, we perform all possible divisions by integers up to i - 1 and obtain x, thus the remaining factors are between i and x. This method has been optimized: since we know that there is no factor of x between 2 and i - 1, we know that the remaining factors lie between i and 
. Thus we can stop as soon as i > b. The worst case occurs when n is prime or a product of two primes of same size, for which we need 
iterations, which is enormous for typical numbers in cryptography. We notice however that this algorithm does more than expected since it prints the factorization of the input instead of just checking whether or not it is prime. Primality tests are nevertheless easier than factorization as will be shown in Section 7.2.
<b class="bold">Input</b>: an integer <i class="emphasis">n</i><b class="bold">Output</b>: a list of prime numbers whose product is <i class="emphasis">n</i><b class="bold">Complexity</b>: <i class="emphasis">O</i>(<span class="inlinemediaobject"><img alt="Image from book"> border="0"> height="25"> id="IMG_631"> src="https://images.books24x7.com/bookimages/id_16192/fig200_01.jpg"> title=""> width="37"></span>) arithmetic operations 1: <i class="emphasis">b</i> <span class="unicode">?</span> <span class="unicode">?</span><span class="inlinemediaobject"><img alt="Image from book"> border="0"> height="25"> id="IMG_632"> src="https://images.books24x7.com/bookimages/id_16192/fig200_02.jpg"> title=""> width="33"></span><span class="unicode">?</span>,...
