**Chapter 15**
1. The prime number theorem states that the ratio of (n) to n/ln(n) converges to 1 as n approaches infinity. In other words, the percent error goes to zero. What happens to the absolute error?
2. Use Fermat’s test with three different bases (or less, if it fails a test!) to decide if 629 is probably prime.
3. Use Fermat’s test with three different bases (or less, if it fails a test!) to decide if 727 is probably prime.
4. Is 561 prime? Investigate by first applying Fermat’s test with base 2, and then by applying the Miller-Rabin test with base 2.
5. Apply the Miller-Rabin test with two different bases (or just one, if it fails the test!) to decide if 941 is probably prime.
6. Apply the Miller-Rabin test with two different bases (or just one, if it fails the test!) to decide if 1909 is probably prime.
7. The chance of a composite number passing a Miller-Rabin test with a randomly chosen base is less than ¼. How many independent tests should be done to guarantee the chance of the number being composite is less than .000001?
8. Would S = {2, 8, 16, 22, 52, 103, 211, 450} be an acceptable choice for a small knapsack?
9. Would S = {3, 9, 23, 75, 239, 548, 1298, 2459} be an acceptable choice for a small knapsack?
10. Finish enciphering WELL DONE, this chapter’s example for the knapsack cipher.
11. Use the knapsack S = {2, 4, 9, 19, 38, 75, 155, 324, 1255, 2521, 5033, 9514, 20161, 40327, 80644, 161299} with the multiplier m = 5837 and the modulus n = 323760 in the scrambled order 6, 11, 1, 16, 10, 7, 3, 14, 9, 8, 12, 4, 15, 2, 5, 13 to encipher MERKLE, two characters at a time, using the ASCII coding scheme.
12. Use the knapsack S = {3, 5, 9, 20, 41, 83, 165, 333, 672, 1342, 2679, 5353, 10722, 21475, 42907, 86103} with the multiplier m = 8539 and the modulus n = 175326 in the scrambled order 10, 1, 13, 15, 8, 9, 16, 6, 5, 7, 14, 2, 12, 4, 11, 3 to encipher BOMB, two characters at a time, using the ASCII coding scheme.
13. Suppose Alice’s public Elgamal key consists of p = 2741, g = 43, and A = 55. Use the encoding scheme applied in the Elgamal example in this chapter and the key k = 14 to encipher MATH, two letters at a time. If you want to check your work by deciphering, Alice uses a = 25.
14. Suppose Alice’s public Elgamal key consists of p = 2789, g = 65, and A = 2041. Use the encoding scheme applied in the Elgamal example in this chapter and the key k = 23 to encipher CRYPTO, two letters at a time. If you want to check your work by deciphering, Alice uses
a = 19.
15. Decipher the following Elgamal ciphertext by using p = 3019 and a = 13.
First pair of letters: C_{1} = 1093 C_{2} = 633
Second pair of letters: C_{1} = 1093 C_{2} = 2451
Note: C_{1} is the same or both pairs of letter. All this indicates is that the sender used the same key, k, for both.
16. Decipher the Elgamal ciphertext given below by using p = 3083 and a = 37. The message will be the name of a band. If you haven’t heard of this band, it might just look like random letters!
First pair of letters: C_{1} = 376 C_{2} = 3069
Second pair of letters: C_{1} = 445 C_{2} = 2279
Unlike the previous exercise, the C_{1} value changes from the first pair of letters to the second. This indicates that the sender used a different key, for the second pair.
**Share with your friends:** |