1
$\begingroup$

Defining $$ o_r(n) = \min \left\{ \hspace{1mm} k \in \mathbb{N} \hspace{2mm} | \hspace{2mm} n^k \equiv 1 \hspace{3mm} (\text{mod } r) \hspace{1mm} \right\} $$ How can we show that finding the smallest $r$ such that $o_r(n) > \log^2(n)$ can be done in polynomial time?

$\endgroup$
5
  • 2
    $\begingroup$ What have you tried? Can you think of any algorithm? What is its running time? I suggest you start by thinking of the stupidest thing you can imagine that might conceivably work, and start with that. That will help you make progress and at least see what the interesting part is. I think the challenging part is not finding an algorithm, but proving it works (which seems to require some theorem about number theory). Also, what's the context where you encountered this? What's the motivation? $\endgroup$ – D.W. Feb 25 '18 at 16:30
  • 1
    $\begingroup$ What do you mean by polynomial time? Do you mean polynomial in $n$ or polynomial in $\lg n$? $\endgroup$ – D.W. Feb 25 '18 at 23:46
  • $\begingroup$ @D.W. Found the context (thought I recognized it when I first saw the question) — this turns up in the analysis of the famous “PRIMES is in P” primality test of Agrawal, Kayal and Saxena. I'm deleting my answer, at least until the OP adds appropriate details to the question. $\endgroup$ – ShreevatsaR Feb 26 '18 at 0:20
  • $\begingroup$ After looking through M Smith's posts on Math.SE, it appears that M Smith has been reading the "PRIMES is in P" paper and wants to understand why it runs in polynomial time. Step 2 of that algorithm asks to find the smallest $r$ such that $o_r(n) > \log^2 n$. If you keep reading in that paper you immediately find the core to the justification why this can be done in polynomial time. $\endgroup$ – D.W. Feb 26 '18 at 6:47
  • 1
    $\begingroup$ M Smith, if you had told us more about the context from the start, we could have pointed to that section of the paper. And I'm not sure why you didn't keep reading the paper, as was previously suggested to you. I'm a little frustrated that the question didn't provide this information from the start. $\endgroup$ – D.W. Feb 26 '18 at 6:47
1
$\begingroup$

It appears you are asking because you are interested in understanding the famous "PRIMES is in P" paper and why its algorithm runs in polynomial time. Finding such an $r$ is exactly step 2 of their algorithm.

As was explained to you previously on Math.SE, the paper explains why its algorithm runs in polynomial time. The explanation is terse and assumes the reader will be able to make the missing connections, but the key ideas are there. If you keep reading in the paper it presents the crucial fact: the smallest such $r$ has size at most $r \le \max\{3, \lceil \log^5 n \rceil\}$ (see Lemma 4.3, which is just a few paragraphs after the statement of the algorithm). Consequently, there is a very simple algorithm to find such an $r$: try each $r$ in turn, i.e., try $r=1$, then $r=2$, then $r=3$, checking each candidate value of $r$ to see if it satisfies the condition. Output the first one you find that satisfies the condition. Thanks to the fact in the paper, you'll only need to try $O(\log^5 n)$ many such $r$, which is polynomially many. Moreover, you can check the condition for a given $r$ in polynomial time. Thus, the total running time is polynomial in $\log n$.

In the future, if you have a question about some aspect of the paper, please tell us in the question what paper you are reading. More generally, tell us about the context around your question and the motivation. Also, when asking about some aspect of a paper, I encourage you to read the entire paper before asking -- sometimes the answer to your question might be found later in the paper.

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