Fermat's factorisation method

Question

We all know Fermat's factorisation method, but how do we know that the values of $(s-t)$ and $(s+t)$ in the next proof are always primes?

When we say "factorisation" do we always mean the factorisation in primes?

Answer 1

In general, we don’t distinguish between algorithms for factoring into primes and algorithms for “merely” factoring into two smaller numbers (i.e. non-trivial factors). There are a few reasonable justifications for this:

1. It is far more common to find an non-trivial algorithm that finds some factor rather than exclusively prime factors. I can only think of trial division as something capable of the latter.
2. In a cryptographic setting, if you can find any non-factor then any system relying on keeping the prime factorization secret would already be considered compromised. In most scenarios such as RSA, there are only two prime factors in the first place.
3. Once you have a general way to find non-trivial factors, you can just apply that repeatedly to each non-prime factor until you drill down to the prime factors. This is aided greatly by the fact that it is comparatively very easy to identify when a number is prime.

In the special case of Fermat factorization, it’s a fair point that just because the initial number is easy to factor (on account of being close to a square), it isn’t necessarily the case that the factors will be easy to factor by the same method. But that doesn’t invalidate the general idea that it isn’t useful to draw a hard line between factoring algorithms and prime-factoring algorithms.