Prime number in verilog

To what end? Are you looking to synthesize something, or do you need prime numbers for a test bench?

If you want to end up with hardware that coughs up prime numbers -- I think you'll either need to settle for a look-up table with stored numbers, or some some sort of state machine that does a sieve or whatever it is that people do these days that's more efficient than a sieve.

Assuming you want this to be synthesisable, may I suggest the Sieve of Eratosthenes

In common with other sieve algorithms, it requires that you know the upper limit in advance and have enough memory to hold a flag for each number up to that upper limit. As such, it is not suited to a design that has to produce a continuous stream of prime numbers without bound.

Allan

Well, a flag for each number up to the square root of the upper limit, if you really want to be stingy.

Is there _any_ prime-finding algorithm that doesn't require you to store more and more history as you go, or to repeat calculations that you wouldn't otherwise have to repeat?

Yes, they're called "incremental sieves". I've never tried one.

The crypto folk (well, those still using RSA) generate their big primes by generating random numbers then testing them. Generating big random numbers is quick, and the primality test is pretty quick too (particularly if one can trade off accuracy and let a pseudoprime through occasionally).

Regards, Allan

Unlike the for loop in C or Java, the verilog for loop increases the amount of hardware used to do the computation. Very often, that is not what you want.

(snip)

I would guess not, but you can make it interesting. Find a compromise between storing and calculating.

My first prime number program was on an HP 9810A calculator. It stored the values computed so far in addressable registers, and stopped when it ran out of them. (I didn't yet know about the square root rule.)

Not so much later, I started learning Fortran, and the sample program in the OS/360 Fortran manual prints a table of primes. That one first prints out 2 and 3, then loops for odd numbers, testing each by dividing by values up to sqrt(float(n)). The program was much smaller and simpler than I had done on the 9810A.

Note that the Fortran program takes one optimization, after printing 2, not even trying other even numbers. You could take that one better, as only two of every six aren't divisible by either 2 or 3. You could write a loop incrementing by six, with two trial loops inside. Note that this trades of program size and complexity for time.

You could also extend it using 5, 7, and 11 as previously known primes, and reduce the computation accordingly.

In the verilog case, you likely don't want hardware with size proportional to, or maybe even proporional to the square of, the largest prime value that you want to compute. Most often, that means a state machine.

You want to loop in time, not space (logic), generating potential primes and testing them. Seems to me that either the sieve or looping in a state machine through potential primes, and another loop in time testing them isn't so complicated to generate, though not the easiest. You might do it wit a state machine generating tool.

It seems likely that the hardware has to be designed based on the largest possibly value, as enough bits will have to be supplied to hold that value. But bits are pretty cheap these days.

You could loop at 50MHz, trying primes, maybe with an iterative divider. Then stop for 1s when you find one, with its value on the built-in (to your FPGA board) display.

-- glen

That's indeed how the crypto folks do it. The Miller-Rabin test uses little memory, is fast and not to hard to implement.

As you said the algorithm will indeed let a pseudoprime through, but you have control over how often that happens on average.

I just looked up the numbers in the book Cryptographic Engineering by Bruce Schneider et. al.

He states that just 64 random Miller-Rabin tests are enough to lower the chances of a pseudoprime down to 2^-128 percent. He also states that the chance of getting killed by a meteor while reading this sentence is far larger than that. :-)

/Nils