Go Back > New To GIMPS? Start Here! > Information & Answers

Thread Tools
Old 2007-07-05, 14:55   #1

2·2,179 Posts
Default 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.
  Reply With Quote
Old 2007-07-05, 15:23   #2
Account Deleted
Mini-Geek's Avatar
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3×1,423 Posts

Is there some reason you can't just use one of the clients at 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.
Mini-Geek is online now   Reply With Quote
Old 2007-07-05, 15:33   #3

13·547 Posts

well, the computer I am working with has a daughter board with FPGA chips on it (namely the HC-36 from starbridge: 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.
  Reply With Quote
Old 2007-07-05, 23:08   #4
P90 years forever!
Prime95's Avatar
Aug 2002
Yeehaw, FL

2×3×19×67 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.
Prime95 is online now   Reply With Quote
Old 2007-07-09, 00:32   #5
Tribal Bullet
jasonp's Avatar
Oct 2004

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

Thread Tools

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

All times are UTC. The time now is 19:17.

Wed Oct 27 19:17:23 UTC 2021 up 96 days, 13:46, 0 users, load averages: 1.35, 1.41, 1.62

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.