or display size. Shor's factorization algorithm uses the extended Euclidian algorithm, which is described in Appendix T. It is not a coincidence that, in this appendix, I use the above numbers to illustrate this algorithm principle. The result is d = 6509. Such a big, 13-bit private key is the price for Alice to pay for having chosen a public key as small as e = 5, but this does not affect the generality of the demonstration. Alice then uses her private key to compute the following blocks:2 mod 16 571 = 37046509 mod 16 571 = 9452 m2=c,5,500 mod 16 571 = 7666509 mod 16 571 = 14326 (20.40) m3=c2 mod 16 571 = 4756509 mod 16 571 = 3049 m4=c6509 16 571 3726509 mod 16571 = 14325. Then Alice converts the decimal numbers M1M2M3M4 into four 14-bit binary words, splits each word into two 7-bit groups, and finally translates the resulting blocks into ASCII, which yields and finally displays on Alice's screen: Decimal 9452 14326 13049 14325 Binary 10 01 00 11 10 11 00 11 01 11 11 11 01 10 11 00 10 11 11 10 01 11 01 11 11 11 01 ASCII 1001001 1101100 1101111 1110110 1100101 1111001 1101111 1110101 Plaintext I Bob and Alice both having computers to perform RSA and a connection to the Inter- net, the entire operation of encryption, transmission, and decryption of Bob's message (possibly completed with a few more statements!) took, in fact, milliseconds, as slowed down by the IP routing protocol and other switching bottlenecks. This is the same amount of time that after composing her reply, Alice will take to send Bob a PKC message using Bob's public key and Bob to retrieve into plaintext through his private 20 One may wonder whether it is physically possible to compute numbers as monstrous as 1006 6509 or 1000 6509 exactly with a personal computer or even worse, a pocket calculator. Indeed, if we make the conversion through the formula ax = 10x loga/log 10 we get for the first block 3704650 = n23 228.4794 2 3.01 X 1023228 , namely a number with a whopping 229 digits! But surprisingly enough, such a computation can be performed w