# Exercises

- Page ID
- 7407

14.1: Let *p* be an odd prime, as usual. Recall that ℚℝ^{∗}* _{p}* is the set of quadratic residues mod

*p*— that is, ℚℝ

^{∗}

*= {*

_{p}*x*∈ ℤ

^{∗}

*| ∃*

_{p}*y*:

*x*≡

_{p}y^{2}}. Show that if

*g*is a primitive root of ℤ

^{∗}

*then ⟨g*

_{p}^{2}⟩ = ℚℝ

^{∗}

*.*

_{p}*Note:* This means that *g ^{a}* ∈ ℚℝ

^{∗}

_{p}if and only if

*a*is even — and in particular, the choice of generator

*g*doesn’t matter.

14.2: Suppose *N* = *pq* where *p* and *q* are distinct primes. Show that |ℚℝ^{∗}* _{N}*| = |ℚℝ

^{∗}

_{p}| · |ℚℝ

^{∗}

*|.*

_{q}*Hint:* Chinese remainder theorem.

14.3: Suppose you are given *X* ∈ ⟨g⟩. You are allowed to choose any *X’* ≠ *X* and learn the discrete log of *X’*. (with respect to base *g*). Show that you can use this ability to learn the discrete log of *X*.

14.4: Let ⟨g⟩ be a cyclic group with *n* elements and generator *g*. Show that for all integers *a*, it is true that *g ^{a}* =

*g*.

^{a%n}*Note:* As a result, ⟨g⟩ is isomorphic to the additive group ℤ_{n}.

14.5: Let *g* be a primitive root of ℤ^{∗}* _{n}*. Recall that ℤ

^{∗}

*has*

_{n}*ϕ*(

*n*) elements. Show that

*g*is a primitive root of ℤ

^{a}^{∗}

*if and only if gcd(*

_{n}*a,ϕ*(

*n*)) = 1.

*Note:* It follows that, for every *n*, there are either 0 or *ϕ*(*ϕ*(*n*)) primitive roots mod *n*.

14.6: Let ⟨g⟩ be a cyclic group with *n* elements. Show that for all *x,y* ∈ ⟨g⟩, it is true that *x ^{n}* =

*y*.

^{n}*Hint:* every *x* ∈ ⟨g⟩ can be written as *x* = *g ^{a}* for some appropriate

*a*. What is (

*g*)

^{a}*?*

^{n}14.7: (a). Prove the following variant of __ Lemma 4.8__: Suppose you fix a value

*x*∈ ℤ

*. Then when sampling*

_{N}*q*= √2

*N*values

*r*

_{1},. . . ,

*r*uniformly from ℤ

_{q}_{N}, with probability at least 0.6 there exist

*i*≠

*j*with

*r*≡

_{i}

_{N}*r*+

_{j}*x*.

*Hint**: *This is extremely similar to __Exercise 4.7__

(b). Let *g* be a primitive root of ℤ^{∗}* _{p}* (for some prime

*p*). Consider the problem of computing the discrete log of

*X*∈ ℤ

^{∗}

*with respect to*

_{p}*g*— that is, finding

*x*such that

*X*≡

*. Argue that if one can find integers*

_{p}g^{x}*r*and

*s*such that

*g*≡

^{r}*·*

_{p}X*g*then one can compute the discrete log of

^{s}*X*.

(c). Combine the above two observations to describe a *O*(√*p*)-time algorithm for the discrete logarithm problem in ℤ^{∗}* _{p}*.

14.8: In an execution of DHKA, the eavesdropper observes the following values:

What will be Alice & Bob’s shared key?

14.9: Explain what is wrong in the following argument:

*In Diffie-Hellman key agreement, Alice sends A* = *g ^{a} and Bob sends B* =

*g*=

^{b}. Their shared key is g^{ab}. To break the scheme, the eavesdropper can simply compute A · B*(g*

^{a})(g^{b}) = g^{ab}.14.10: Let ? be a cyclic group with *n* elements and generator *g*. Consider the following algorithm:

Let *DH* = {(*g ^{a},g^{b},g^{ab}* ) ∈ ?

^{3}|

*a,b,*∈ ℤ

_{n}}.

(a). Suppose (*A,B,C*) ∈ *DH*. Show that the output distribution of RAND(*A,B,C*) is the uniform distribution over *DH*

(b). Suppose (*A,B,C*) ∉ *DH*. Show that the output distribution of RAND(*A,B,C*) is the uniform distribution over ?^{3}.

(c). Consider the problem of determining whether a given triple (*A,B,C*) is in the set *DH*. Suppose you have an algorithm ? that solves this problem on average slightly better than chance. That is:

The algorithm ? does not seem very useful if you have a *particular* triple (*A,B,C*) and you really want to know whether it is in *DH*. You might have one of the triples for which ? gives the wrong answer, and there’s no real way to know.

Show how to construct a randomized algorithm ?’ such that: for every (*A,B,C*) ∈ ?^{3}:

Here the input *A,B,C* is fixed and the probability is over the internal randomness in ?’. So on every possible input, ?’ gives a very reliable answer.