Timeline for Higher roots modulo prime complexity best algorithm
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 9, 2019 at 18:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 10, 2018 at 18:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 10, 2018 at 17:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 11, 2018 at 17:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Sep 11, 2018 at 17:00 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 12, 2018 at 18:47 | comment | added | Emil Jeřábek | I don’t know if there are better randomized algorithms known for the specific case of $\ell$-th roots. (Certainly various steps in the generic factoring algorithms can be simplified, but an altogether different method would be needed to get a superpolynomial speedup.) | |
| Aug 12, 2018 at 18:41 | comment | added | Dror Speiser | @EmilJeřábek True that. I think the OP is asking what the best method is, and whether the complexity is a particular one. But maybe I misunderstood your comment: are randomized polynomial factoring algorithms, that take $poly(\ell log(p))$ time, the best known? With no dependence on $\ell$? | |
| Aug 12, 2018 at 18:36 | comment | added | Emil Jeřábek | @DrorSpeiser This depends on whether you write $\ell$ in unary or in binary, but in any case, polynomial in $\ell$ is exactly what the OP asks for. | |
| Aug 12, 2018 at 18:29 | comment | added | Dror Speiser | Polynomial time polynomial factoring gives polynomial time in $\ell$ - not in $log(\ell)$ - which is not polynomial time in the input length. | |
| Aug 12, 2018 at 16:37 | answer | added | Igor Rivin | timeline score: -1 | |
| Aug 11, 2018 at 11:53 | comment | added | KConrad | @EmilJeřábek saying efficient deterministic square root calculations mod $p$ are "an open problem" and nothing more about them is not telling the whole story, since it might suggest there is no idea what such an algorithm might look like. The paper of Adleman, Manders, and Miller at cs.cmu.edu/~glmiller/Publications/AMM77.pdf provides such an algorithm (for square roots) under GRH for Dirichlet $L$-functions. | |
| Aug 11, 2018 at 9:57 | comment | added | Emil Jeřábek | There are randomized polynomial-time algorithms for factoring of polynomials over finite fields, your problem is a special case of that. Efficient deterministic algorithms are an open problem already for square root computation. | |
| Aug 11, 2018 at 6:10 | review | First posts | |||
| Aug 11, 2018 at 7:24 | |||||
| Aug 11, 2018 at 6:05 | history | asked | Amal Duriseti | CC BY-SA 4.0 |