7
$\begingroup$

All of the fast algorithms that I have seen which factor integers work by searching for smooth numbers. Are there any fast algorithms for factoring integers that don't work by searching for smooth numbers? Is there any reason to believe that it is possible to construct fast algorithms for factoring integers that don't work by searching for smooth numbers?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I find the terminology "friable" far superior to "smooth" for this arithmetic property. $\endgroup$
    – Greg Martin
    Commented Dec 2, 2013 at 7:53
  • $\begingroup$ @GregMartin, I agree. $\endgroup$
    – Craig Feinstein
    Commented Dec 2, 2013 at 13:33

4 Answers 4

Reset to default
7
$\begingroup$

This paper explains why smooth numbers play a key role in almost every modern integer factorization algorithm. Maybe it lists the exceptions, but I couldn't find them.

http://www.math.dartmouth.edu/~carlp/PDF/paper104.pdf‎

Improve this answer
$\endgroup$
4
$\begingroup$

There is a non-classical Shor's algorithm that does not use smooth numbers.

Classically there is no reason to believe there is no such efficient algorithm.

On the other hand regardless of searching for smooth numbers or not, look at Fortnow's comments http://blog.computationalcomplexity.org/2002/09/complexity-class-of-week-factoring.html on existence of polynomial time factoring algorithm.

If you know how to do discrete log, you can factor but current fastest techniques for this needs smooth numbers. It is well known you can convert certain beyond half minimum distance decoding instances of coding theory problems to DLOG instances. So if you find the fast algorithms for those decoding instances (which may not involve smooth numbers) you can calculate DLOG. And then factor integers.

Wiki says In number theory, "Dixon's factorization method (also Dixon's random squares method[1] or Dixon's algorithm) is a general-purpose integer factorization algorithm; it is the prototypical factor base method, and the only factor base method for which a run-time bound not reliant on conjectures about the smoothness properties of values of a polynomial is known." in http://en.wikipedia.org/wiki/Dixon%27s_factorization_method.

Continued fraction approach is based on Dixon's algorithm and hence may not need smooth numbers for analysis http://en.wikipedia.org/wiki/Continued_fraction_factorization.

Improve this answer
$\endgroup$
3
$\begingroup$

There are several different kinds of factoring and not all depend on smoothness in the same way. The first method historically was Fermat factoring: Search for solutions to $x^2-y^2=N$ by squaring numbers around $\sqrt{N}$. Continued fraction factorization methods do similar things as the quadratic sieve, but without the factor base as in [1]. Jacobian based methods (elliptic and hyperelliptic curves) search for a group of smooth order, but the runtime depends on the size of the sought-after factor, and smoothness is detected by a group calculation rather than trial factoring of sieving.

[1]http://www.ams.org/journals/bull/1931-37-10/S0002-9904-1931-05271-X/home.html

Improve this answer
$\endgroup$
2
$\begingroup$

Depends a bit on what you call a "fast algorithm", but Pollard rho doesn't search for smooth numbers.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I think that in this context, "fast" means "sub-exponential". But your point is well-taken, the question could be more precise. $\endgroup$
    – Joe Silverman
    Commented Dec 3, 2013 at 13:06

You must log in to answer this question.

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