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

[rogue]

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.

[dsouza123]

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 ?

[xilman]

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

[BWetter246]

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.

[dsouza123]

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

[ewmayer]

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.