But you could turn it around into finding factors of a very large number to check whether it is prime.
Couldn't you just lie about this? Imagine "15" is such a huge number: I just claim that the only factors I could find for 15 are 1 and 15, thus making it prime. This still requires you to try to find other factors to debunk my claim...
A large number is proposed and everybody keeps dividing it by various primes until somebody gets lucky and finds a factor. It takes a lot of computational power to keep dividing but when you have found a factor anybody can quickly check whether it actually is a factor.
Then some formula using the previous number and the factor that has just been found is used to create the next big number to check.
Of course there is the problem that if the number is actually prime we never find a factor. This isn't an answer just an idea of what sort of thing the pow problem might be.
There is a lot of processing power out there working on hashing. What if a researcher wants to use this sort of distributed processing power for a useful research project? Everybody donates their processing power to the project and they are then entered into a lottery with the chances of winning related to how much processing power they donate. This lottery replaces the lottery of whether or not you come up with the right nonce.
how about this:
the currency is 'pre-mined' EXCEPT if you find a new prime number. The miners only get transaction fees.
here is the twist:
so if you think you discovered a prime number, you create a special block which grants you eg. 80,000 USD worth of primecoin.
if someone discovers a factor to that prime, then you lose your block, your award, and anyone holding those coins also loses their balances(this would of course require extensive reordering of the BC- but it is effectively possible). This kind of tracing to a genesis transaction is done and proven with color coins. What does this create? it means that pseudoprimes would be a kind of currency, just not a very sound one. If you chose to accept value from a dubious pseudoprime, you risk losing your money. So this puts the onus on the person claiming the number, they might want to publish a reason why they think this number is prime.
it would have an interesting effect, for instance the pseudoprimes that are located along features in the Ulam Spiral would have higher market rates than those that didn't. It would create an entire speculative market for prime computation. Kurt Godel would be ecstatic.
In other words: you believe integer X is prime. You read a whitepaper that suggested so. So you buy some coins that are FOUNDED in that prime. If it is later proven to be prime, the market value goes up. If I'm a Integer Factorization Miner, and I think I can find a factor in it- I take out a short position- mine the integer, find a factor, publish, and the price plummets and I go buy a steak dinner.
Has no one ever proposed this idea before? Primes are really the only true COMMODITY in mathematics. They are in limited supply but also unbounded. They are useful. They are hard to find. This lives up more to the promise of bitcoin than bitcoin itself.