Chapter 4: Number Theory and Cryptography
Q47E
Show that 2821 is a Carmichael number.
Q47SE
The encrypted version of a message is LJMKG MGMXF QEXMW. If it was encrypted using the affine cipher what was the original message?
Q48E
Show that if are distinct primes that satisfy then n is a Carmichael number.
Q48SE
Use the autokey cipher to encrypt the message NOW IS THE TIME TO DECIDE (ignoring spaces) using
a) the keystream with seed X followed by letters of the plaintext.
b) the keystream with seed X followed by letters of the ciphertext.
Q49E
a) Use Exercise 48 to show that every integer of the form , where m is a positive integer and 6m+1, 12m+1, and 18m+1 are all primes, is a Carmichael number.
b) Use part (a) to show that 172, 947, 529 is a Carmichael number.
Q49E
Describe an algorithm that finds the Cantor expansion of an integer.
Q49E
Prove that the product of any three consecutive integers is divisible by 6.
Q49SE
Use the autokey cipher to encrypt the message THE DREAM OF REASON (ignoring spaces) using
a) the keystream with seed X followed by letters of the plaintext.
b) the keystream with seed X followed by letters of the ciphertext.
Q4E
Prove that part \((iii)\)of Theorem \(1\)is true.
Q4E
Another way to resolve collisions in hashing is to use doublehashing. We use an initial hashing function where p is prime. We also use a second hashing function. When a collision occurs, we use a probing sequence
Use the double hashing procedure we have described with
p = 4969 to assign memory locations to files for employees with social security numbers
