Skip to content
Textbook Guides

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition

Solution Manual For Introduction To Cryptography With Coding Theory, 2nd Edition provides the perfect textbook solutions, giving you the help you need to succeed in your studies.

Preview 16 of 181 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    SOLUTIONS MANUAL for INTRODUCTION TO CRYPTOGRAPHY with Coding Theory, 2nd edition Wade Trappe Wireless Information Network Laboratory and the Electrical and Computer Engineering Department Rutgers University Lawrence C. Washington Department of Mathematics University of Maryland August 26, 2005

  2. Page 2
  3. Page 3
    Read page 3 as text

    Contents Exercises Chapter 2 - Exercises 1 Chapter 3 - Exercises 6 Chapter 4 - Exercises 14 Chapter 5 - Exercises 17 Chapter 6 - Exercises 19 Chapter 7 - Exercises 23 Chapter 8 - Exercises 25 Chapter 9 - Exercises 27 Chapter 10 - Exercises 28 Chapter 11 - Exercises 29 Chapter 12 - Exercises 31 Chapter 13 - Exercises 33 Chapter 14 - Exercises 34 Chapter 15 - Exercises 36 Chapter 16 - Exercises 40 Chapter 17 - Exercises 44 Chapter 18 - Exercises 46 -2

  4. Page 4
    Read page 4 as text

    -1 Chapter 19 - Exercises 51 Mathematica problems Chapter 2 52 Chapter 3 63 Chapter 6 66 Chapter 7 72 Chapter 8 74 Chapter 9 75 Chapter 12 78 Chapter 16 79 Chapter 18 81 Maple problems Chapter 2 84 Chapter 3 98 Chapter 6 102 Chapter 7 109 Chapter 8 112 Chapter 9 113 Chapter 12 116 Chapter 16 118 Chapter 18 121

  5. Page 5
    Read page 5 as text

    0 MATLAB problems Chapter 2 124 Chapter 3 147 Chapter 6 151 Chapter 7 161 Chapter 8 164 Chapter 9 165 Chapter 12 167 Chapter 16 169 Chapter 18 174

  6. Page 6
    Read page 6 as text

    Chapter 2 - Exercises 1. Among the shifts of EVIRE , there are two words: arena and river . Therefore, Anthony cannot determine where to meet Caesar. 2. The inverse of 9 mod 26 is 3. Therefore, the decryption function is x = 3( y − 2) = 3 y − 2 (mod 26). Now simply decrypt letter by letter as follows. U = 20 so decrypt U by calculating 3 ∗ 20 − 6 (mod 26) = 2, and so on. The decrypted message is ’cat’. 3. Changing the plaintext to numbers yields 7, 14, 22, 0, 17, 4, 24, 14, 20. Applying 5 x + 7 to each yields 5 · 7 + 7 = 42 ≡ 16 (mod 26), 5 · 14 + 7 = 77 ≡ 25, etc. Changing back to letters yields QZNHOBXZD as the ciphertext. 4. Let mx + n be the encryption function. Since h = 7 and N = 13, we have m · 7 + n ≡ 13 (mod 26). Using the second letters yields m · 0 + n ≡ 14. Therefore n = 14. The first congruence now yields 7 m ≡ − 1 (mod 26). This yields m = 11. The encryption function is therefore 11 x + 14. 5. Let the decryption function be x = ay + b . The first letters tell us that 7 ≡ a · 2 + b (mod 26). The second letters tell us that 0 ≡ a · 17 + b .Subtracting yields 7 ≡ a · ( − 15) ≡ 11 a . Since 11 − 1 ≡ 19 (mod 26), we have a ≡ 19 · 7 ≡ 3 (mod 26). The first congruence now tells us that 7 ≡ 3 · 2 + b , so b = 1. The decryption function is therefore x ≡ 3 y + 1. Applying this to CRWWZ yields happy for the plaintext. 6. Let mx + n be one affine function and ax + b be another. Applying the first then the second yields the function a ( mx + n ) + b = ( am ) x + ( an + b ), which is an affine function. Therefore, successively encrypting with two affine functions is the same as encrypting with a single affine function. There is therefore no advantage of doing double encryption in this case. (Technical point: Since gcd( a, 26) = 1 and gcd( m, 26) = 1, it follows that gcd( am, 26) = 1, so the affine function we obtained is still of the required form.) 7. For an affine cipher mx + n (mod 27), we must have gcd(27 , m ) = 1, and we can always take 1 ≤ m ≤ 27. So we must exclude all multiples of 3, which leaves 18 possibilities for m . All 27 values of n are possible, so we have 18 · 27 = 486 keys. When we work mod 29, all values 1 ≤ m ≤ 28 are allowed, so we have 28 · 29 = 812 keys. 8. (a) In order for α to be valid and lead to a decryption algorithm, we need gcd( α, 30) = 1. The possible values for α are 1 , 7 , 11 , 13 , 17 , 19 , 23 , 29. (b) We need to find two x such that 10 x (mod 30) gives the same value. There are many such possible answers, for example x = 1 and x = 4 will work. 1

  7. Page 7
    Read page 7 as text

    2 This corresponds to the letters ’b’ and ’e’. 9. If x 1 = x 2 +(26 /d ), then αx 1 + β = αx 2 + β +( α/d )26. Since d = gcd( α, 26) divides α , the number α/ 26 is an integer. Therefore ( α/d )26 is a multiple of 26, which means that αx 1 + β ≡ αx 2 + β (mod 26). Therefore x 1 and x 2 encrypt to the same ciphertext, so unique decryption is impossible. 10. (a) In order to find the most probable key length, we write the ciphertext down on two strips and shift the second strip by varying amounts. The shift with the most matches is the most likely key length. As an example, look at the shift by 1: B A B A B A A A B A B A B A B A A A B A * * This has a total of 2 matches. A shift by 2 has 6 matches, while a shift by 3 has 2 matches. Thus, the most likely key length is 2. (b) To decrypt, we use the fact that the key length is 2 and extract off every odd letter to get BBBAB, and then every even letter to get AAAAA. Using a frequency count on each of these yields that a shift of 0 is the most likely scenario for the first character of the Vigenere key, while a shift of 1 is the most likely case for the second character of the key. Thus, the key is AB . Decrypting each subsequence yields BBBAB and BBBBB. Combining them gives the original plaintext BBBBBBABBB. 11. If we look at shifts of 1, 2, and 3 we have 2, 3, and 1 matches. This certainly rules out 3 as the key length, but the key length may be 1 or 2. In the ciphertext, there are 3 A ’s, 5 B ’s, and 2 C ’s. If the key length were 1, this should approximate the frequencies .7, .2, .1 of the plaintext in some order, which is not the case. So we rule out 1 as the key length. Let’s consider a key length of 2. The first, third, fifth, ... letters are ACABA . There are 3 A ’s, 1 B , and 1 C . These frequencies of .6, .2, .2 is a close match to .7, .2, .1 shifted by 0 positions. The first element of the key is probably A . The second, fourth, ... letters of the ciphertext are BBBBC . There are 0 A ’s, 4 B ’s, and 1 C . These frequencies .0, .8, .2 and match .7, .2, .1 with a shift by 1. Therefore the second key element is probably B . Since the results for length 2 match the frequencies most closely, we conclude that the key is probably AB . 12. Since the entries of A i are the same as those in A 0 ( shifted a few places) the two vectors have the same length. Therefore A 0 · A i = | A 0 || A i | cos θ = | A 0 | 2 cos θ. Note that cos θ ≤ 1, and equals 1 exactly when θ = 0. But θ = 0 exactly when the two vectors are equal. So we see that the largest value of the cosine is when A 0 = A i . Therefore the largest value of the dot product is when i = 0. 13. Change YIFZMA to pairs of numbers: (24, 8), (5, 25), (12, 0). Invert the matrix to get N = ( 3 − 13 − 2 9 ) ≡ ( 3 13 24 9 ) (mod 26). Calculate (24 , 8) N = (4 , 20), (5 , 25) N = (17 , 4), (12 , 0) N = (10 , 0). Change back to letters: eureka .

  8. Page 8
    Read page 8 as text

    3 14 . Suppose the encryption matrix M is ( a b c d ) . Change the ciphertext to numbers: (6, 4), (25, 23), (3, 18). Change the plaintext to numbers: (18, 14), (11, 21), (4,3). We know (18 , 14) M ≡ (6 , 4), etc. We’ll use (11 , 21) M ≡ (25 , 23) and (4 , 3) M ≡ (3 , 18) to get equations for a, b, c, d , which are most easily put in matrix form: ( 11 21 4 3 ) ( a b c d ) ≡ ( 25 23 3 18 ) . The inverse of ( 11 21 4 3 ) mod 26 is ( 3 5 22 11 ) . Multiply by this matrix to obtain M = ( a b c d ) ≡ ( 12 3 11 2 ) . 15. Suppose the matrix has the form M = ( α β γ δ ) Then the encryption of a plaintext x = ( b, a ) = (1 , 0) yields ( α, β ). We know this corresponds to HC, and hence α = 7 and β = 2. The second piece of information is that zz encrypts to GT. This corresponds to a plaintext of (25 , 25) or equivalently ( − 1 , − 1). Using this yields − α − γ = 6 and − β − δ = 19. Thus, γ = 13 and δ = 5. 16. (a) The plaintext is (3,14), (13, 19). The ciphertext is (4,11), (13, 8). We have ( 3 14 13 19 ) M ≡ ( 4 11 13 8 ) . The inverse of ( 3 14 13 19 ) mod 26 is ( 19 12 13 3 ) . Multiplying by this inverse yields M ≡ ( 10 9 13 23 ) . (b) We have ( 3 14 13 19 ) M ≡ ( 4 11 13 10 ) . Proceeding as in part (a), we find M ≡ ( 10 19 13 19 ) . 17. Suppose the plaintext is of the form ( x, y ), then the ciphertext is of the form ( x + 3 y, 2 x + 4 y ) (mod 26). There will be many possible plaintexts that will map to the same ciphertext. We will try to make plaintexts that yield a ciphertext of the form (0 , ∗ ). To do so, we will have the relationship x = − 3 y (mod 26). Now we need to find two y values that produce the same 2( − 3 y ) + 4 y = − 2 y (mod 26). If we take y = 4 and y = 17 then we get the same value for − 2 y (mod 26). Thus, (14 , 4) and (1 , 17) are two plaintexts that map to (0 , 18). 18. We will need to use three different plaintexts. First, choose ( x, y ) = (0 , 0). This will produce a ciphertext that is precisely ( e, f ). Next, try ( x, y ) = (1 , 0). This will produce a ciphertext that is ( a, b ) + ( e, f ). We may subtract off ( e, f ) to find ( a, b ). Finally, use ( x, y ) = (0 , 1) to get ( c, d ) + ( e, f ) as the ciphertext. We may subtract off ( e, f ) to get ( c, d ).

  9. Page 9
    Read page 9 as text

    4 19. As is Section 2.11, set up the matrix equation   0 0 1 0 1 1 1 1 1     c 0 c 1 c 2   ≡   1 1 0   . This yields c 0 = 1 , c 1 = 0 , c 2 = 1, so the recurrence is k n +3 ≡ k n + k n +2 . The next four terms of the sequence are 1, 0, 0, 1. 20. The sequence is 1,0,1,0,1,0,1,... . The matrix equation is ( 1 0 0 1 ) ( c 0 c 1 ) ≡ ( 1 0 ) . This yields c 0 = 1 , c 1 = 0, so k n +2 ≡ k n . 21. Set up the matrix equation ( x n x n +1 x n +1 x n +2 ) ( c 0 c 1 ) = ( x n +2 x n +3 ) . Using the values provided, we obtain ( 1 1 1 0 ) ( c 0 c 1 ) = ( 0 2 ) . The inverse of the matrix can be found to be − ( 0 − 1 − 1 1 ) = ( 0 1 1 2 ) (mod 3) Multiplying both sides of by the inverse matrix, yields c 0 = 2 and c 1 = 1. 22. Use x 1 , x 2 and x 3 to solve for c 1 by obtaining c 1 + 2 ≡ 1 (mod 5). Thus, c 1 = 4. Next, use x 2 , x 3 and x 4 to solve for c 0 . We get c 0 + c 1 + 2 (mod 5) ≡ 0, and hence c 0 = 4. 23. The number of seconds in 120 years is 60 × 60 × 24 × 365 × 120 ≈ 3 . 8 × 10 9 . Therefore you need to count 10 100 / (3 . 8 × 10 9 ) ≈ 2 . 6 × 10 9 0 numbers per second! 24. (a) The ciphertext will consist of one letter repeated. However, there is no way of deducing what the key is. (b) The ciphertext will consist of one letter repeated. However, there is no way of deducing what the key is. (c) The ciphertext will consist of a continuous stream of the letter A . This is easy to detect. However, there will be no way to tell what the key is. 25. (a) The ciphertext will correspond to a shifted version of the key word that is repeated many times. The periodic nature of the resulting ciphertext will cause Eve to suspect the plaintext is a single letter, while the period of the repeating ciphertext will correspond to the key length. (b) Using the fact that no English word of length six is the shift of another English word, simply treat the Vigenere key as if it were the plaintext and the

  10. Page 10
    Read page 10 as text

    5 single character plaintext as if it were the shift in a shift cipher. Decrypting can be done by trying all possible shifts of the first six characters of the ciphertext. One of these shifts will be a word that corresponds to the Vigenere key. (c) If we use the method of displacement, then shifting by six will have the highest number of matches. In fact, every place will match up. This will be easy to detect. However, shifting the ciphertext by one place will just yield the amount of matches that occur when the repeated key is shifted by one place. In particular, the key word will most likely not have that many matches with itself when shifted over one place. Similarly for shifts of two, three, four, and five. As a result, other shifts will have a much smaller amount of matches.

  11. Page 11
    Read page 11 as text

    Chapter 3 - Exercises 1. (a) Apply the Euclidean algorithm to 17 and 101: 101 = 5 · 17 + 16 17 = 1 · 16 + 1 . Working back yields 1 = 17 − 16 = 17 − (101 − 5 · 17) = ( − 1) · 101 + 6 · 17. (b) Since − 101+6 · 17 = 1, we have 6 · 17 ≡ 1 (mod 101). Therefore 17 − 1 ≡ 6 (mod 101). 2. (a) Apply the Euclidean algorithm to 7 and 30: 30 = 4 · 7 + 2 7 = 3 · 2 + 1 . Working backwards yields 1 = 7 − 3 · 2 = 7 − 3 · (30 − 4 · 7) = 13 · 7 + ( − 3) · 30. Therefore 13 · 7 ≡ 1 (mod 30), so d = 13. (b) Let c ≡ m 7 (mod 31) be the ciphertext. Claim: c 13 ≡ m (mod 31). Proof: c 1 3 ≡ ( m 7 ) 13 ≡ m 91 ≡ ( m 30 ) 3 m . If m 6 ≡ 0 (mod 31) then m 30 ≡ 1 (mod 31) by Fermat. Then c 13 ≡ 1 3 m ≡ m . If m ≡ 0 (mod 31), then c ≡ m 7 ≡ 0, so c 13 ≡ 0 13 ≡ 0 ≡ m . Therefore c 13 ≡ m for all m . Therefore decryption is performed by raising the ciphertext to the 13th power mod 31. 3. 3. (a) gcd(12 , 236) = 4, so divide both sides by 4 to obtain 3 x ≡ 7 (mod 59). The inverse of 3 mod 59 is 20, so multiply both sides by 20 to obtain x ≡ 140 ≡ 22 (mod 59). This yields x ≡ 22 , 81 , 140 , 199 (mod 236). (b) 30 is not divisible by 4 = gcd(12 , 236), so there are no solutions. 4. (a) 30030 = 116 · 257 + 218 257 = 1 · 218 + 39 218 = 5 · 39 + 23 39 = 1 · 23 + 16 23 = 1 · 16 + 7 16 = 2 · 7 + 2 7 = 3 · 2 + 1 2 = 2 · 1 + 0 . 6

  12. Page 12
    Read page 12 as text

    7 Therefore, gcd(30030 , 257) = 1. (b) If 257 is composite, it is divisible by a prime p ≤ √ 257 = 16 . 03 . . . . The primes satisfying this are exactly the prime factors of 30030. Since the gcd is 1, none of them divide 257, so 257 is prime. 5. (a) 4883 = 1 · 4369 + 514 4369 = 8 ˙ 514 + 257 514 = 2 · 257 + 0 . Therefore, the gcd is 257. (b) We know that both numbers have 257 as a factor. This yields 4883 = 257 · 19 and 4369 = 257 · 17. 6. (a) The first two steps of the Euclidean algorithm are F n = 1 · F n − 1 + F n − 2 F n − 1 = 1 · F n − 2 + F n − 3 . It continues in this way until 2 = 2 · 1 + 1 1 = 1 · 1 + 0 . Therefore, the gcd is 1. (b) 11111111 = 1000 · 11111 + 111 11111 = 100 · 111 + 11 111 = 10 · 11 + 1 11 = 11 · 1 + 0 . Therefore, the gcd is 1. (c) The first step of the Euclidean algorithm is a = 10 F n − 2 · b + c, where c consists of F n − 2 repeated 1’s. Continuing in this way, in each step we divide F j − 1 repeated 1’s into F j repeated 1’s and get a remainder consisting of F j − 2 repeated 1’s. Eventually, we get down to the computations of part (b), and then obtain that the gcd is 1. 7. (a) If ab ≡ 0 (mod p ), then p | ab . By the Corollary on page 64, since p is prime, either p | a or p | b . Therefore, either a ≡ 0 (mod p ) or b ≡ 0 (mod p ). (b) We follow the proof of the Corollary on page 64. Since gcd( a, n ) = 1, there are integers x, y such that ax + ny = 1. Multiply by b to obtain abx + bny = b . Since n | ab , both terms on the left are multiples of n . Therefore n | b . 8. ( x +1)( x − 1) ≡ 0 (mod p ) implies, by 3(a), that either x +1 ≡ 0 (mod p ) or x − 1 ≡ 0 (mod p ). Therefore x ≡ ± 1 (mod p ).

  13. Page 13
    Read page 13 as text

    8 9. One solution is to look at the numbers congruent to 3 (mod 10) until we find one that is 2 (mod 7): 3, 13 ≡ 6, 23 ≡ 2 (mod 7). Therefore x ≡ 23 (mod 70). 10. Suppose there are x people. Then x ≡ 1 (mod 3) , x ≡ 2 (mod 4) , x ≡ 3 (mod 5). The last two congruences combine to x ≡ 18 (mod 20). List the numbers that are 18 (mod 20) until you find one that is 1 (mod 3). The answer is x ≡ 58 (mod 60). 11. If a 6 ≡ 0 (mod p ), then Fermat says that a p − 1 ≡ 1 (mod p ). Multiply by a to get a p ≡ a (mod p ). If a ≡ 0 (mod p ), then a p ≡ 0 p ≡ 0 ≡ a (mod ). Therefore a p ≡ a (mod p ) for all a . 12. By Fermat’s theorem, 2 100 ≡ 1 (mod 101). Therefore, 2 10203 ≡ (2 100 ) 102 2 3 ≡ 1 102 2 3 ≡ 8. Therefore, the remainder is 8. 13. “Last two digits” means we work mod 100. Since φ (100) = 40, Euler’s theorem says that 123 40 ≡ 1 (mod 100). Therefore, 123 562 ≡ (123 40 ) 14 123 2 ≡ 123 2 ≡ 23 2 ≡ 529 ≡ 29. The last two digits are 29. 14. (a) 7 7 ≡ ( − 1) 7 ≡ − 1 ≡ 3 (mod 4). (b) 7 7 = 3 + 4 k for some k . By Euler’s theorem, 7 4 ≡ 1 (mod 10). Therefore, 7 7 7 = 7 3 (7 4 ) k ≡ 7 3 · 1 k ≡ 343 ≡ 3 (mod 10) . The last digit is 3. 15. (a) φ (1) = 1 , φ (2) = 1 , φ (5) = 4 , φ (10) = 4. The sum is 10. (b) φ (1) = 1 , φ (2) = 1 , φ (3)2 , φ (4) = 2 , φ (6) = 2 , φ (12) = 4. The sum is 12. (c) The sum of φ ( d ), for all of the divisors d of n , equals n . 16. (a) Since p ∤ a , Fermat says that a p − 1 ≡ 1 (mod p ). For p = 7, we have a 6 ≡ 1 (mod 7), so a 1 728 ≡ ( a 6 ) 288 ≡ 1 288 ≡ 1 (mod 7). Since 1728 = 12 · 144 and 1728 = 18 · 96, a similar argument works for p = 13 and for p = 19. (b) If p ∤ a , then multiply the result of (a) by a to get a 1729 ≡ a (mod p ). If p | a , then a 1729 and a are both 0 (mod p ), so a 1729 ≡ a in this case, too. (c) Fix a number a . The Chinese Remainder Theorem says that x ≡ a 1729 (mod 7) , x ≡ a 1 729 (mod 13) , x ≡ a 1729 (mod 19) has a unique solution x (mod 1729), since 1729 = 7 · 13 · 19. We know two such solutions: x = a (from part (b) and x = a 1 729 (trivially). Since x is unique mod 1729, we must have a ≡ a 1729 (mod 1729). 17. (a) The powers of 2 mod 11 are 2 , 4 , 8 , 5 , 10 , 9 , 7 , 3 , 6 , 1. This gives all nonzero congruence classes mod 11, so 2 is a primitive root mod 11. (b) The inverse of 3 (mod 10) is 7. We obtain 8 7 ≡ (2 3 ) 7 ≡ 2 21 ≡ (2 10 · 2 1 ≡ 1 · 2 ≡ 2 (mod 11) . Therefore, x = 7. (c) This can be done directly, but here is another way. If c 6 ≡ 0 (mod 11), then c ≡ 2 j for some j . Therefore, c ≡ (8 7 ) j ≡ 8 7 j (mod 11), so c is a power of 8. (d) Write xy = 1 + ( p − 1) k . Then h x ≡ ( g y ) x ≡ g · ( g p − 1 ) k ≡ g · 1 k ≡ g (mod p ) .

  14. Page 14
    Read page 14 as text

    9 (e) Let c be nonzero mod p . Then c ≡ g j (mod p ) for some j , so c ≡ ( h x ) j ≡ h xj (mod p ). Since every nonzero congruence class is a power of h , we have that h is a primitive root mod p . 18. (a) The determinant is 1 · 1 − 1 · 6 = − 5 ≡ 21 (mod 26). The inverse of the determinant is 5 (mod 26). The inverse of the matrix is therefore 1 21 ( 1 − 1 − 6 1 ) ≡ 5 ( 1 − 1 − 6 1 ) ≡ ( 5 21 22 5 ) . (b) The determinant is 1 − b . The matrix is invertible mod 26 exactly when gcd(1 − b, 26) = 1. This happens when 1 − b is odd and not 0 mod 13, so b ≡ 0 , 2 , 4 , 6 , 8 , 10 , 12 , 16 , 18 , 20 , 22 , 24 (mod 26). 19. The determinant is 9 − 35 = − 26. This is divisible by 2 and by 13, so these are the two primes for which the matrix is not invertible mod p . 20. (a) We know a φ ( n ) ≡ 1 (mod n ), by Euler. Since r is smallest, r ≤ φ ( n ). (b) Since a r ≡ 1, we have a m ≡ ( a r ) k ≡ 1 k ≡ 1 (mod n ). (c) By (b), a qr ≡ 1. Therefore, 1 ≡ (by assumption) a t ≡ a qr a s ≡ 1 · a s ≡ a s . (d) Since a s ≡ 1 and r is the smallest positive integer with a r ≡ 1, we must have s = 0. Therefore t = qr , so r | t . (e) By Euler, a φ ( n ) ≡ 1 (mod n ). From part (d) with t = φ ( n ), we obtain ord n ( a ) | φ ( n ). 21. (a) If r divides 600, then r = 2 a · 3 b · 5 c with a ≤ 3 , b ≤ 1 , c ≤ 2. If r < 600, then we cannot have a = 3 , b = 1 , c = 2. If a ≤ 2, then r | 2 2 · 3 · 5 2 = 300. If b = 0 then r | 2 3 · 5 2 = 200. If c ≤ 1 then r | 2 3 · 3 · 5 = 120. (b) From 9(e), we know that ord 601 (7) | 600. If ord 601 (7) < 600, then it divides 300, 200, or 120, by (a). (c) Suppose ord 601 (7) | 300. By 9(b), we must have 7 300 ≡ 1 (mod 601), which is not the case. Therefore, ord 601 (7) ∤ 300. Similarly, ord 601 (7) ∤ 200 and ord 601 (7) ∤ 120. (d) From (b) and (c), we cannot have ord 601 (7) < 600. Since ord 601 (7) ≤ 600 from 9(a), we must have ord 601 (7) = 600. Therefore the numbers 7 j (mod 601), for j = 0 , 1 , . . . , 599 are distinct, so there are 600 of them. This implies that 7 is a primitive root mod 601. (e) Calculate g ( p − 1) /q i (mod p ) for i = 1 , 2 , . . . , s . If each of these is 6 ≡ 1 (mod p ), then g is a primitive root mod p . (Of course, perhaps we should check first that p ∤ g .) 22. (a) We have 3 16 k ≡ 2 k 6 ≡ 1 (mod 65537) and 3 32 k ≡ 2 32 ≡ 1 (mod 65537). Therefore 65536 ∤ 16 k and 65536 | 32 k . Write 32 k = 65536 ℓ for some ℓ . Divide by 32 to obtain k = 2048 ℓ , so 2 11 = 2048 | k . If 2 12 = 4096 | k , then 16 k is a multiple of 16 · 4096 = 65536, which we showed doesn’t happen. Therefore k is a multiple of 2048, but is not a multiple of 4096. (b) From (a), we see that k is an odd multiple of 2048. We also know that 0 ≤ k < 65536, since every nonzero number mod 65537 can be written as a power of 3 with exponent in this range. There are 65536/2048=32 multiples of 2048 in this range. Of these, 16 are multiples of 4096. The remaining 16 are possibilities for k . We now calculate 3 2048 m (mod 65537) for m = 1 , 3 , 5 , · · · . We find (with the help of a computer) that m = 27 works. So k = 2048 ∗ 27 = 55296.

  15. Page 15
    Read page 15 as text

    10 23. (a) We claim that after the k th step 2, we have r k ≡ y b 1 b 2 ··· b k (mod n ). This is easily seen to be the case for k = 1. Assume it is true for k − 1. We’ll show it’s true for k . We have s k ≡ r 2 k − 1 ≡ y 2 · b 1 b 2 ··· b k − 1 . Then r k ≡ s k y b k ≡ r 2 k y b k ≡ y 2 · b 1 ...b k − 1 + b k ≡ y b 1 ··· b k − 1 b k . Therefore, when k = w we have r w ≡ y x , as desired. (b) Write x = b 1 . . . b w in binary as in (a). We assume b 1 = 1. The algorithm is easily seen to work when x = 0, so we may assume w ≥ 1. We claim that after step 2, a = b 1 . . . b w − k , b ≡ y b w − k +1 ...b w and c ≡ y 2 k for some value of k . When we start, we have k = 0. Suppose we arrive at step 2 with a = b 1 . . . b w − k , b ≡ y b w − k +1 ...b w , and c ≡ y 2 k . If a is odd, then the output of step 2 is the same as the input, hence of the desired form. If a is even, then b w − k = 0. We obtain the new a = b 1 . . . b w − k − 1 , b ≡ y b w − k b w − k +1 ...b w (we may include the extra bit at the beginning since it is 0), and c ≡ y 2 k +1 . Therefore the output has a, b, c in the desired form with k + 1 in place of k . Now let’s look at what happens in step 3. The output of step 2 is of the form a = b 1 . . . b w − j , b ≡ y b w − j +1 ...b w and c ≡ y 2 j for some value of j . If a is even, step 3 does nothing, so the output still has the desired form. If a is odd, then the last bit b w − j of a is 1. The new a is a = b 1 . . . b w − j − 1 0. Also, the new b is y b w − j b w − j +1 ...b w · y 2 j ≡ y 1 b w − j b w − j +1 ...b w ≡ y b w − j b w − j +1 ...b w . The new c is still y 2 j . If the new a = 0, then j = w − 1, so b ≡ y x . Therefore step 5 outputs y x , as desired. Otherwise, step 4 sends us to step 2, which outputs a = b 1 . . . b w − j − 1 , b ≡ y b w − j b w − j +1 ...b w , and c ≡ y 2 j +1 . This is of the desired form with k = j + 1. Therefore, the output of step 2 always has the desired form, as claimed. Since a gets smaller at each application of steps 2 and 3, eventually a = 0 and the algorithm stops. As pointed out above, the output of step 5 is then y x (mod n ). 24. Since z j ≡ 0 (mod m i ) when j 6 = i , we have x ≡ a i y i z i ≡ a i z − 1 i z i ≡ a i (mod m i ). 25. (a) Solve x 2 ≡ 133 (mod 11) to obtain x ≡ ± 1 (mod 11). Now solve x 2 ≡ 133 (mod 13) to obtain x ≡ ± 4 (mod 13). There are four ways to combine these via the Chinese Remainder Theorem: x ≡ 43 , 56 , 87 , 100 (mod 143). (b) This reduces to x 2 ≡ 77 (mod 11) and x 2 ≡ 77 (mod 13). The solutions satisfy x ≡ 0 (mod 11) and x ≡ ± 5 (mod 13). These combine to yield x ≡ 44 , 99 (mod 143). 26. Suppose x 2 ≡ − 1 (mod p ). Raise both sides to the ( p − 1) / 2 power to obtain x p − 1 ≡ ( − 1) ( p − 1) / 2 (mod p ). By Fermat, x p − 1 ≡ 1. Since p ≡ 3] pmod 4, the exponent ( p − 1) / 2 is odd. Therefore ( − 1) ( p − 1) / 2 = − 1. This yields 1 ≡ − 1 (mod p ), which is a contradiction. Therefore x cannot exist. 27. (a) There are at most 4 square roots of x (mod n ). Therefore, several random selections of these square roots should include the meaningful message m . (b) Being able to find square roots mod n is computationally equivalent to factoring n , which is presumed to be hard.

  16. Page 16
    Read page 16 as text

    11 (c) Eve chooses a random number m and computes x ≡ m 2 (mod n ). She gives x to the machine, which outputs a square root m ′ of x . If gcd( m, n ) = 1, there are four possible m ′ , namely m , − m , and two others. After a few tries, Eve should obtain m ′ with m ′ 6 ≡ ± m (mod n ). Since m 2 ≡ x ≡ m ′ 2 (mod n ), a nontrivial factor of n is given by gcd( m − m ′ , n ). 28. (a) Since r 1 = a − bq 1 and d | a, b , we have d | r 1 . Since r 2 = b − q 2 r 1 and d | b, r 1 , we have d | r 2 . (b) Suppose d | r 1 , . . . , r j . Since r j +1 = r j − 1 − q j +1 r j and d | rj − 1 , r j , we have d | r j +1 . By induction, we have d | r i for all i . (c) Since r k − 1 = q k +1 r k , we have r k | r k − 1 . Assume r k | r k − i for i = 1 , 2 , . . . , j . Since r k − j − 1 = q k − j +1 r k − j + r k − j +1 and r k | r k − j , r k − j +1 by assumption, we have r k | r k − j − 1 . By induction, r k | r i for all i . (d) Since b = q 2 r 1 + r 2 and r k | r 1 , r 2 , we have r k | b . Since a = q 1 b + r 1 and r k | a, r 1 , we have r | a . (e) Since d | r k for each common divisor d , we have r k ≥ d for all common divisors d . Since r k is a common divisor, it is the largest. 29. (a) ( 123 401 ) = ( 401 123 ) = ( 32 123 ) = ( 2 123 ) 5 = − 1 . Therefore, there is no solution. (b) ( 43 179 ) = − ( 179 43 ) = − ( 7 43 ) = ( 43 7 ) = ( 1 43 ) = 1 . Therefore, there is a solution. (c) ( 1093 65537 ) = ( 65537 1093 ) = ( 2 1093 ) ( 525 1093 ) = − ( 43 525 ) = − ( 9 43 ) = − 1 . Therefore, there is no solution. 30. (a) If a ≡ b 2 (mod n ), then ( a n ) = ( b n ) 2 = ( ± 1) 2 = 1 . Therefore, if ( a n ) = − 1, then a cannot be a square mod n . (b) ( 3 35 ) = − ( 35 3 ) = − ( 2 3 ) = 1 . (c) Since 3 is not a square mod 5, it cannot be a square mod 35. 31. ( 2 15 ) = 1, but 2 7 ≡ 8 (mod 15). 32. (a) ( 3 65537 ) = ( 65537 3 ) = ( 2 3 ) = − 1 .

165 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Information Technology study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.