Mersenne Primality Test in Hardware

2007-07-05, 14:55

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.

Mini-Geek · 2007-07-05, 15:23

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.

2007-07-05, 15:33

well, the computer I am working with has a daughter board with FPGA chips on it (namely the HC-36 from starbridge: http://www.starbridgesystems.com/hypercomputing/HC-36/). 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.

Prime95 · 2007-07-05, 23:08

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 pipeline-able, then would it be possible to use the standard recursive turn-one-big-multiply-into-3-half-size-multiplies until you got down to say 10,000 bit chunks, then feed these 10,000 bit chunks to the pipelined FPGA multiply algorithm.

jasonp · 2007-07-09, 00:32

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 general-purpose hardware, but not by 1000x like FPGAs can sometimes do. You can do 100x as many operation in parallel, but general purpose hardware has 20-30x your clock rate.

2007-07-05, 14:55	#1
Unregistered 11243₈ 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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Fastest software for Mersenne primality test?	JonathanM	Information & Answers	25	2020-06-16 02:47
Conjectured Primality Test for Specific Class of Mersenne Numbers	primus	Miscellaneous Math	1	2014-10-12 09:25
New Mersenne primality test	Prime95	Miscellaneous Math	19	2014-08-23 04:18
A (new) old, (faster) slower mersenne-(primality) PRP test	boldi	Miscellaneous Math	74	2014-04-17 07:16
LLT Cycles for Mersenne primality test: a draft	T.Rex	Math	1	2010-01-03 11:34

2007-07-05, 15:23	#2
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 4278₁₀ 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.

2007-07-05, 15:33	#3
Unregistered 2²×5²×71 Posts	well, the computer I am working with has a daughter board with FPGA chips on it (namely the HC-36 from starbridge: http://www.starbridgesystems.com/hypercomputing/HC-36/). 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.

2007-07-05, 23:08	#4
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 2²·3·659 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 pipeline-able, then would it be possible to use the standard recursive turn-one-big-multiply-into-3-half-size-multiplies until you got down to say 10,000 bit chunks, then feed these 10,000 bit chunks to the pipelined FPGA multiply algorithm.

2007-07-09, 00:32	#5
jasonp Tribal Bullet Oct 2004 6731₈ 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 general-purpose hardware, but not by 1000x like FPGAs can sometimes do. You can do 100x as many operation in parallel, but general purpose hardware has 20-30x your clock rate.