20060325, 02:51  #1 
1B46_{16} 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 110000000). 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 
20060325, 03:20  #2  
"Mark"
Apr 2003
Between here and the
29×223 Posts 
Quote:


20060325, 04:35  #3 
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 ? 
20060325, 07:20  #4  
Bamboozled!
"ð’‰ºð’ŒŒð’‡·ð’†·ð’€"
May 2003
Down not across
11,027 Posts 
Quote:
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 

20060327, 03:32  #5 
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.

20060327, 14:32  #6 
Sep 2002
662_{10} 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 
20060327, 17:14  #7  
∂^{2}ω=0
Sep 2002
RepÃºblica de California
2^{2}·3·7·139 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Implementing Factoring Algorithms  Raman  Hobbies  45  20090511 05:11 
Overview of Factoring Algorithms  ThiloHarich  Factoring  0  20070902 20:32 
design factoring algorithms  koders333  Factoring  14  20060125 14:08 
factoring algorithms are patented?  koders333  Factoring  1  20060119 20:04 
A distributedcomputing project to optimize GIMPS FFT? Genetic algorithms  GP2  Software  10  20031209 20:41 