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.

1. The $p-1$-Pollard algorithm.
2. The $p+$-William algorithm.
3. 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.

1. A. Granville, Aurifeuillian factors, Math Comp. Vol. 75, 2006.
2. E. Bach, Factoring with Cyclotomic Polynomials, Math. Comp. 1989.

Cyclotomic Factoring is a class of integer factoring algorithms. It is based on the Euler congruence $x^{\varphi(n)}-1 \equiv 0 \mod n$. There are a few well known special cases.

1. The $p-1$-Pollard algorithm.
2. The $p+$-William algorithm.
3. Aurifeuillian Factoring, this is the oldest.

The time complexity is $O(n^{1/4})$ arithmetic operations. Many authors have 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.

1. A. Granville, Aurifeuillian factors, Math Comp. Vol. 75, 2006.
2. E. Bach, Factoring with Cyclotomic Polynomials, Math. Comp. 1989.