I'm curious of the efects of the network once difficulty gets really high and prime numbers to be found are insanely difficult to compute let alone verify by nodes to be efficient in any meaningful way.
http://bitcoinmagazine.com/primecoin-the-cryptocurrency-whose-mining-is-actually-useful/In order to be a viable cryptocurrency, Primecoin needs a way to finely tune the difficulty of the proof of work; otherwise, new developments in technology or increased popularity may lead to new blocks being created too quickly for the blockchain to be stable or so slowly that transactions take hours to confirm. By themselves, prime chains do not provide enough granularity; a chain eight primes long may be a hundred times harder to find than a chain seven primes long. One option is to reward length, but that would make verification more difficult. The solution that Primecoin settled for is one based on the Fermat test. The Fermat test is a quick way of telling if a number is (very probably) a prime: raise any number (typically 2) to the power of a prime, subtract out the prime as many times as possible and see if you get the original number back. For example:
217 – 17 * 7710 = 2
223 – 23 * 364722 = 2
But:
221 – 21 * 99864 = 8
An alternative, and slightly better, formulation is to raise the number to the power of the prime minus one and see if you get one; this being true clearly implies the number passing the other test, and the other direction holds most of the time (one exception is that 3560 = 375 but 3561 = 3 (561 is not prime), but these become extremely rare as primes get bigger). Primecoin uses the p-1 test in combination with the Euler-Lagrange-Lifchitz test, which uses similar principles, to establish primality. So, the question is, how can one use this test to create granularity? That is, how can one distinguish between a chain 7.2 primes long and a chain 7.5 primes long? The answer is simple: look at the resulting value of the Fermat test of the first value in the chain not to be a prime; the lower it is, the larger the “fractional length”. For example, our chain of 2, 5, 11, 23, 47 has the next value 95, 294 modulo 95 (modulo being the mathematical term for the process of repeated subtraction used above) is 54, so the chain would have a length of 5 + (95 – 54) / 95 ~= 5.43. However, the chain 1531…24481 has the next value 48961 with a relatively low Fermat remainder of 1024, so the length would be 5 + (48961 – 1024) / 48961 ~= 5.97. In order for a prime chain to count as a valid proof of work, it must have a fractional length at least equal to the difficulty; as of the time of this writing, this parameter is floating around 7.1.
Since we do not want proofs of work to be reusable, Primecoin also adds another restriction. For the purposes of Primecoin, the “origin” of a bi-twin chain is defined as the average of the first pair, and for single Cunningham chains the origin is what the average of the first pair would be if the Cunningham chain’s twin also existed; for example, the origins of the two single Cunningham chains given above are 1530 and 3, respectively. The restriction is that the origin of a prime chain must be divisible by the hash of the block that the proof of work is for. Hash functions have the property that the only way to look for a value that has a particular hash is the computationally infeasible strategy of simply trying new values until you get a result that works; thus, the only way to generate valid proofs of work is to look for prime chains targeted to one block of which you already know the hash, and these chains would only ever be useful for that specific block.
Primecoin also adds a number of other innovations on the side:
Smooth difficulty adjustment – unlike Bitcoin, which adjusts its difficulty to exactly match the target rate of 1 block per 10 minutes every 2016 blocks (roughly two weeks), Primecoin adjusts its difficulty slightly every block, nudging it toward the target rate in an exponential decay pattern. For example, if network hash power (or rather, prime generation power) suddenly doubles, the next block would be 0.02% harder than the previous, increasing the amount of work required per block to 186.5% of the original after one week and 198.2% after two weeks, assuming no further mining power increases take place.
Very fast confirmations – unlike Bitcoin, where transactions take an average of ten minutes to confirm (eight minutes in practice since the difficulty must constantly catch up to increasing mining power), Primecoin blocks come at a rate of one per minute. This allows secure transactions to be made much more quickly; six confirmations may take fifty minutes in Bitcoin, but they take only six minutes in Primecoin. The underlying mathematics behind why six confirmations is a fairly safe threshold is independent of block confirmation time, so the Primecoin transaction at six confitmations is no less secure (it can be argued that attackers can make double-spending attempts ten times more frequently, but going up to just seven or eight confirmations more than makes up for this).
Self-adjusting block reward – Bitcoin is known for its controlled currency supply algorithm, which guarantees that only 21 million bitcoins will ever be generated, as well as specifying the rate at which these bitcoins will come out. Primecoin follows a different path. The number of primecoins (XPM) released per block is always equal to 999 divided by the square of the difficulty, a formula which should converge to some maximum if the difficulty increases linearly. Given that Moore’s Law states that computing power increases exponentially, and the effort it takes to find a prime chain is exponential in its length, that is quite likely to hold true.
