Let p and q be primes such that p = 2q + 1. Let a be a random element of Z*p. Pr

Question

Let p and q be primes such that p = 2q + 1. Let a be a random element of Z*p. Prove that if neither alpha 2 mod p nor alpha q mod p is equal to 1, then alpha is a generator of Z*p. Use without proof the following fact, which is stated in the notes but which I only mentioned in passing in class: the order of any element of Z*p divides phi (p). Another fact stated in the notes is that the number of generators of Z* is phi (p - 1). In this case, we have phi (p - 1) = phi (2q) = phi (2) phi (q) = q - 1. Therefore, the probability that a randomly selected element of Z*p is a generator is about .50. So the fact I'm asking you to prove in this problem provides an efficient method for finding a generator of Z*p. as long as we can find a p and q of the required form. It turns out that there are reasonably efficient techniques for finding pairs of primes of this form. ]

Explanation / Answer

For prime p, phi(p)=p-1=2q

( because phi(p) is the cardinality of the set of numbers less than p, which are co-prime to p, which for prime p is p-1) in this case,

Now, order of alpha divides 2q (as given in the hint).

Thus, the options for order of alphaa are 1,2,q, 2q. (Since both q and 2 are primes)

Since 2 and q can't be the order (given as neither alpha2 mod p and nor alphaq mod p is equal to 1), the remaining options are 1 and 2q.

1 is not an option as the group is cyclic, thus it must have a generator.

Hence, the order of alpha has to be 2q. And thus it is a generator of Zp*

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.