I will upload my questions when I get it from my professor.
Math 5405, Spring 2021, Assignment 1 Solutions 1. A character in The man who mistook his wife for a hat, by Oliver Sacks, owns a book with all primes having up to 10 decimal digits. Using the prime number theorem, estimate the number of such primes. With 70 digits to a line, and 50 lines to a page, approximately how many pages would this book have? Solution: The number of primes is approximately 1010/(ln1010)≈ 4×108. Most of these primes have 10 decimal digits, so the number of pages is approximately 4×108×10 70×50 ≈ 106. 2. Solve 563x≡ 7943 mod 18965 using your favorite calculator or software. Solution: Using the gcd algorithm, the inverse of 563 mod 18965 is −8893. The solution is x ≡ −8893×7943 ≡ 7526 mod 18965 . 3. Fill in the multiplication table for the field F9 := Z[i]/3, viewing the elements as {0, ±1, ±i, ±1± i}. (Since the table is symmetric about the diagonal, you can skip the part below the diagonal!) Solution: The multiplication table is × 0 1 −1 i −i 1+ i 1− i −1+ i −1− i 0 0 0 0 0 0 0 0 0 0 1 1 −1 i −i 1+ i 1− i −1+ i −1− i −1 1 −i i −1− i −1+ i 1− i 1+ i i −1 1 −1+ i 1+ i −1− i 1− i −i −1 1− i −1− i 1+ i −1+ i 1+ i −i −1 1 i 1− i i −i 1 −1+ i i −1 −1− i −i 4. With F9 as in the previous problem, find all elements of the group F×9 that have order 8. Solution: Since F×9 is a cyclic group with 8 elements, and ϕ(8) = 4, there are 4 such elements: ±1± i. 5. Construct an isomorphism between the groups (Z/7)× and Z/6. Solution: The elements of (Z/7)× with order 6 are 3 and 5, so the possible isomorphisms Z/6−→ (Z/7)× are 1−→ 3 1−→ 5 2−→ 2 2−→ 4 3−→ 6 or 3−→ 6 4−→ 4 4−→ 2 5−→ 5 5−→ 3 0−→ 1 0−→ 1 6. Using the Chinese remainder theorem, find all solutions of x2 = 2 in the ring Z/119. (Note that 119 = 7×17.) Solution: The solutions in Z/7 and Z/17 are, respectively, ±3 and ±6. Next, use Euclid’s algorithm to obtain 1 = 5×7−2×17, so −34≡ { 1 mod 7 0 mod 17 and 35≡ { 0 mod 7 1 mod 17. It follows that the solutions of x2 = 2 in the ring Z/119 are ±3(−34)±6(35) = ±11,±45 . 7. How many solutions does x2 = 7 have in each of the following rings? (You need not find the solutions.) (a) Z/19 (b) Z/21 (c) Z/57 Solution: (a) Quadratic reciprocity shows that 7 is a square modulo 19, so it has two square roots. (b) Since x2 = 7 has two solutions in Z/3 and one solution in Z/7, there are two solutions in Z/21. (c) Since x2 = 7 has two solutions in Z/3 and two solutions in Z/19, there are four solutions in Z/57. 8. Is 2 a primitive root modulo 103? Try to do this efficiently! Solution: The group (Z/103)× has 102 = 2× 3× 17 elements, so if 2 is not a primitive root, then its order divides 6 or 34 or 51. Check: 26 ≡ 64 mod 103 , 234 ≡ 46 mod 103 , 251 ≡ 1 mod 103 , which shows that 2 is not a primitive root. 9. Use quadratic reciprocity to see whether the following have solutions; each modulus is prime. (a) x2 ≡ 123 mod 401, (b) x2 ≡ 43 mod 179. Solution: 123 is not a square mod 401 since( 123 401 ) = ( 3 401 )( 41 401 ) = (1) ( 401 3 ) (1) ( 401 41 ) = ( 2 3 )( −9 41 ) = (−1) ( −1 41 ) = (−1)(1) = −1 . However, 43 is a square mod 179 since( 43 179 ) = (−1) ( 179 43 ) = (−1) ( 7 43 ) = (−1)(−1) ( 43 7 ) = ( 1 7 ) = 1 . 10. Let p be an odd prime. Fill in the table below. Prove that x8 ≡ 16 mod p has a solution. Solution: p≡ 1 mod 8 p≡ 3 mod 8 p≡ 5 mod 8 p≡ 7 mod 8( −1 p ) 1 −1 1 −1( 2 p ) 1 −1 −1 1( −2 p ) 1 1 −1 −1 It follows that if p ≡ 1,3,7 mod 8, then either 2 or −2 is a square modulo p, so x8 ≡ 16 mod p has a solution. If p≡ 5 mod 8, then there exists a with a2 ≡−1 mod p. But then (1+a)2 ≡ 2a mod p, so (1+a)8 ≡ 16 mod p. Alternatively: x8−16 = (x2−2)(x2 +2)(x2−2x+2)(x2 +2x+2). If p≡ 1,3,7 mod 8 then, from the table, at least one of x2−2 or x2 +2 has a root. In the case p ≡ 5 mod 8, it suffices to show that x2 +2x+2 has a root. By the quadratic formula, this has a root provided ( −4 p ) = 1, which is indeed the case from the table. Math 5405, Spring 2021, Assignment 2 Solutions 1. We saw that if a prime p is 3 mod 4, and a is a square modulo p, then a(p+1)/4 is a solution of x2 ≡ a mod p. Using this, and your favorite software, find the square roots of (a) 26055 modulo the prime 34807, (b) 576031280 modulo the prime 5986660523. Solution: (a) Since 34807≡ 3 mod 4, the square-roots are ±26055(34807+1)/4 ≡ ±33573 ≡ ±1234. (b) Similarly, since 5986660523≡ 3 mod 4, the square-roots are ±576031280(5986660523+1)/4 ≡ ±54473761 ≡ ±5932186762. 2. Try to find the square root of 48382 modulo the prime 83987 using the idea from the previous problem. Square your answer to see if it is correct. What happened here? Solution: If 48382 were a square modulo 83987, its square roots would be ±48382(83987+1)/4 ≡ ±60555. However, 605552 ≡ 35605≡−48382, showing that 48382 is not a square modulo 83987. (Since 83987≡ 3 mod 4, exactly one of ±48382 is a square mod 83987). 3. Let p be an odd prime. Suppose x,y are nonzero modulo p, and x2 ≡ y2 mod p2, prove that x≡±y mod p2. Solution: x2 ≡ y2 mod p2 implies that p2 | (x− y)(x+ y). If p | (x− y) and p | (x+ y), then p divides 2x, and hence x. But this is a contradiction. Hence p2 | (x− y) or p2 | (x+ y), i.e., x≡±y mod p2. 4. Alice and Bob are flipping coins over the phone. Suppose Alice cheats by choosing primes p = q, show that Bob always loses, in the sense that Alice always returns ±x, where x is the random number chosen by Bob. (So Bob should always ask for the two primes at the end of the coin flip.) Solution: Bob chooses a number x and send x2 mod p2 to Alice. The previous problem shows that the only square roots of x2 mod p2 are ±x mod p, so Alice is guaranteed to win. 5. We saw how to solve x2 ≡ a mod p when p≡ 3 mod 4; here is an analogue for p≡ 5 mod 8. Suppose a is a quadratic residue modulo a prime p with p≡ 5 mod 8. (a) Show that a(p−1)/4 ≡±1 mod p. (b) If a(p−1)/4 ≡ 1 mod p, prove that the solutions of x2 ≡ a mod p are ±a(p+3)/8. (c) If a(p−1)/4 ≡−1 mod p, prove that the solutions of x2 ≡ a mod p are ±2a(4a)(p−5)/8. Solution: (a) Since a is a quadratic residue, Euler’s formula implies that a(p−1)/2 ≡ 1 mod p. Hence its square root a(p−1)/4 can only be ±1 mod p. (b) We compute ( ±a(p+3)/8 )2 ≡ a(p+3)/4 ≡ a×a(p−1)/4 ≡ a. (c) Similarly, ( ±2a (4a)(p−5)/8 )2 ≡ 4a2 (4a)(p−5)/4 ≡ 2(p−1)/2 a×a(p−1)/4 ≡ ( 2 p ) ×a× (−1) ≡ a. 1 6. Consider the prime p = 5643653. Using the previous problem (and your favorite software!) solve (a) x2 ≡ 435645 mod p, (b) x2 ≡ 1892117 mod p. Solution: (a) As 435645(p−1)/4 ≡ 1 mod p, use (b) to get ±435645(p+3)/8 ≡±4935936≡±707717. (b) Since 1892117(p−1)/4 ≡−1 mod p, the solutions using (c) are ±5270963≡±372690. 7. A shift key is exchanged using the Diffie-Hellman method with primitive root g = 5 modulo the prime p = 47. The actual numbers exchanged over a public channel were X = 38 and Y = 3. Find the shift key k, and use it to decipher the message EQPITCVWNCVKQPU. (The above was obtained by shifting k steps forward in the circle A 7−→ B 7−→ C 7−→ ·· · 7−→ Z 7−→ A) Solution: We need to solve 5x≡ 38 mod 47 or 5y≡ 3 mod 47. Towards this, we compute the powers of 5 mod 47 till we encounter 38 or 3. 51 52 53 54 55 56 57 58 59 510 511 512 513 514 515 516 517 5 25 31 14 23 21 11 8 40 12 13 18 43 27 41 17 38 Thus, x = 17, and hence the shift key is Y x ≡ 2 mod 47. (Alternatively, solve 5y ≡ 3 mod 47 to get y = 20.) Shifting back by two letters, the message is CONGRATULATIONS. 8. An RSA cipher has modulus n = 4189 and encryption key e = 11. Factor n and find the decryption key. Solution: The modulus n factors as 4189 = 59×71, so ϕ(n) = 58×70 = 4060, and the decryption key is the inverse of 11 mod 4060, i.e., d = 3691. 9. Decipher the RSA-encrypted message 1373 1149 108 that has been sent to Kamehameha; his public key is n = 1517 and e = 11. Express the final answer in terms of the nine letter alphabet from the lecture notes. Solution: Recall that the decryption key is d = 131, or compute this using the factorization n = 37× 41. The decrypted message is 1373d mod n≡ 62 1149d mod n≡ 42 108d mod n≡ 53 which translates as MA-HA-LO. 10. Use the ElGamal cipher with p = 103, g = 2, X = 58, and y = 31 to encrypt KO-NA = 83-72. Solution: First compute Y ≡ gy mod p to obtain Y = 83. The encryption key is k ≡ Xy mod p, i.e., k = 98. Then, the message 83-72 is encrypted as 83× k ≡ 100 and 72× k ≡