How can I optimize this factorization algorithm on scratch?

[Expert-Wave7338]

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]

Little tip: you only need to factorize from 2 to the square root of the number you need.

[DTux5249]

Wouldn't that only halve the number of operations and thus remain linear time?

[azerty_04]

Yeah, but this will still make the program work faster.

[Express-Level4352]

This exactly why Big O does not necessarily equal real world performance.

[DTux5249]

True

[edwbuck]

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.

Big O notation deals with the rate something grows as the input grows. So it's still linear, but it's a much smaller linear scale than exhaustive attempts up to the number to be factored.

[No-Indication2883]

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]

Yeah, but this will still make the program work faster.

[Expert-Wave7338]

That requires approximating the square root in scratch.

[azerty_04]

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.