Quote from: usahero on August 22, 2013, 11:51:13 AM

Could you explain what primecoin algorithm actually does?

Why doesn't primecoin for example just read some known prime numbers from some database, compare them if there is any Cunningham chain candidate and ... offer result?

Does this algorithm have to find all these prime numbers by brute force first, and then find the chains..?

If you could describe this in layman's terms, I'd be very happy.

The algorithm is kind of complicated to explain in lay terms. First, I'd like to point out that there is no database of primes of this size that would be even kind of useful. The numbers used are on the order of 10¹⁰⁰. In that range about 1 in 180 numbers is prime. That means that in order to store all of the prime numbers between 10¹⁰⁰ and 10¹⁰¹ you would more memory than there could ever exist in the universe--more bits than there are atoms. No such database can ever exist within the current understanding of physics.

So, the algorithm is somewhat of a brute force. It has some elegance to it, though. The chains have a very specific form, which gives a lot of opportunity for speedups. For example, if your chain starts at N then 2N-1 is in the chain (for one of the chain types). It would be inefficient to check the primality of 2N-1 if N is already shown to be composite--the chain is already proven to be invalid. Many optimizations take this general form.

The algorithm itself is broken into two main parts: sieving and primality tests. Sieving is a really fast way to show that lots of numbers are composite, but it is impractical to show that any number is prime by a sieve alone. The most famous (and oldest) sieve is the Sieve of Eratosthenes, which has a lovely Gif and explanation on its wikipedia page. Sieves work by eliminating numbers that have small factors; it is easy and computationally cheap to carry out a single division to determine if a big number, N, is divisible by a small number, k, and about 1 in k divisions will show that N is divisible by k and that N is therefore composite. This can be taken a step farther by noting that if N is divisible by k then N + a*k is also divisible by k, allowing many candidates to be eliminated by a single division and a few multiplications. Thus, the mining algorithm first generates a set of candidate numbers based on a hash function and the data in the block, then runs that set of numbers through a sieve.

The next step is to actually test the remaining numbers after the sieve takes out most of them. This is accomplished by the Fermat (Probable) Primality Test, which holds that if a^P-1 ≡ 1 (mod P) for all a and prime P. That is to say, you can take any number (a) and raise it to the power of your candidate (P) minus one, then divide the result by the candidate; if you get anything other than 1 as the remainder of that division then P is composite, otherwise P is probably prime. For PrimeCoin a is always taken to be 2, and "probable" is taken to be good enough--the odds that 2 is a "Fermat Liar" for P are much less than the odds that P is prime.

Thus, the general flow is (Protocol to build a block and find the appropriate hash value to start from) -> (form a set of numbers that could be valid as part of prime chains for this block) -> (run the numbers through a sieve) -> (Eliminate numbers that passed the sieve but aren't parts of chains of length 9 or longer (current integer difficulty)) -> (for each chain of possibly prime numbers remaining, execute a Fermat Primality test until you either find a complete chain or find a composite number that proves that no chain long enough will be found there).