# Euclidean Algorithm vs Factorization

Can someone give me an explanation targeted to a high school student as to why finding thegcd of two numbers is faster using the euclidean algorithm compared to using factorization, there should be no algorithm efficiency involved, just a general explanation, something my brother in grade 9 can understand.

-
For large numbers with large factors, it's way much easier to take quotients and remainders (or even just subtract) than to factor. –  Ｊ. Ｍ. Oct 18 '10 at 0:14
@J.M.: But integer factorization algorithms also take quotients and remainders. That alone doesn't say much. It's the number of such operations that matters. –  Bill Dubuque Oct 18 '10 at 0:21
Hm, should've been more precise: it takes more quotients/remainders to factor than to compute a GCD, tho I'm not sure why "there should be no algorithm efficiency involved" is in the question. –  Ｊ. Ｍ. Oct 18 '10 at 0:29
because my brother has no understanding of algorithm efficiency :( –  fmunshi Oct 18 '10 at 1:38
How can you hope to explain this if he has "no understanding of algorithm efficiency"? That seems central to the question. See Arturo Magadin's answer. –  Ross Millikan Oct 18 '10 at 2:53

The Euclidean algorithm is a definite recipe that tell you exactly what to do at any given step; there is no guessing, no trial and error involved. Trying to factor a number will (even with some of the best methods currently known) involve guesses and trial-and-error; trial division is of course the classic example, but even some of our best methods (elliptic curve factorization and number field sieve, to name two) all involve some "random guessing" and trials to try to find factors. Sure, they are more clever ways of testing than simply trying everything out there, but you still usually end up doing a lot of grunt work along the way that leads nowhere (dividing by a number that is not a factor in trial division; not getting good relations in the number field sieve; performing all computations on an elliptic curve modulo $n$ and not finding any non-invertible elements), or performing good-looking computations that end up with a trivial factor ($1$ or $n$). In essence, this is "wasted effort", waste that simply does not occur with the Euclidean algorithm.

Added: Note that this is a reflection of our current known factoring methods, and not necessarily (as Bill Dubuque points out, we just don't know either way) an inherent difficulty in factoring. You don't want to compare "factoring" with "Euclidean algorithm", you want to compare specific ways of factoring with the Euclidean algorithm. And the ways we know (and the ways the high school students know, which are likely to be trial division plus a handful or two of divisibility tests to make the former simpler) have these drawbacks.

Perhaps an analogy would be that the Euclidean algorithm is like having a full recipe to prepare a dish, and all the ingredients laid out ready to be used; factorization involves starting to prepare the dish, rummaging through your supplies for ingredients, and possibly realizing part-way through that you don't have the right ingredients, forcing you to start over from scratch with a new dish for which you hope you do have the ingredients. Even if the former situation involves a complex dish while the latter is a series of attempts at very simple and quick dishes, chances are you will spend less total time with the full-recipe-and-all-ingredients-laid-out-method than the let's-try-this-and-hope-we-have-all-the-stuff method.

-
I don't think that analogy works. It's not a question of searching, guessing... or not. In fact some of the fastest gcd algorithms can be viewed as searching in the remainder sequence. It's simply a matter of how fast you can perform the algorithm, whether it employs brute-force searching or not. We simply don't know any fast algorithm for factorization nor do we have any deep understanding of whether or not factoring is intrinsically hard. –  Bill Dubuque Oct 18 '10 at 3:09
Yes, it's not just a question of searching, but of efficient searching. We do not have any way of doing efficient searching for factors, for whatever reason. The more advanced methods maximize the odds of hitting on a right one through clever ideas, but there is still a lot of blindly stumbling around going on in those algorithms. That is part of the "difficulty" of the problem as it currently stands. Certainly I agree that we do not have any deep understanding of whether factoring is "intrinsically hard", but I don't think the question, reasonably interpreted, was asking that. –  Arturo Magidin Oct 18 '10 at 3:24

It boils down to the fact that currently known factorization algorithms are much slower than the fastest known gcd algorithms. It would be difficult to say much more than that that would be comprehensible to a 9'th grade student (in fact one might argue that not much more than that is even known to experts).

-

For very small numbers then factorization is quicker than the Euclidean algorithm. But the Euclidea algorithm gives more; it allows one to compute reciprocals in modular arithmetic.

For larger numbers, finding factorizations may be slow or even practically impossible, but the Eulcidean algorithm still works well. Also modern factorization methods from Pollard rho to the number field sieve, make essential use of the Euclidean algorithm.

-