When was the problem of factoring integers explicitly considered, what was the oldest factoring algorithm?

Question

I know Gauss made it clear that he wanted an efficient solution to the problem in 1801. In his Disquisitiones Arithmeticae he calls all factoring algorithms "laborious and prolix", surely a 19th-century notion of superpolynomial.

I know Euclid's Elements essentially contains the fundamental theorem of arithmetic, so perhaps Euclid and ``his peers'' were already interested in the question in some more or less implicit way.

I would like to know the first publication that has --- like Gauss --- made it loud and clear that the problem should be given due attention. So, for example, the first factoring algorithm effectively does that. The author must have studied enough to find it and, therefore, I could make the case that he saw the importance. (Even if he found the algorithm sort by chance or indirectly.)

Essentially, I'm interested in giving a date of when the problem becomes, say, pressing.

Answer 1

Trial division was used even before Pythagoreans, Euclid's number theory allowed restricting trials to primes, with the sieve of Eratosthenes identifying the primes. Al-Banna explicitly limited the size of tried factors by the square root, as did Fibonacci later. More sophisticated methods before Gauss were given by Fermat and Euler. There is no cutoff date, I am afraid, the "pressure" grew gradually, see Mollin, Brief History of Factoring and Primality Testing.