FYI -- http://riecoin.org/faq.html Finding a prime number p takes O( log(p) ^ 4 ) work, while verifying if it's prime requires O( log(p) ^ 3 ) using the Rabin-Miller test. That's not much difference, so finding prime numbers is not practical for a PoW. One possible solution for this is looking for prime number constellations (like twin prime numbers, or triplets, etc), that is n "consecutive" prime numbers. Consecutive in this case means that they are grouped as closely as possible minimizing the distance between the first and the last one. This takes O( log(p) ^ (n + 3) ), while verification still takes the cube of the log. This allows us to make the generation arbitrarily more difficult than the verification. Difficulty can be adjusted by changing the length of the prime numbers. Riecoin currently uses constellations of size 6 (also known as prime sextuplets) which have the form p, p+4, p+6, p+10, p+12, p+16. So each block represents six prime numbers. ... How is Riecoin different from Primecoin? Primecoin uses the Fermat primality test, which has some flaws. Carmichael numbers are not prime and still pass Fermat's test for all bases, however those are relatively rare. Secondly, in general, if Fermat's test says a number is prime, it has at least a 50% probability of being prime. Primecoin uses only one Fermat test with base 2. While base 2 may provide more confidence than the general bound of 50%, still many composites will pass as primes. What's worst, is that Euler-Lagrange-Lifchitz test used for the other primes in the chain assumes the previous number in the chain is prime. So if the chain starts with a number that is not prime, then the Euler-Lagrange-Lifchitz test is not guaranteed to work, and all numbers in the chain may be composite. Short version: Primecoin numbers are not guarranteed to be prime, they may be Fermat pseudoprimes to the base 2. There is an infinite list of Fermat pseudoprimes to the base 2 (oeis.org/A001567). Riecoin uses enough Rabin-Miller tests with random bases, so the probability of a number that is not prime being accepted by the majority of the Riecoin network is negligible.