"The problem of distinguishing prime numbers from composite numbers and of
resolving the latter into their prime factors is known to be one of the most
important and useful in arithmetic. It has engaged the industry and wisdom
of ancient and modern geometers to such an extent that it would be superfluous
to discuss the problem at length. Neverthless we must confess
that all methods that have been proposed thus far are either restricted to
very special cases or are so laborious and prolix that even for numbers
that do not exceed the limits of tables constructed by estimated men,
i.e. for numbers that do not yield to artificial methods, they try the
patience of even the practiced calculator... The dignity of the science
itself seems to require that every possible means be explored for the
solution of a problem so elegant and so celebrated."
-- Karl Friedrich Gauss, Disquisitiones Arithmeticae
(translation: A. A. Clarke)
"The invention of new [factorization] methods may push off the
limits of the unknown a little farther, just as the invention of a
new astronomical instrument may push off a little the boundaries of
the physical universe; but the unknown regions are infinite, and if
we could come back a thousand years from now, we should no doubt find
workers in the theory of numbers announcing in the journals new schemes
and new processes for the resolution of a given number into its factors."
-- D.N. Lehmer