Thursday, January 24, 2013

[seihpavf] Parallel factorization implementation

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 :