Prime number testing on FPGA

[Dennis Yurichev]

Hi.

There are a such thing as Great Internet Mersenne Prime Search
(GIMPS):

"The Great Internet Mersenne Prime Search (GIMPS) is a collaborative
project of volunteers who use freely available computer software to
search for Mersenne prime numbers."

"To perform its testing, the project relies primarily on Édouard Lucas
and Derrick Henry Lehmer's primality test,[3] an algorithm that is
both specialized to testing Mersenne primes and particularly efficient
on binary computer architectures."

http://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_Search

There are another number primality tests exists, so the question is,
is there can be such primality test which is suitable for FPGA in such
way, when it will work much more effectively than Édouard Lucas and
Derrick Henry Lehmer's primality test running on generic computer?

P.S.:
https://www.eff.org/awards/coop

 

[backhus]

On 20 Jan., 08:10, Dennis Yurichev <dennis.yuric...@gmail.com> wrote:

Hi.

There are a such thing as Great Internet Mersenne Prime Search
(GIMPS):

"The Great Internet Mersenne Prime Search (GIMPS) is a collaborative
project of volunteers who use freely available computer software to
search for Mersenne prime numbers."

"To perform its testing, the project relies primarily on Édouard Lucas
and Derrick Henry Lehmer's primality test,[3] an algorithm that is
both specialized to testing Mersenne primes and particularly efficient
on binary computer architectures."

http://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_Search

There are another number primality tests exists, so the question is,
is there can be such primality test which is suitable for FPGA in such
way, when it will work much more effectively than Édouard Lucas and
Derrick Henry Lehmer's primality test running on generic computer?

P.S.:https://www.eff.org/awards/coop

Hi,
some thoughts about the problem.
Actual numbers under test have more than 12 million decimal digits.
It would be interesting to know if the algorithm can work on these
digits in a streaming way, or if it needs random access.
In the second case the performance gain may be neglectible.

Another interesting point would be, if such an algorithm could perform
better when working on a true binary representation of the number
under test.
This would probably increase the number of binary digits, but
hopefully increase the performance of the algorithm.
Also, the steps of generating/converting the number could be separated
from the algorithm itself.

If the algorithm can work in parallel (that is, multiple instances can
work on the same number under test) it would further benefit from a
hardware implementation.

So, the first useful thing to do would be to take a close look at the
algorithms for testing the prime nature of a given number.

Have a nice synthesis
Eilert

 

[Thomas Womack]

In article <b8e5e93e-22af-47d3-b397-11db7cafa26e@s5g2000yqm.googlegroups.com>,
Dennis Yurichev <dennis.yurichev@gmail.com> wrote:

There are another number primality tests exists, so the question is,
is there can be such primality test which is suitable for FPGA in such
way, when it will work much more effectively than =C9douard Lucas and
Derrick Henry Lehmer's primality test running on generic computer?

The LL test already uses about as few multiplications as you can
reasonably hope for.

The inner loop of the primality test is a large FFT, which is the
classic non-streaming task, done in double-precision floating point,
which is another thing at which generic computers are significantly
better than FPGAs.

People have occasionally built a large FFT multiply (often a
number-theoretic transform, since arithmetic mod 2^64-2^32+1 is rather
easier to implement than double-precision FP) in FPGAs; they have to
be big FPGAs, on a board with lots of attached DDR3 or QDR SRAM
memory, and end up about as fast as a desktop PC at ten to fifty times
the cost.

Basically, Sandy Bridge or Phenom chips are an enormously cheaper
source of multipliers and memory bandwidth than Xilinx.

Tom

 

[backhus]

On 20 Jan., 12:45, Thomas Womack <twom...@chiark.greenend.org.uk>
wrote:

In article <b8e5e93e-22af-47d3-b397-11db7cafa...@s5g2000yqm.googlegroups.com>,
Dennis Yurichev  <dennis.yuric...@gmail.com> wrote:

There are another number primality tests exists, so the question is,
is there can be such primality test which is suitable for FPGA in such
way, when it will work much more effectively than =C9douard Lucas and
Derrick Henry Lehmer's primality test running on generic computer?

The LL test already uses about as few multiplications as you can
reasonably hope for.

The inner loop of the primality test is a large FFT, which is the
classic non-streaming task, done in double-precision floating point,
which is another thing at which generic computers are significantly
better than FPGAs.

People have occasionally built a large FFT multiply (often a
number-theoretic transform, since arithmetic mod 2^64-2^32+1 is rather
easier to implement than double-precision FP) in FPGAs; they have to
be big FPGAs, on a board with lots of attached DDR3 or QDR SRAM
memory, and end up about as fast as a desktop PC at ten to fifty times
the cost.  

Basically, Sandy Bridge or Phenom chips are an enormously cheaper
source of multipliers and memory bandwidth than Xilinx.

Tom

Hi Tom,
is there a reason why the algorithm uses floating point for the FFT
calculation?
Since the problem is the analysis of an integer number, this makes me
wonder.
Or is it just to make use of the FP-Coprocessor that is available in
the CPU anyway, and has no mathematical reason?

regards
Eilert

 

[Kolja Sulimma]

On 20 Jan., 08:10, Dennis Yurichev <dennis.yuric...@gmail.com> wrote:

There are another number primality tests exists, so the question is,
is there can be such primality test which is suitable for FPGA in such
way, when it will work much more effectively than Édouard Lucas and
Derrick Henry Lehmer's primality test running on generic computer?

I can't compare the performance, but the reconfigurable computing
people
from imperial collage have been working on that:
http://wwwhomes.doc.ic.ac.uk/~rcheung/papers/fpt04.pdf

Kolja

 

[backhus]

On 24 Jan., 09:31, Kolja Sulimma <ksuli...@googlemail.com> wrote:

On 20 Jan., 08:10, Dennis Yurichev <dennis.yuric...@gmail.com> wrote:

There are another number primality tests exists, so the question is,
is there can be such primality test which is suitable for FPGA in such
way, when it will work much more effectively than Édouard Lucas and
Derrick Henry Lehmer's primality test running on generic computer?

I can't compare the performance, but the reconfigurable computing
people
from imperial collage have been working on that:http://wwwhomes.doc.ic.ac..uk/~rcheung/papers/fpt04.pdf

Kolja

Hi,
interesting paper.
Only drawback I see at the moment is the size of the prime numbers.
But if the algorithm can work with a given number of Processing
Elements on any number under test,
it would just be necessary to replace the BRAM storage by some
external memory interface for DDR-Ram or (if read only) FLASH memory.
(More elegant would be some network solution of course.)

Have a nice synthesis
Eilert