0
$\begingroup$

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

  • 0
    I added an example2012-06-14

2 Answers 2

1

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 .

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.

1

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

  • 0
    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$2012-06-15