MA-410 Homework 3

Due at 4:59pm in my mailbox in SAS 3151, Thursday, April 11, 2019

Solutions may only be submitted in hard copy. Note my office hours on my schedule.

1. ENT, §6.2, Problem 1, page 116.
2. ENT, §8.4, Problem 2, page 167. Please use the residue 2 for the primitive root modulo 11.
3. ENT, §9.1, Problem 8, page 174. Please prove part (a) for r being a quadratic non-residue. For part (b) use r=3 as a quadratic non-residue modulo both 17 and 41.
4. ENT, §10.1, Problem 14, page 209. [Hint: use Maple's “&^ mod” procedure. There may be a typo in the hint: 1013 ⋅ 17 ≡ 1 (mod φ(2573)).] Note: the 7th edition of the text book has different numbers than the 6th, which decrypt to actual text: (n,k) = (2573, 1013) and the cipher text is 0464 1472 0636 1262 2111.
5. Bonus problem: Let p be a prime ≡ 5 (mod 8); then p-1 ≡ 0 (mod 4) and p+3 ≡ 0 ≡ 3p+1 (mod 8).
   Let a be a quadratic residue, and r a quadratic non-residue, and let b = 2^-1 ((1+r^(p-1)/4) a^(3p+1)/8 + (1-r^(p-1)/4) a^(p+3)/8 ) mod p. Please prove that b² ≡ a (mod p).