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

  • $\begingroup$ 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\ $\endgroup$ – DonAntonio Jun 14 '12 at 15:58
  • $\begingroup$ 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}\,$ $\endgroup$ – DonAntonio Jun 14 '12 at 16:02
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Jun 14 '12 at 16:05
  • $\begingroup$ I added an example $\endgroup$ – 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.

| cite | improve this answer | |

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\,$ ...

| cite | improve this answer | |
  • $\begingroup$ 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$ $\endgroup$ – Must Jun 15 '12 at 7:52

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.