Skip to main content
Theoretical Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

5
  • 7
    $\begingroup$ What does the algorithm do? Essentially, it takes $r$ and a random $\ell \leq r$ and outputs $r' = r/gcd(\ell,r)$. so if you check all small multiples of $r'$, then it is very likely that $r$ is one of these. Why does $(\log n)^{1+\epsilon}$ give $O(1)$? That's number theory. Andrew Odlyzko is a number theorist, and I consulted him about this problem, but I've completely forgotten his justification for this. $\endgroup$ Commented Jul 26, 2015 at 16:39
  • $\begingroup$ Thanks! It looks like I need to look for a number theorist myself! $\endgroup$ Commented Jul 27, 2015 at 6:16
  • 1
    $\begingroup$ You may want to try MathOverflow. $\endgroup$ Commented Jul 27, 2015 at 18:06
  • $\begingroup$ I’m thinking about it. I will probably reformulate it in a more “number theoretic way” for that, if I don’t get the answer soon. I think it can be rephrased as a sum of totient functions. $\endgroup$ Commented Jul 27, 2015 at 18:20
  • 2
    $\begingroup$ @Kaveh : The related question on MathOverflow, asking a related number theory question which, I think, is equivalent. $\endgroup$ Commented Jul 31, 2015 at 15:51