Timeline for How to construct a small coprime?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 14, 2017 at 23:45 | vote | accept | Igor Pak | ||
| Sep 14, 2017 at 23:45 | |||||
| Sep 14, 2017 at 15:22 | comment | added | Gerhard Paseman | I guess a valid inference is that I am different from most people. Gerhard "Or Else I'm Mostly Wrong" Paseman, 2017.09.14. | |
| Sep 14, 2017 at 15:17 | comment | added | Timothy Chow | @GerhardPaseman : If Igor's problem is co-NP hard then either P = NP or Cramér's hypothesis on prime gaps fails badly. Either one of these would surprise most people. | |
| Sep 13, 2017 at 19:37 | comment | added | Gerhard Paseman | Igor, it would not surprise me that what you seek to solve is CoNP hard. If so, do you still want to reject alternatives? @Steven, that is in the worst case. If time is important, one can try several starting $d$ and not test so many. However, I am offering what I know, and I may never be able to give Igor the answer he wants. Gerhard "Sometimes The Answer Takes Longer" Paseman, 2017.09.13. | |
| Sep 13, 2017 at 19:12 | comment | added | Steven Stadnicki | Even with sieving savings you're still talking about looking at $O(n^{2-\epsilon})$ numbers at a minimuim, which makes this substantially more expensive than the naive primality tests - even testing all the numbers between $n$ and $2n$ is only going to take $O(n^{1+\epsilon})$ time and it's known that one needs to test far fewer than that - it should be more like $O(n^{21/40+\epsilon})$. | |
| Sep 13, 2017 at 16:49 | comment | added | Igor Pak | You misunderstand the question. I want deterministic algorithm which works in poly(log n) time. I want q to be as small as possible, but can live with somewhat larger q if that's the best known. None of what you wrote moves in that direction. | |
| Sep 13, 2017 at 15:59 | comment | added | Gerhard Paseman | Further, the large bound of Iwaniec represents the worst case. On average, $c-d$ is more like $\log P$, and my gut tells me (because I don't know any literature to quote) that the extreme cases can probably be avoided after $\log n$ (not too stupid) trials. Gerhard "You Are Not Always Unlucky" Paseman, 2017.09.13. | |
| Sep 13, 2017 at 15:39 | comment | added | Gerhard Paseman | Yes. And if running primality tests in that range is cheap, then that's the way to go. However, It may be that gcd is cheaper on larger numbers. If Igor has some specific application in mind, he might prefer not doing primality tests. Gerhard "Having Options Can Be Good" Paseman, 2017.09.13. | |
| Sep 13, 2017 at 15:35 | comment | added | Lucia | As already observed in the problem there is a prime between $n$ and $2n$. This is already stronger than what would follow from Iwaniec's bound on the Jacobsthal problem. | |
| Sep 13, 2017 at 15:28 | comment | added | Gerhard Paseman | The estimate is in Arxiv 1311.5944, if you want to skip question 37679. Gerhard "Is On A Link Diet" Paseman, 2017.09.13. | |
| Sep 13, 2017 at 15:24 | history | answered | Gerhard Paseman | CC BY-SA 3.0 |