ntum) factorization algorithm, along with modular-algebra basics shown in Appendix T. The reason for describing PKC and RSA in that earlier chapter is to illustrate that the cryptoalgorithm would be readily "cracked" overnight should, one day, Shor's factorization be successfully implemented in quantum computers. Fortunately for PKC and RSA, such a horizon still lies in the far distant future, but in the timescale of cryptology, how "distant" is that? Here, I assume that the reader is already familiar with PKC and RSA, or will refer back to Chapter 20 and, therefore, I shall only further develop the discussion about factorizing large numbers. The PKC and RSA cryptosystem is, indeed, based on the fact that it is extremely difficult to factorize large numbers. To recall, given a number n, factorization consists of finding the unique set of prime numbers (p1, P2 Pk) whose product p1 X P2 X Pk is equal to N. Note that these prime factors are not generally all different. For instance, the number 1000 is factorized into 2 X 2 2 23 53. We can then use just two sufficiently large and different prime numbers (p, q) to generate a bigger number n = pq, knowing that someone who knows n would have a hard time figuring out the two primes (p,q) and this is basically the essence of the PKC and RSA safety assumption. For instance, consider n = 62 615 533. To find its factorization, we need to divide it by prime numbers, trying them out one after another. In this specific case, the answer is p = 7919 and q = 7907, which are the highest two primes in the first- thousand prime list.' 6 This choice made factorization easy with any pocket calculator. See lists of the first 1000 primes in, for instance: http://primes.utm.edu/lists/small/1000.txt www.math.utah.edu/~pa/math/primelist.html. 25.5 Public-key cryptography and RSA But what about n = 15 773 077? The answer (p = 2383, q = 6619) is less immediate, since it takes 200 division tests to find q in this first-thousand-prime list, but this is still within reach of a home computer havi