Cyclotomic Factoring is a class of integer factoring algorithms. It is based on the Euler congruence $x^{\varphi(n)-1 \equiv o \mod n$. There are a few well known special cases.
- The $p-1$-Pollard algorithm.
- The $p+$-William algorithm.
- Aurifeuillian Factoring, this is the oldest.
The time complexity is $O(n^{1/4})$ arrithmetic operations. Many authors havd tried to obtain $O(n^{1/5})$, but no major reduction in complexity have been achieved in the last few decades.
There is a large literature on this topic, a few are listed.
- A. Granville, Aurifeuillian factors, Math Comp. Vol. 75, 2006.
- E. Bach, Factoring with Cyclotomic Polynomials, Math. Comp. 1989.