20070705, 14:55  #1 
15337_{8} Posts 
Mersenne Primality Test in Hardware
I was wondering If anyone had any HDL code to test prime numbers possibly using a FFT or even with a FFT. I have access to a very very powerful computer. I already tried implementing the algorithm in hardware using a visual language, but the software is not that great and it became very difficult, especially when trying to figure out how to represent 10 million digit numbers.

20070705, 15:23  #2 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
10257_{8} Posts 
Is there some reason you can't just use one of the clients at http://www.mersenne.org/freesoft.htm? They're available for many OSes and some can run multiple threads to use multiple CPUs or cores of the powerful computer on one number, although it reduces efficiency by some degree. Also, they probably use a very efficient way of testing primality of Mersenne numbers.

20070705, 15:33  #3 
6,269 Posts 
well, the computer I am working with has a daughter board with FPGA chips on it (namely the HC36 from starbridge: http://www.starbridgesystems.com/hypercomputing/HC36/). In order to run the software on those FPGAs I need to write code for them. If I just run the free software it will just run off of the processors that actually run the machine.

20070705, 23:08  #4 
P90 years forever!
Aug 2002
Yeehaw, FL
1E5F_{16} Posts 
I haven't given it serious thought, but would the following idea work?
In Knuth Vol 2, I think Knuth states there is a hardware multiply algorithm that operates in linear time. If it is pipelineable, then would it be possible to use the standard recursive turnonebigmultiplyinto3halfsizemultiplies until you got down to say 10,000 bit chunks, then feed these 10,000 bit chunks to the pipelined FPGA multiply algorithm. 
20070709, 00:32  #5 
Tribal Bullet
Oct 2004
3×1,181 Posts 
In general this is a very hard job. See this thread for suggestions the last time someone wanted to implement the LL test in hardware. My personal opinion is that it's possible to significantly beat Prime95 running on even the fastest generalpurpose hardware, but not by 1000x like FPGAs can sometimes do. You can do 100x as many operation in parallel, but general purpose hardware has 2030x your clock rate.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fastest software for Mersenne primality test?  JonathanM  Information & Answers  25  20200616 02:47 
Conjectured Primality Test for Specific Class of Mersenne Numbers  primus  Miscellaneous Math  1  20141012 09:25 
New Mersenne primality test  Prime95  Miscellaneous Math  19  20140823 04:18 
A (new) old, (faster) slower mersenne(primality) PRP test  boldi  Miscellaneous Math  74  20140417 07:16 
LLT Cycles for Mersenne primality test: a draft  T.Rex  Math  1  20100103 11:34 