Factoring with Cyclotomic Polynomials

From MaRDI portal





The authors generalize several methods for factoring \(N=pq\dots\) by algorithms of the ``\(p-1\) type. Take the \(k\)-cyclotomic field determined by the polynomial \(\Phi(x)\) so \(x^k-1=\Phi (x)\Psi(x)\) (for the ``\(p-1\) type, \(k=1\) and \(\Phi =x-1)\). Choose a ``lucky \(t\) in a subfield of prime order, and hope that for some \(i\) \((\le k)\) we can find \(p\) as the gcd of \(N\) and the coefficients of \(t^{\Psi (\sigma^i)E}-1,\) for \(\sigma\) the Frobenius symbol. Here \(E\) is a ``small factorial, just large enough to be divisible by \(\Phi(p)\), with more luck. An analysis made by the ERH shows that the luck is polynomially viable in a probabilistic sense, and it is better to have \(t\) in a higher field than \(\mathbb Q\), because we can expect different Artin residue symbols for \(p,q,\ldots\) to produce a gcd which will split the different factors in \(N\). The method is illustrated for \(k=6\), \(\Phi =x^2-x+1\), and it requires an algebraic system (MACSYMA) to handle the polynomials modulo \(N\) involved in calculating powers of \(t\) in \(\mathbb Q(t)\). [See \textit{H. C. Williams} and \textit{J. S. Judd}, Math. Comput. 30, 867--886 (1976; Zbl 0342.10007)].




Cited in
(28)


Describes a project that uses

Uses Software






This page was built for publication: Factoring with Cyclotomic Polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3809851)