Timeline for Fastest deterministic factoring algorithm in subexponential space?
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 5, 2018 at 21:15 | comment | added | Turbo | @Aurel What do you mean by dimension $1$? | |
| Mar 16, 2018 at 4:21 | vote | accept | Dan Brumleve | ||
| Jan 9, 2018 at 0:04 | answer | added | Alexey Milovanov | timeline score: 5 | |
| Jan 8, 2018 at 20:14 | comment | added | Dan Brumleve | @AlexeyMilovanov, wait, the deterministic algorithm that uses $N^{o(1)}$ space you're describing also uses $2^{N^{o(1)}}$ time, since it has to find a suitable combination of "random" bits, right? I think Dixon's method is not of interest unless there is some way to choose the candidate squares deterministically. | |
| Jan 8, 2018 at 18:41 | comment | added | Aurel | @AlexeyMilovanov Ah yes that is true, since it is in dimension 1. Nice! | |
| Jan 8, 2018 at 17:53 | comment | added | Alexey Milovanov | @Aurel Dixon's algorithm has a rigorous proof of its (subexponential) run-time bound. | |
| Jan 8, 2018 at 17:42 | comment | added | Alexey Milovanov | en.m.wikipedia.org/wiki/Dixon%27s_factorization_method | |
| Jan 8, 2018 at 16:36 | comment | added | Aurel | @AlexeyMilovanov Good point! But even then, as far as I am aware, the analysis of the number field sieve is based on heuristics, so that would still not give a theorem. Or am I misremembering? | |
| Jan 8, 2018 at 15:04 | comment | added | Alexey Milovanov | @Aurel but it uses at most $N^{o(1)}$ random bits. Hence there exists a deterministic algorithm that uses $N^{o(1)}$ space that finding suitable "random" bits and so, solving the problem (since it is easy to verify here that the result of an algorithm (factorization) is right). | |
| Jan 7, 2018 at 14:42 | history | edited | Dan Brumleve | CC BY-SA 3.0 |
added 175 characters in body
|
| Jan 7, 2018 at 9:19 | comment | added | Aurel | @EmilJeřábek The sieve algorithms are not deterministic. | |
| Jan 7, 2018 at 7:49 | comment | added | Emil Jeřábek | The general number field sieve runs in time $N^{o(1)}$, and therefore in space $N^{o(1)}$. | |
| Jan 7, 2018 at 1:31 | history | edited | Dan Brumleve | CC BY-SA 3.0 |
deleted 1 character in body
|
| Jan 7, 2018 at 1:26 | history | edited | Dan Brumleve | CC BY-SA 3.0 |
added 170 characters in body
|
| Jan 7, 2018 at 1:13 | history | asked | Dan Brumleve | CC BY-SA 3.0 |