How can I optimize this factorization algorithm on scratch?
Posted by Expert-Wave7338@reddit | learnprogramming | View on Reddit | 11 comments
I recently wrote a program which uses the a simple factorization approach ((x-1)| n , (x+1)|n when x\^2 == 1 mod n , of course excluding trivial factors); given that this runs \~ O(n), is there an effective way to implement a sieve which does not rely on Gaussian elimination?
azerty_04@reddit
Little tip: you only need to factorize from 2 to the square root of the number you need.
DTux5249@reddit
Wouldn't that only halve the number of operations and thus remain linear time?
edwbuck@reddit
It does a bit better than halve the numbers, but the time will still be linear.
after all.... one only needs to check up to 8 to cover every factor that might go into 63, so it's pretty apparent that it's more than 1/2 the numbers that are eliminated.
Express-Level4352@reddit
This exactly why Big O does not necessarily equal real world performance.
DTux5249@reddit
True
azerty_04@reddit
Yeah, but this will still make the program work faster.
Expert-Wave7338@reddit (OP)
That requires approximating the square root in scratch.
azerty_04@reddit
There's an operator which does various operations on number available, and while the default one is the absolute value, you can use it to get the square root if you select the good operation.
No-Indication2883@reddit
wait isnt that for trial division? your algorithm looks like its trying to find squares that are congruent to 1 mod n which is more like pollards rho or quadratic sieve territory
for actual sieving without gaussian elimination maybe look at trial division with wheel factorization but thats still gonna be slower than what you have
azerty_04@reddit
Yeah, but this will still make the program work faster.
azerty_04@reddit
Little tip: you only need to factorize from 2 to the square root of the number you need.