Say you're trying to use a computer to factor a number, N. N is large and you want to stop as soon as possible in the case that it's a prime.
If you don't have a lot of memory to work with, then the obvious thing is some kind of optimized
trial division. (Which is not the same as - and not to be confused with - the
Sieve of Eratosthenes. SoE has a
(
Read more... )