Skip to content

Speed up of worst case factorization

J Sory requested to merge JASory/gnome-calculator:gnome-43 into master

The worst case of factorization of x is when x is prime. This merge request inserts a Miller test for x > 2^32 to check for this worst case and block factorization attempt if x is prime. In the case of x being composite it will almost surely be detected (e < 1/3E+6) by the first strong fermat test (called is_sprp in the source code), resulting in an inconsequential slow-down for composite x in the average case. The Miller test is deterministic assuming the GRH, and effectively deterministic for all applied purposes (as the machine error bound far exceeds the algorithmic error bound). (There is a discrepancy in number of bases used as Sorenson & Webster's reduced base optimization is used for small integers x > 2^80).

Attempts at implementing faster factorization will likely require an implementation of large integers (at the very least 128-bit arithmetic) independent of mpf as the overhead of mpf appears to be excessive when implementing pollard rho.

Additionally this is my first merge request on gitlab and a project like this so the style may not be matched perfectly and may not integrate with all the implementations.

Merge request reports