4
$\begingroup$

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$ ?

$\endgroup$

1 Answer 1

2
$\begingroup$

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:

  1. Methods for smaller factors: Trial division, Pollard Rho, ...
  2. one run of the $p-1$ method,
  3. 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),
  4. a larger number of runs of the elliptic-curve method, each with a newly chosen curve,
  5. an even larger number of curves with increased smoothness bounds,
  6. 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .