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?
$\begingroup$
$\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. ♦Commented Feb 25, 2018 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. ♦Commented Feb 25, 2018 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$– ShreevatsaRCommented Feb 26, 2018 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. ♦Commented Feb 26, 2018 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. ♦Commented Feb 26, 2018 at 6:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
