A push-button program to factor integers requires a fairly complicated parallelization pattern, so could serve as a model to test any parallelization or concurrency toolkit or language.
Several algorithms: Trial division, Pollard rho, elliptic curve method, quadratic sieve all to be run in parallel. Restart all algorithms whenever one finds a factor. If found factor is composite, continue the factorization recursively.
ECM and QS are internally parallelizable.
Adjust thread priorities depending on the probability of each algorithm discovering a new factor based on how much effort already expended with it.
No comments :
Post a Comment