2
$\begingroup$

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?

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

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$).

$\endgroup$

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.