This kinds of discussions makes the value of Riecoin, it's lot more interesting than mixing and mashing hash algorithms!

The value of the coin eventually matter in that if it were high enough, it would incentivize some dedicated prime computing silicon, which eventually could have other uses. I guess NSA & similar have such silicon, but it's definitely beyond the budget of us mere mortals.


I am surely moving the goalposts here, but would it be possible to amortize the verification over many blocks?
Sort of a distributed partial Rabin-Miller (is that practical and can it be made provable?)

This would obviously have DOS issues, if a superblock is found incorrect after many blocks, you can't go back in time to try another, so that superblock would be "lost"...
It could be alleviated if for the superblock, up to X candidate prime clusters could be "registered" as meta-data, apart from the difficulty requirement, those would only have to pass low-probability primality tests, cheap enough in terms of computing but hard enough to filter spam (possible?). The registration could be allowed for a few blocks after the super-block (to minimize the network stall).
At this point the reward for the super-block would be zero, with tx vout with an amount of zero per candidate (just to keep track of their addresses).

Over the next N blocks, partial rabin-miller tests would be performed on those candidates alongside the usual PoW.
After the N blocks, candidates that failed primality would be rejected, and the superblock reward would then either be split among those that passed the test or attributed randomly.

It all hinges on the provability of a partial Rabin-Miller test, which may be a pipe dream