Timeline for Efficient deterministic algorithms of factorizing
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 10, 2017 at 1:41 | comment | added | Noam D. Elkies | Find a quadratic nonresidue $r \ll \log^2(p)$ (if memory serves) by trying all candidates. Once you have a non-square in a finite field it's easy to extract square roots. The existence of a quadratic nonresidue of size polynomial in $\log p$ is a known consequence of the ERH. (Not "EGRH": I mean the analogue of Riemann for Dirichlet $L$-series; here we need the $L$-series associated to the quadratic character $\bmod p$.) | |
| Sep 10, 2017 at 1:22 | comment | added | Turbo | @NoamD.Elkies what is the algorithm under $EGRH$? | |
| Jul 6, 2016 at 0:18 | comment | added | Noam D. Elkies | There isn't even an algorithm that is unconditionally proved to factor quadratics over large prime fields in polynomial time. ("Unconditionally" because there is such an algorithm under the extended Riemann Hypothesis.) | |
| Jul 5, 2016 at 23:22 | history | edited | Gerry Myerson | CC BY-SA 3.0 |
typos
|
| Jul 5, 2016 at 20:40 | comment | added | Alexey Milovanov | @MaxAlekseyev my question is about finite fields only | |
| Jul 5, 2016 at 20:39 | history | edited | Alexey Milovanov | CC BY-SA 3.0 |
added 9 characters in body
|
| Jul 5, 2016 at 20:27 | comment | added | Max Alekseyev | @Alexey: It is still not clear. Perhaps, you meant $\mathbb{Z}_q$, but even if so, $\mathbb{F}_q$ is not the same as $\mathbb{Z}_q$ when $q$ is not prime. | |
| Jul 5, 2016 at 19:41 | comment | added | Alexey Milovanov | @MaxAlekseyev, yes, of course. I have edited my question, I hope now it is clear | |
| Jul 5, 2016 at 19:39 | history | edited | Alexey Milovanov | CC BY-SA 3.0 |
deleted 22 characters in body
|
| Jul 3, 2016 at 18:34 | comment | added | Alexey Milovanov | @MichaelZieve thank you, I was misled by the book "Number-theoretic Algorithms in Cryptography" by Vasilenko where he did not note that $q$ must be prime in the algorithm of Shoup | |
| Jul 3, 2016 at 18:20 | comment | added | Michael Zieve | Try searching via google. This will lead you to the wikipedia page en.wikipedia.org/wiki/… and to a survey paper by von zur Gathen and Panario, which tell you what's known. There is no known deterministic polynomial time algorithm for this which works in every case. | |
| Jul 3, 2016 at 17:53 | history | asked | Alexey Milovanov | CC BY-SA 3.0 |