As student I've been asked the following question:

Consider the specific prime $p=17$. Determine the single element generators (by hand or by Java program) of $F^*_{17}$. Recall $F^*_{17}$ is the multiplicative group of size $16 = 17−1$ formed by removing $0$ from the field $F^*_{17}$.

Can anyone explain what the steps are in order to attempt the question?

  • 3
    $\begingroup$ Welcome to Cryptography. For homework questions we provide hints. A generator $g$ of a group $G$, where the $F^*_{17}$ is a multiplicative cyclic group, is an element such that when you multiply $g$ itself, again and again, you will get all the elements of the group. Eventually, it will be 1. Now can you think methods? Also, see Little Fermat theorem, $\endgroup$ – kelalaka Mar 14 at 12:40

I was unable to find a solution to the problem besides the approach suggested in the comments, but I wanted to add a few theorems from group theory that are relevant here.

The problem with picking a random group element as a generator is that it might actually be a generator of a smaller subgroup. By Euler's theorem, every element raised to the power of the group order, $n$, is $1$. That is, if $x$ is an element of a subgroup of order $k$, then

$$x^n = x^{km} = (x^k)^m = 1^m = 1.$$

So it is not sufficient to check that an element raised to the $n$th power is $1$, since this is satisfied by all group elements.

But it is not necessary to check every exponent $[1,n]$ to see if it generates a subgroup because, by Lagrange's theorem, there can be at most one subgroup for every divisor of $n$. So it suffices to check divisors of $n$ as exponents to see if they generate the group identity.

| improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.