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? 
 A: 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$).
