On smoothness assumptions in Integer factorization I have came across a lot of factorization methods and most of them seem to assume smoothness of some numbers.
For example


*

*When $p-1$ is smooth

*When $|E(\mathbb{F}_p)|$ is smooth. (Elliptic curve factorization)

*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$  ?
 A: Yes. There is the $p+1$ method described by
Williams (1982)
and a cyclotomic generalization by
Bach, Shallit (1989).
One problem with higher-degree cyclotomic polynomials is that their values
grow so quickly that the density of smooth values below some bound is much
lower than for the $p-1$ and $p+1$ methods.
A general problem with the cyclotomic methods, including $p\pm1$,
is that $p$ rigidly determines the integer value that we require to be smooth.
If it is not smooth, the method will fail, and retrying cannot be expected
to help, except perhaps retrying with a larger smoothness bound.
The elliptic-curve method, proposed 1985 by H. W. Lenstra Jr. and
discussed soon after by e.g. Brent (1985),
is less limited.
The method succeeds if some randomly chosen elliptic curve happens to have
smooth order over the finite field with $p$ elements, but that order is not
fixed to e.g. $p\pm1$, but can vary around $p+1$ in an interval
of width about $4\sqrt{p}$, depending on the curve chosen.
So if a run fails, one can simply try another curve and again
hope to hit some smooth value near the unknown $p$ and thus succeed.
Therefore, higher cyclotomic methods are rarely found in practice.
Typically, the following methods are attempted:


*

*Methods for smaller factors: Trial division, Pollard Rho, ...

*one run of the $p-1$ method,

*about three attempts of the $p+1$ method (there is some guessing
of a suitable nonsquare$\bmod{p}$ involved,
therefore one attempt might not be enough),

*a larger number of runs of the elliptic-curve method,
each with a newly chosen curve,

*an even larger number of curves with increased smoothness bounds,

*If applicable (that is, if the length of the number to be factored
and the amount of computing power available allow it),
the quadratic sieve or the number field sieve.


Happy factoring.
