Assignment #4: Reductions, Quadratic Residues, and Review

For this assignment, you will submit a single Python source file `a4.py`. You may include answers to the written problems inside a comment block at the beginning of the file (e.g., using `''' This is a comment. '''`).

For the written problems #1-5, you may NOT use a programming language or calculator, and you must show your work. When making a claim in an argument, you should reference the fact you are applying.

For the programming problems #6-7, your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. You may reuse functions that you defined on previous assignments.

1. Suppose the following set S and relation R on S are defined:
 S
=
 {0,1,2,3,4,5,6,7}
 R
=
 {(0,0),(1,1),(1,7),(7,1),(2,2),(2,4),(4,2),(3,3),(4,3),(3,4),(2,3),(3,2),(4,4),(5,5),(6,6),(7,7)}
Define explicitly the quotient set S/R.
Since R is reflexive, symmetric, and transitive, it is an equivalence relation. Thus, we can divide S into a collection of subsets of S so that the members of each subset of mutually equivalent according to R.

Thus, we have S/R = {{0}, {1, 7}, {2, 3, 4}, {5}, {6}}.
2. Let n N and a Z/nZ. Suppose that gcd(a,n) = 1. Determine the exact size of the following set:
 { a ⋅ i mod n | i ∈ {0,...,n-1} }
We know that the above set is a permutation of {0,...,n-1}, so the size is n.
3. Let n N and a Z/nZ. Suppose that gcd(a,n) = 1. Determine the exact size of the following set:
 { i ⋅ (aφ(n)) mod n | i ∈ {0,...,n-1} }
We know by Euler's theorem that aφ(n) mod n = 1 since a and n are coprime. Thus, the size of the set is n, since this is exactly the set {0,...,n-1}.
4. Let p N be a prime number. Determine the exact size of the following set:
 { aφ(p) mod p | a ∈ {1,...,p-1} }
We know by Euler's theorem that aφ(p) mod p = 1 if a and p are coprime. Thus, the size of the set is 1.
1. Find the multiplicative inverse of each of the following if it exists, or explain why it does not exist (the solution may be a formula in terms of the variables in the expression).
1. 2 Z/5Z
2. 3 Z/10Z
3. 5 Z/21Z
4. (2 ⋅ 3) Z/11Z
5. 6 Z/7Z
6. (3 ⋅ b) Z/(ab)Z
7. a Z/(a+1)Z
8. (ab) Z/((ab)-1)Z
1. 2φ(5)-1 mod 5   =   23 mod 5   =   8 mod 5 = 3
2. 3φ(10)-1 mod 10   =   3((5-1)⋅(2-1))-1 mod 10   =   33 mod 10 = 7
3. Using the formula for inverses in terms of φ:
 5φ(21)-1 mod 21
=
 5((7-1)⋅(3-1))-1 mod 21
=
 511 mod 21
=
 5 ⋅ (52)5 mod 21
=
 5 ⋅ (4)5 mod 21
=
 5 ⋅ 4 ⋅ (22)4 mod 21
=
 20 ⋅ (28) mod 21
=
 20 ⋅ 256 mod 21
=
 20 ⋅ 4 mod 21
=
 80 mod 21
=
 17 mod 21
4. For purposes of illustration, we solve this by finding the inverses of the components, then multiplying:
 2 ⋅ 6
 12
 1 mod 11
 3 ⋅ 4
 12
 1 mod 11
 (2 ⋅ 3) -1
 6 ⋅ 4
 24
 2 (mod 11)
5. 6 Z/7Z, since 6 ⋅ 6 = 36 ≡ 1 (mod 7)
6. If b > 1, then there is no inverse, since gcd(3 ⋅ b, ab) ≥ b. If b = 1, then the inverse is (3 ⋅ b)φ(ab)-1 mod (ab). Either or both of these answers are acceptable.
7. We know that gcd(a, a+1) = 1. Thus, we can find s and t that satisfy Bézout's identity:
 s ⋅ a + t ⋅ (a + 1)
=
 gcd(a, a+1)
 (-1) ⋅ a + (1) ⋅ (a + 1)
=
 1
 s
=
 -1
 t
=
 1
But (s,t) is the output of the extended Euclidean algorithm, and if the greatest common divisor is 1, then s is the multiplicative inverse of the first argument modulo the second argument, which is a in this case. Thus, -1 Z/(a+1)Z, or (a+1)-1 = a, is the multiplicative inverse of a in Z/(a+1)Z. Alternatively, a -1aφ(a+1)-1 mod (a+1). Either or both of these answers are acceptable.
8. We know that (ab) ≡ 1 (mod ((ab) - 1)). Thus, the inverse is 1 Z/((ab) - 1)Z.
2. Compute each of the following.
1. 111025 mod 17
Since 11 and 17 are coprime, we have that 111025 ≡ 111025 mod φ(17). Then, we have that:
 1025 mod φ(17)
 1025 (mod 16)
 (210 + 1) (mod 24)
 1 (mod 24)
 111025
 111 (mod 17)
 11 (mod 17)
2. 2(2100000001) mod 7
Since gcd(2,7) = 1, we can compute 2100000001 mod φ(7) to make the exponent more manageable. We know that the powers of 2 modulo 6 are 2,4,2,4,2,4,2,4,... Thus, since 100000001 is odd, we have:
 2100000001
 21 (mod 6)
 2(2100000001)
 2(21) (mod 7)
 4 (mod 7)
3. { x | x Z/17Z, x2 ≡ 16 mod 17 }
Since 17 is prime, we know there are at most two solutions. Since 16 < 17, we know that they are 4 and -4 = 17-4 = 13. Thus, this set is {4, 13}.
4. { x | x Z/10Z, x2 ≡ 9 mod 10 }
The two obvious solutions to the equation x2 ≡ 9 (mod 10) are 3 and -3 = 10-3 = 7. However, there may be as many as four solutions since 10 = 2 ⋅ 5.

In Z/2Z, 9 ≡ 1. The two solutions in Z/2Z are thus 1 and -1. However, since -1 = 2-1 = 1, there is only one solution in Z/2Z.

In Z/5Z, 9 ≡ 4, and the two solutions are 2 and -2 = 5-2 = 3. Thus, there are two distinct systems of equations that can be set up, so there are two distinct solutions x1 and x2:
 x1
 1 (mod 2)
 x1
 2 (mod 5)
 x2
 1 (mod 2)
 x2
 3 (mod 5)
The two solutions are still 3 and 7. Thus, the set is {3,7}.
5. |{ x | x2 ≡ 4 mod (7 ⋅ 23 ⋅ 31 ⋅ 59) }|
We know that 2 and -2 are solutions to x2 ≡ 4 in Z/7Z, Z/23Z, Z/31Z, and Z/59Z because these moduli are greater than 4. Thus, there are 24 possible distinct systems of equations for which we can use CRT to find solutions. Thus, there are 24 = 16 solutions, so the size of this set is 16.
6. (Z/6Z)*
Using the definition, we have that:
 (Z/6Z)*
=
 {x | x ∈ Z/6Z, x -1 ∈ Z/6Z}
=
 {x | x ∈ Z/6Z, gcd(x,6) = 1}
=
 {1, 5}
3. At some point in the past, Alice used Bob's public RSA key (n,e) to send him several encrypted messages. Bob stored the encrypted versions of these messages without decrypting them. Some time later, Bob decides to read the messages. However, he discovers he has misplaced his public key (n,e), his private key d, and one of his primes p; he only knows q and φ(n) (he cannot ask anyone else for the lost information). Can Bob find a way to recover some or all of the lost information and read Alice's old messages? Explain in detail.
Bob can use q and φ(n) to recover p, since:
 φ(n)
=
 (p-1) ⋅ (q-1)
 p
=
 (φ(n)/(q-1)) + 1
However, e was chosen at random from (Z/φ(n)Z)*, and p and q do not help in reproducing it. Thus, even though Bob could compute d for a given e, e cannot be recovered, so Bob cannot recover the lost information.
4. Suppose that an efficient algorithm has been discovered for computing discrete logarithms modulo primes. That is, given some value ga mod p, it is now possible to efficiently compute a if g is known (i.e., logg (ga) ≡ a). Assuming that no other discoveries have been made, explain how Alice and Bob can (possibly using some other method, not necessarily D-H) still securely agree on a shared secret integer s Z without meeting in person. You must explain why this alternate method is still secure despite the new discovery.
Because none of the other problems we considered (factoring, computing φ, congruent squares, and the RSA problem) have any known polynomial-time reductions to the discrete logarithm problem, the existence of an efficient algorithm for computing discrete logarithms does not imply an efficient solution for any of the other problems. Thus, it is no more risky than before to assume that cryptographic protocols such as RSA are secure.

Bob and Alice could use the RSA or Rabin cryptographic protocol. For example, Alice chooses a secret, and Bob generates a public RSA key. Alice then encrypts and sends the secret value to Bob. Bob decrypts that secret value. At this point, Alice and Bob share a secret that no one else knows (assuming RSA is secure).
5. Consider the following problem (call it "φ-four"): "given an integer n that is the product of four distinct primes, find φ(n)." Notice that the four distinct primes are not known in the specification of the problem. It is only known that n is the product of some four distinct primes.
1. Given our assumptions about the intractability of various problems (i.e., that certain problems are not in P), you must show that φ-four is also not in P. To do so, you must implement a solver for some existing intractable problem that uses a solver for φ-four (call it `phi_four()`) as a subroutine. The algorithm you implement must represent a polynomial-time reduction to φ-four from the intractable problem you choose. Note: remember that the four primes must be distinct; your reduction must work for all possible instances of the intractable problem.
2. Suppose that we discover an efficient algorithm `getFactor()` that takes a single integer input and returns exactly one prime factor of its input. Implement a Python function that solves φ-four efficiently by calling `getFactor()` as a subroutine.
6. Implement a Python function `roots()` that takes two arguments: an integer y as its first argument, and a list of primes as its second argument. You may assume that all the primes p are such that p ≡ 3 mod 4. Let P be the product of all the primes in the list. The function should return a set of all the distinct square roots of y2 in Z/PZ. Your implementation must be efficient (i.e., it may not iterate over all possible values in Z/PZ to look for square roots).