mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2006-03-25, 02:51   #1
bunbun
 

1B4616 Posts
Question 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
  Reply With Quote
Old 2006-03-25, 03:20   #2
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

29×223 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2006-03-25, 04:35   #3
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

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 ?
dsouza123 is offline   Reply With Quote
Old 2006-03-25, 07:20   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

11,027 Posts
Default

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
xilman is offline   Reply With Quote
Old 2006-03-27, 03:32   #5
BWetter246
 
Aug 2005

17 Posts
Default

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.
BWetter246 is offline   Reply With Quote
Old 2006-03-27, 14:32   #6
dsouza123
 
dsouza123's Avatar
 
Sep 2002

66210 Posts
Default

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
dsouza123 is offline   Reply With Quote
Old 2006-03-27, 17:14   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

22·3·7·139 Posts
Default

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.
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Implementing Factoring Algorithms Raman Hobbies 45 2009-05-11 05:11
Overview of Factoring Algorithms ThiloHarich Factoring 0 2007-09-02 20:32
design factoring algorithms koders333 Factoring 14 2006-01-25 14:08
factoring algorithms are patented? koders333 Factoring 1 2006-01-19 20:04
A distributed-computing project to optimize GIMPS FFT? Genetic algorithms 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.