View Single Post
Old 2003-05-22, 02:04   #5
Maybeso's Avatar
Aug 2002
Portland, OR USA

2·137 Posts
Default Re: About trial factoring

Originally Posted by cheesehead
Among other shortcuts, Prime95 trial factoring considers only the 16 congruence classes mod 120 (+-1, +-7, +-17, +-23, +-31, +-41, +-47, +-49) that might contain prime Mersenne factors. Thus it skips fourteen of the mod 120 congruence classes (+-9, +-15, +-25, +-33, +-39, +-55, and +-57) which satisfy +-1 mod 8 but are never prime.
For a long time now, I've wanted to adapt the Atkins algorithm to generate primes in those 16 congruence classes using a single binary quadratic form. One obstacle for me was c is not my first language, so dealing with make files, etc. is a pain. Plus, to do it right, I wanted to incorporate one of the large number libraries.

I finally reduced my goal to writing a simple one that works, and wrote it as an html form using javascript. Now, someone can easily convert my source to c, mesh it with one of the libraries, and we'll be in business.

After reading the info on Trial Factoring, I suspect that this won't be usefull with the methods Prime95 uses to store and sieve candidate factors - Since each candidate is separated by at least 2*p.

But if anyone is interested, I can email it; or post it here as an attachment; or upload it to someones server and post a link.

Maybeso is offline   Reply With Quote