I have just read in a book that in El-Gamal PKC, the best choice of a base g is a number whose order in the field ($\mathbb{F}_p$) is a large prime, and added: "approximately = $\frac{p}{2}$". but from my point of view choosing a primitive root as a base is more secure because then the key space will be at least twice as large as if you chose any other base of any other order.

Is there anything I am ignoring or what?

  • $\begingroup$ In case anyone has the same question, choosing a big prime order is better because there are algorithms like Pohlig-HellMan algorithm which reduces the discrete logarithm problem with a base having order N to much easier problems whose bases have orders corresponding to the prime factors of the original order. So, choosing a Prime order will make this algorithm useless. $\endgroup$ Jul 12 at 1:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy