mersenneforum.org Distributed Factoring and prime testing algorithms
 Register FAQ Search Today's Posts Mark Forums Read

 2006-03-25, 02:51 #1 bunbun   1B4616 Posts Distributed Factoring and prime testing algorithms Hello, I wrote a distributed prime factoring and prime testing algorithm a few months ago. The algorithm felt like it could have been better. For prime factoring what I did was find the square root of the number and then break that chunk of numbers into equal sized blocks and send them to the clients for processing (I would send a range such as 1-10000000). The client would then test each odd number in the sent range as a factor of the number to be factored. If it went into the number being factored evenly then I would test it for primality. The client would then send the prime factors found back to the server which would tally the results. I dont really like the brute force approach and I would be interested if anyone has ideas on how to make the algorithm faster. Cheers, Bunbun
2006-03-25, 03:20   #2
rogue

"Mark"
Apr 2003
Between here and the

29×223 Posts

Quote:
 Originally Posted by bunbun Hello, I wrote a distributed prime factoring and prime testing algorithm a few months ago. The algorithm felt like it could have been better. For prime factoring what I did was find the square root of the number and then break that chunk of numbers into equal sized blocks and send them to the clients for processing (I would send a range such as 1-10000000). The client would then test each odd number in the sent range as a factor of the number to be factored. If it went into the number being factored evenly then I would test it for primality. The client would then send the prime factors found back to the server which would tally the results. I dont really like the brute force approach and I would be interested if anyone has ideas on how to make the algorithm faster. Cheers, Bunbun
That's the worst way to factor any number. Look into ECM, QS, or NFS.

 2006-03-25, 04:35 #3 dsouza123     Sep 2002 2×331 Posts How did you turn the program into a distributed one ? What programming language, distributed code library ? What OSes does it run on ? Windows ? Linux ? OS X ? JAVA VM ?
2006-03-25, 07:20   #4
xilman
Bamboozled!

"ð’‰ºð’ŒŒð’‡·ð’†·ð’€­"
May 2003
Down not across

11,027 Posts

Quote:
 Originally Posted by rogue That's the worst way to factor any number. Look into ECM, QS, or NFS.
Minor quibble. Trial division is actually the best way to find small factors of large integers. The great majority of integers have a factor which is less than 1000. (Calculating the exact proportion is left as an easy exercise.)

I think you meant to say that it's amongst the worst algorithms for factoring large integers which are known not to have any small factors. It's not even the worst for those integers either. Some algorithms have been designed to be spectacularly bad, as an exercise in humour. For a real algorithm, look up the expected and worst case behaviours of Fermat's method some time.

Paul

 2006-03-27, 03:32 #5 BWetter246   Aug 2005 17 Posts bunbun, you can use a speedup and make more blocks within the block with a divisor of 10 and only test the numbers containing 1,3,7,9.
 2006-03-27, 14:32 #6 dsouza123     Sep 2002 66210 Posts To make it faster: Only divide by prime numbers. Unfortunately determining if a number is prime requires more calculations than the division, so try numbers that might be prime, though many wont be. Anyway this will eliminate 1/3 of the odd numbers you are testing. Only divide by numbers that are +1 or -1 mod 6 because they may be primes. Otherwise known as multiples of 6, +1 or -1. Example 6 -> 7,5 6 mod 6 -> 0 7 is +1, 5 is -1 12 -> 13,11 12 mod 6 -> 0 13 is +1, 11 is -1 If by all odds then 7,9,11,13,15,17 get tested If by +1 or -1 mod 6 then 7,11,13,17 get tested, skiping 9,15. Instead of adding 2 each time, find either the +1 or -1 number. With 7 the example starting +1, do the division, add 4 (now 11) do the division add 2 (now 13) do the division add 4 (now 17) do the division etc +4,+2,+4,+2 instead of +2,+2,+2,+2,+2,+2
2006-03-27, 17:14   #7
ewmayer
2ω=0

Sep 2002
RepÃºblica de California

22·3·7·139 Posts

Quote:
 Originally Posted by bunbun I dont really like the brute force approach and I would be interested if anyone has ideas on how to make the algorithm faster.
Ask Eratosthenes - he's old and sometimes a bit cranky, but usually has something worthwhile to say on such topics.

 Similar Threads Thread Thread Starter Forum Replies Last Post Raman Hobbies 45 2009-05-11 05:11 ThiloHarich Factoring 0 2007-09-02 20:32 koders333 Factoring 14 2006-01-25 14:08 koders333 Factoring 1 2006-01-19 20:04 GP2 Software 10 2003-12-09 20:41

All times are UTC. The time now is 20:33.

Fri Dec 3 20:33:12 UTC 2021 up 133 days, 15:02, 0 users, load averages: 1.03, 1.18, 1.15