Decrypt and encrypt
homework代写 | 密码学代做 | 加密与解密 – 这是值得参考的密码学方面的homework代写的题目
(1) a) (4 Points)Determine how many roots the polynomialf(x) =x^241 1 has inZ/ 385 Z. Justify your answer. b) Letg(x) =x^3 +x+ 7. i) (3 Points)Find a solution tog(x) inZ/ 21 Z. ii) (3 Points)Find a solution tog(x) inZ/ 3969 Zwhich is congruent modulo 21 to the solution you found in i). To help you with this, you may use the fact thatd 1 = 43 is an inverse of 49 inZ/ 81 Zas well as thatd 2 = 23 is an inverse of 81 inZ/ 49 Z.
(2) Suppose Alice has a public RSA key of (2867,89) and that Bob has sent a message to Alice encrypted via her public key. You have intercepted the encrypted message ofc= 45.
a) (6 Points)Determine Alices private RSA key. Note: In order to do this you must factor 2867 into a product of primes. For your convenience, a list of primes under 100 is given by: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97. b) (4 Points)Decrypt the message Bob sent to Alice.
(3) Let 5 (x) =x^4 +x^3 +x^2 +x+ 1Z[x] and recall that x^5 1 = (x1) 5 (x). Though it is proved in the textbook that 5 (x) is irreducible overZ, when considered as an element Fp[x] for a primepnote that 5 (x) may or may not be prime. Lett(x)F 3 [x] be a monic prime factor of 5 (x) in F 3 [x] and letL= F 3 [x]/t(x)F 3 [x]. Note that|L| = 3deg(t(x))and |L|= 3deg(t(x))1. We considerF 3 as a subset ofLby identifyingcF 3 with the element [c]t(x)inL. Under this identification we have that the inclusionF 3 Lis a ring homomorphism and as such we may ask whether or not a polynomial inF 3 [x] has a root inL. Moreover, you are free to assume the following: for= [x]t(x)Lwe have thatis a root oft(x) inL.
a) (3 Points)SupposeLis a root oft(x). Explain why we must have ordL() = 5. b) (3 Points)Explain why we must have 5| 3 deg(t(x))1. c) (4 Points)Explain why we must havet(x) = 5 (x) and hence that 5 (x) itself is prime inF 3 [x].
(4) Lets(x) =x^2 +x+ 2F 5 [x].
a) (4 Points)Show thats(x) is irreducible inF 5 [x]. b) (6 Points)Note thatE=F 5 [x]/s(x)F 5 [x] is a field with|E|= 25. Determine whether or not 3x+ 2 is a primitive root of (E,).
(5) Consider 15 (x) =x^8 x^7 +x^5 x^4 +x^3 x+ 1Z[x] where from homework 7 we know that x^15 1 = (x1)(x^2 +x+ 1)(x^4 +x^3 +x^2 +x+ 1) 15 (x) and where we similarly note that
x^3 1 = (x1)(x^2 +x+ 1)
and that x^5 1 = (x1)(x^4 +x^3 +x^2 +x+ 1).
a) (3 Points)Letpbe a prime. Show that ifd= gcd(p 1 ,15) then any solutionaFp tox^15 1 is also a solution toxd1. b) (4 Points)Give a necessary and sufficient condition on a primepwhich ensures that 15 (x) will have 8 distinct roots in Fp. Show that your condition is necessary and sufficient. c) (3 Points)For each of the following primespstate how many roots 15 (x) has inFp. No justification is required. i) p= 5. ii) p= 311. iii) p= 337.