Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment 4

MAT315: Introduction to Number Theory

Due June 11th

Each part of problem 1 and 2 relies on the previous parts.  You should think of problem 1 and problem 2 as being larger problems which have been broken down into smaller, easier problems to guide you to the solution.  Nonetheless, if you are stuck, don’t hesitate to assume the answer to the previous parts to continue; you can always come back to the previous parts later.

Problem 1.      a) Use the Chinese Remainder Theorem to construct a function f : Z/2 × Z/5 −→ Z/10 which is a ring isomorphism.Your answer should clearly indicate all 10 pairs (input, output).

b) Alice wants to use RSA to communicate privately with Bob. To this effect, she has chosen the primes 2 and 5.  Help Alice set up a public key and a private key by writing down what they should be.

c) Bob has received Alice’s public key, and would like to send the message ”937” to Alice.  Help Bob by encrypting the message for them. Since the number in the message is larger than 10, you should break it into smaller messages.

d) Alice has received Bob’s message and is asking for your help decrypting the message. Show Alice what the decryption process looks like.

Problem 2.  One issue that can arise when using RSA is that the message a can generate a subgroup which is too small.  When this happens, it is possible to recover the decrypted message from the encrypted message using brute-force alone. In this problem, you will show that ”most”messages will not generate a small subgroup by establishing results about cyclic groups along the way. As a matter of terminology, we define the order of an element g of a group to be the smallest positive integer k such that gk  = 1, and we denote this quantity ord(g).

a) Let p be an odd prime. Prove that there exist some residue class g ∈ Z/p× such that {gl  ∈ Z/p×  | l ∈ N} = Z/p× . As a matter of terminology, for any g we call the group {gl  ∈ Z/p×  | l ∈ N} the group generated by g . (Hint: choose an arbitrary element in the group. If it generates all of the group, you are done. If not, pick some h not in ⟨g⟩ and try to find integers x,y such that gx hy has a larger order).

b) Let m be a positive integer. Prove that the set {g ∈ Z/m×  | ord(g) = d} has size φ(d) provided it is nonempty. Use this to show that 对d|m φ(d) = m by counting the size of Z/m in two different way.

c) With the same notation as in a), prove that as p goes to infinity the proportion

#{g ∈ Z/p×  | g generates a subgroup of size  ≥ p1/3}

φ(p)

tends to 1 i. e .  that most elements in the group generate a subgroup of size at least p1/3 . (Hint: use b) to estimate the sum        对       φ(d))

d|p−1;d<p1/3

d) Let p1 ,p2  be odd primes and let m  = p1p2 .  Prove that as min{p1 ,p2 }  goes to infinity, the proportion

#{a ∈ Z/m×  | ord(a) ≥ min{p1 ,p2 }1/3}

φ(m)

tends to 1 i. e .  as the primes get large, most elements will generate a subgroup of size at least min{p1 ,p2 }1/3