Timeline for Mod $N^2$ evaluation of a polynomial defined by first $N-1$ roots
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 11, 2020 at 23:16 | comment | added | Richard G. | Thank you. That is a noticeable improvement over just calculating all the terms! | |
| Aug 10, 2020 at 10:08 | comment | added | Ben Smith | Pollard has an algorithm which can be used to evaluate $f(x)$ in $O(\sqrt{N})$ operations in $\mathbb{Z}/N^2\mathbb{Z}$. Pollard's paper ("Theorems on factorization and primality testing") is not available freely online, but there's a convenient description of the algorithm in Section 2.1 of Bostan's "Computing the N-th Term of a q-Holonomic Sequence". | |
| Aug 7, 2020 at 22:21 | comment | added | Richard G. | The latter, computing $f(\alpha)$. | |
| Aug 7, 2020 at 12:03 | comment | added | Ben Smith | When you say "evaluating $f$", do you mean computing the coefficients of $f$, or computing $f(\alpha)$ for $\alpha$ in $\mathbb{Z}/N^2\mathbb{Z}$ (or some $\mathbb{Z}/N^2\mathbb{Z}$-algebra)? | |
| Aug 6, 2020 at 8:13 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals from title
|
| Aug 6, 2020 at 6:02 | review | First posts | |||
| Aug 6, 2020 at 6:49 | |||||
| Aug 6, 2020 at 5:56 | history | asked | Richard G. | CC BY-SA 4.0 |