Allow long running factorizations to yield

[DannyKong12]

I'm trying to write a program where the solution requires a prime factorization of an integer from a list of many possible candidate solutions. Any factorization will do, but obviously some numbers are harder to factor than others. WHP at least one of the numbers has some small factors. My approach is simply to try to factor a random candidate for some amount of time, and abandon it to move on to another solution if its taking too long.

I would like to do this with a timeout macro/function see this for example, but since factor, in particular pollardfactor doesn't yield(), such a macro won't work. From limited testing, in hard instances, this inner loop can run quite long.

Primes.jl/src/Primes.jl

Lines 544 to 553 in 42b97a5

	while k < r && G == 1
	ys = y
	for i in 1:(m > (r - k) ? (r - k) : m)
	y = y^2 % n
	y = (y + c) % n
	q = (q * (x > y ? x - y : y - x)) % n
	end
	G = gcd(q, n)
	k += m
	end

It would be really helpful if pollardfactor could yield from time to time, (perhaps once every X iterations of that loop, and once at the end). Someone who knows the code a bit better could probably find a better spot to place the yields that minimizes the impact on runtime for smaller instances.

[oscardssmith]

I think the better approach here would be probably to finish up my ECM/Quadratic Sieve PRs since they are asymptotically a bunch faster.

[DannyKong12]

Yeah, that would certainly help as well. Although I think its unavoidable that you will never run into a long running instance of factor. I'm testing a fork with just one additional yield() inside this loop, and it was enough for me. See the change here:

https://github.com/DannyKong12/Primes.jl/blob/ffe33dec8d6da619faa373ecb9baf9014bd82d85/src/Primes.jl#L553-L555

From a small amount of testing, this doesn't impact performance in a measurable way, it yields maybe ~10 times when factoring a large semiprime. For numbers with small factors it doesn't appear to affect things at all, since pollardfactor isn't used. This is a big improvement if you are attempting to factor many large numbers like I am, you can robustly interrupt a factor instance in ~1/10th of its total runtime.

It would be minimal overhead to add even more, and that would let the scheduler more finely control the execution of factor, but its probably not necessary.

[oscardssmith]

Fair enough. If you make a PR, I'll merge.