Integer factorization, the fast way?

Nice Coder · 2004-11-04T13:37:28

Ok, i've been building a small integer factorizer. It is currenly very slow. It takes 2.8 seconds to factorize 102,812,541,257 into 53 * 6,199 * 312,931. It is currently using a few things, First, it checks the common divisors (2,3,5,7 and 11). if it is divisible by those, then it has the factors almost instantly. Then it sqrt's the number. if it is < 200 then it does a trial division search (all numbers < 200, takes < 1 second) And finally, if it is > 200, then it uses a modified sieve of Eratosthenes. Basically, it checks n. if n isn't a factor, then 2n, 3n, 4n, 5n, on. will not be a factor, so you can rule them off your list. It is quite slow for big numbers, but spends most of its time removing all the common factors (2, 3, 5,7 and 11) and i don't know how to get rid of them beforehand. My question is: What is a method, which is faster then my sieve, and which is not too hard (without explanation, some things i just don't understand yet...), to understand or code. From, Nice coder

Math and Physics Programming

Started by Nice Coder October 29, 2004 02:35 AM

19 comments, last by jperalta 19 years, 5 months ago

jperalta

356

November 04, 2004 01:37 PM

Basicaly, as far as I can tell from all sources that use this method you pick your curve in a rather arbitrary fashion. That is you pick your point P = (x,y) which fixes and x and y and pick an a and solve the equation y^2 = x^3 + ax + b for b.

Integer factorization, the fast way?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Integer factorization, the fast way?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines