And -- to be totally explicit -- although the naïve way of finding GCD is based on factoring, in fact finding GCD can be done very quickly with Euclid's algorit

And -- to be totally explicit -- although the naïve way of finding GCD is based on factoring, in fact finding GCD can be done very quickly with Euclid's algorithm, without any need for factoring.