Is there a fast algorithm to generate all cyclotomic polynomials $\Phi_n$ for which the degree of $\Phi_n$ is a fixed constant $d?$ This is obviously related to the "inverse totient" function: compute all $n$ for which $\phi(n) = d.$
$\begingroup$
$\endgroup$
2
asked Dec 22, 2013 at 1:53
-
4$\begingroup$ This arxiv.org/pdf/math/0404116v3.pdf paper of Contini, Croot and Shparlinki produces a polynomial time algorithm to compute $n$ for "almost all d" (the authors also give complexity for all $d.$) $\endgroup$– AlvinCommented Dec 22, 2013 at 6:04
-
3$\begingroup$ Do you want to write down those cyclotomic polynomials ? Because if you do, then the complexity is at least proportional do $d$. So you might as well use an explicit lower bound on $\phi(n)$, and use it to list all the possible $n$ and compute all of their $\phi(n)$ with a sieve, which will be $d^{1+o(1)}$. $\endgroup$– AurelCommented Dec 22, 2013 at 9:33
Add a comment
|