# How to know in which half $n$ exist of $a^n$ mod $p = r$ for a known $r$?

$a,p,r,n$ are positive integers

$p$ is an odd prime

$$a^n\pmod p = r$$

Assume that we have two halves for $n$ values:

Starting from $$r = a \,\,\,\text{to}\,\,\,r = p - 1$$

The other half is from $$r = p - a\,\,\,\text{to}\,\,\, r = 1$$

Given $a,p$ and $r$

Is it possible to know in which half does $n$ exist, without having to find $n$ value?

Edit: Example:

For $a=2$, $p=11$, $n$ from $1$ to $10$:

First half:

$n=1, r=2=a$

$n=2, r=4$

$n=3, r=8$

$n=4, r=5$

$n=5, r=10=p-1$

Second half:

$n=6, r=9=p-a$

$n=7, r=7$

$n=8, r=3$

$n=9, r=6$

$n=10, r=1$

• Where does $\,n\,$ enter in your formulae? I think that where you wrote $\,a^x\,$ you actually meant $\,a^n\,$ , so I'll edit your question. Please do check this is corret, @Must\ – DonAntonio Jun 14 '12 at 15:58
• I also am not sure what halves are you referring to: if one is with $\,a\leq r\leq p-1\,$, the other one would have to be for $\,1\leq r\leq a-1\,$ , and not what you wrote. I assume here you meant the non-zero residues clases modulo $\,p\,$ , and of course these won't be actual halves unless $\,a=\frac{p-1}{2}\,$ – DonAntonio Jun 14 '12 at 16:02
• Do you mean that the values of $n$ range from $r=a$ to $r=p-1$ or is it $n=a$ to $n=p-1$? Is $a$ known to be a generator (primitive root)? I so, I doubt anything useful can be said about the location of $n$ without expensive (discrete logarithm) calculation. – André Nicolas Jun 14 '12 at 16:05
• I added an example – Must Jun 14 '12 at 20:46

As @DonAntonio pointed out, for an arbitrary choice of $a,r$ there may not be a solution. And even if there is a solution, it is not necessarily true that there's an $m$ with $a^{2m}\equiv 1$ and $a^{m}\equiv p-1$ as you suggested in your comment. For example consider $2^3\equiv 1 \pmod{7}$.

So let us assume that $a$ is a primitive root modulo $p$ so in fact there is an index $n$ for every $1\le r <p$.

In a literal sense it is possible to know which half $n$ is in without necessarily finding it. You can compute $a^i \bmod p$ for $i=1,2,\ldots$ and stop if you find $r$ or if you get to $i=(p-1)/2$. But I suspect you were looking for something more efficient.

It is unlikely that a much more efficient method is known, since having one would allow computation of discrete logarithms quickly.

If given $r$ you can find that $n$ is in the "first half", then choose a $t_1$ close to $p/4$ and solve for $n_1$ such that $a^{n_1}\equiv ra^{t_1}\pmod{p}$. This let's you determine whether $n$ is in the first or second quarter (more or less). If $n$ was in the "second half" solve $a^{n_1}\equiv ra^{-t_1}$ for $n_1$ to place $n$ in the third or fourth quarter.

Similarly, pick $t_2$ close to $p/8$ and solve $a^{n_2}\equiv ra^{\pm t_1\pm t_2}$ with signs as necessary to place $n$ in an eighth of the range. You can use a binary search this way to solve for the exact value of $n$ in $O(\log p)$ steps.

I think more conditions must be imposed on the question for it to have a definite answer. For example, for $\,p=5, a=-1\,,\,r=2\,$ there's no solution to $\,a^n=r\pmod 5\,$ ...

One condition (perhaps a too strong one) is to require $\,a\,$ to be a primitive root modulo $\,p\,$ ...

• I don't know the needed conditions, just assuming for the given values there exist a positive integer m, $n=m$ for $r=p-1$, and $n=2m$ for $r=1$ – Must Jun 15 '12 at 7:52