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?

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

4 Answers 4

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

$\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.

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

$\endgroup$
2
$\begingroup$

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

$\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$ Dec 3, 2013 at 13:06

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.