# order of an element modulo safe prime

I have to find and element of order $\frac{p-1}{2}$ in a group with p-1 elements (say in the group of units modulo $p$). Now I know that $p$ is prime and that $\frac{p-1}{2}$ is also a prime (that is $p$ is a so called safe prime). I actually have an exact value for $p$ but it is of such magnitude that there is no point writing it here. Now since $p$ is a prime we have that $p-1$ is even and by Lagrange we know that the order of any subgroup has to divide the order of the group. This fact leaves us with 3 choices for possible orders for subgroups in this group, namely $2$, $q$ and $2\cdot q=p-1$ where $q=\frac{p-1}{2}$. I would like to find an element that definitely has order $\neq 2$ and $\neq p-1=2q$ cause this will leave us with only one choice. Now since $p$ is greater than say $10^{30}$ the first couple of hundred elements will definitely satisfy that they won't have order $2$ (so we can try with small values like $2,3,4,\ldots$). But now I am stuck, how can I find an element that is definitely NOT a generator? (like is there any way to tell that $3$ for example cannot be a generator) Is there any easy ways? Knowing that $p$ is a safe prime?

• What can you say about the order of $a^2$? – Daniel Fischer Feb 23 '15 at 12:13
• thanks, now I have to live with the burden that I havent seen this before :) – Vinyl_cape_jawa Feb 23 '15 at 12:20
• If I had a dollar for every time ... – Daniel Fischer Feb 23 '15 at 12:22
• Being a poor student I can only contribute with an online hug...but an honest one :) – Vinyl_cape_jawa Feb 23 '15 at 17:36

For the sake of filling in the hint provided some time ago by Daniel Fischer, consider first an arbitrary nonzero element $$a$$ of $$\mathbb Z \bmod p$$. The (multiplicative) order of $$a$$ must divide the order of the multiplicative group, namely $$p-1$$.
By assumption (that $$p$$ is a safe prime) the prime factorization of $$p-1$$ is $$2\cdot \frac{p-1}{2}$$.
So there are very few possibilities for the order of $$a$$. It could be $$1,2,p-1$$ or the desired order $$\frac{p-1}{2}$$. We can easily rule out the first two possibilities if we avoid $$a^2 \equiv 1 \bmod p$$, since with $$p$$ prime there are exactly two roots $$a\equiv \pm 1 \bmod p$$ of that equation.
Now pick any other element $$a$$ of the multiplicative group. If the order $$|a|=p-1$$, then we could fix things up by choosing $$a^2$$ modulo $$p$$.
In fact unless $$p=5$$ one can also show that $$a^2$$ has the desired order $$\frac{p-1}{2}$$ even if $$a$$ already had order $$\frac{p-1}{2}$$. This is because when $$p$$ is a safe prime greater than $$5$$, the factor $$\frac{p-1}{2}$$ is coprime to $$2$$ (odd, so that squaring $$a$$ of order $$\frac{p-1}{2}$$ will not change its order).
Hence Daniel Fischer's hint, to consider the order of $$a^2$$, with the obvious exceptions ($$p=5$$ or $$a=0,\pm 1$$).