I have came across a lot of factorization methods and most of them seem to assume smoothness of some numbers.

For example

  1. When $p-1$ is smooth
  2. When $|E(\mathbb{F}_p)|$ is smooth. (Elliptic curve factorization)
  3. Smoothness of prime ideals in Number field sieves.

I want to know whether any other notions are known to be equivalent to factoring like smoothness of $p+1$ or $p^2+1$ ?


1 Answer 1


See my paper with Eric Bach, "Factoring with cyclotomic polynomials", where we show that if the cyclotomic polynomial $\Phi_k(p)$ is $B$-smooth for any $p$ dividing $N$, then we can factor $N$ in time polynomial in $\log N$ and $k$ and $B$. In particular this gives a $(p+1)$-method (see the earlier work of Williams) and $(p^2+1)$ method.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.