Exercise 3: sample answer (a) Trial division of 391: 391 / 3 : no (3 + 9 + 1 = 13, not a multiple of 3) 391 / 5 : no (does not end in 0 or 5) 391 / 7 : 7 x 55 = 385, remainder 6, no 391 / 11: 11 x 35 = 385, remainder 6, no 391 / 13: 13 x 30 = 390, remainder 1, no 391 / 17: 17 x 23 = 391, yes The primes are 17 and 23. That took six tries (3, 5, 7, 11, 13, 17). (b) The number of tries grows with the size of the smaller prime. For a number hundreds of digits long, the primes themselves have over a hundred digits, so the number of possible divisors is astronomically large. All the computers on Earth could not finish the search in a human lifetime, and the cleverer known methods are still far too slow. (c) The open padlock is the public key (anyone may use it to lock). The key that opens it is the private key, kept by the owner. The idea removes the requirement that the key be delivered securely in advance, because the lock can be handed out openly and only the unlocking key stays secret.