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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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.