New currency Primecoin searches for prime numbers as proof of work

A new digital currency has been announced, which uses prime numbers as its proof of work. Primecoin is still in beta, but its goal is to provide a proof of concept that a digital currency can produce something useful besides its subjective market value.

One of the criticisms always put against bitcoin is that the cryptographic computation that provides proof of work has no intrinsic value. This is true – the bitcoin market places a subjective value on the currency, just as any other commodity. However, at least physical coins can be melted down and used to make something else.

Long before cryptocurrencies existed there were other distributed computing projects not run for profit but for scientific progress. Those projects are still running; SETI@Home was set up to help process signals from interstellar space in the hope of finding signs of alien intelligence. Meanwhile, Folding@home sought help from the public in simulating how proteins behave in order to aid research into Alzheimer's, Huntington's, Parkinson's and many types of cancer.

These projects have not gained the same notoriety as digital currencies because, to be blunt, most people are motivated by money rather than the common good. However, there have been repeated suggestions on the Bitcoin forum that digital currencies should contribute computing power to a worthwhile cause. The problem is that the SHA256 algorithms that bitcoin uses are far faster to verify than the computations done with those scientific projects. Speed of verification is crucial to protecting against double spending.

That is where Primecoin comes in. Prime numbers are a valuable mathematical resource. Prime numbers are numbers that are only divisible by one or themselves, and no other numbers. This is useful in encrypting internet traffic (e.g. SSL or TLS), because while it's easy to multiply two prime numbers together, to create a "public key", it's difficult to run the calculation in reverse. I.e. It's a difficult computation to take an exceptionally large number and find its "prime factors".

Furthermore, while prime numbers have fascinated mathematicians for centuries nobody yet understands how to calculate prime numbers. Instead, we use super computers to find prime numbers by trial and error. They take ever increasingly large numbers and attempt to find their integer (whole number) factors. If there is none (besides one and itself), then it's a prime number.

That has made prime numbers a highly valuable mathematical resource because of the way they can be used as encryption keys. So much so, that the Electronic Frontier Foundation offers cash prizes to groups that find large prime numbers. For example, in 2009 it paid $100,000 for the discovery of a 12-million digit prime.

The group behind the peer-to-peer cryptocurrency, PPCoin, think it has the answer with Primecoin. There is a detailed paper [PDF] on the website, explaining how the currency works. It shows that the proof of work in finding prime numbers is computationally efficient. However, this is on the proviso that the prime numbers are not "record-breakingly large".

This is where there is a question mark over the value as it isn't made clear whether there are still prime numbers, other than those that break the records, to be discovered.