Being physicist and unfortunately not so into math i watched this today (and the 20min more footage) about prime gaps and kinda liked it:
https://www.youtube.com/watch?v=vkMXdShDdtYSome questions:
Is there also world records for primes that have a gap of 2 ? Can gapcoin find them or because of sieves it may pass primes (I am not sure i understand how sieves work)?
I am kinda excited with primes lately. What should i read to understand how gapcoin finds gaps? Does it need really advanced mathematics?
The average length of a prime gap with the starting prime
p, is
log(p), which means that the average prime gap size increases with larger primes.
Instead of the pure length, Gapcoin uses the “merit” of a prime gap, which is the ratio of the gap’s size to the average gap size. Let
p be the prime starting a prime gap, then
m = gapsize/log(p) will be the merit of this prime gap.
Also a pseudo-random number is calculated from
p to provide finer difficulty adjustment.
Let
rand(p) be a pseudo-random function with
0 < rand(p) < 1 Then, for a prime gap starting at prime
p with size
s, the difficulty will be
s/log(p) + 2/log(p) ∗ rand(p), where
2/log(p) is the average distance between a gap of size
s and
s + 2 (the next greater gap) in the proximity of
p.
When it actually comes to mining, there are two additional fields added to the block header, named “shift” and “adder”.
We will calculate the prime
p as
sha256(block header) ∗ 2^shift + adder. As an additional criterion the adder has to be smaller than
2^shift to avoid that the PoW could be reused.
Mining:For mining, PoWCore uses a basic prime sieve with some slightly improvements:
The sieving steps:Calculate the first
n primes. In the actual sieve we skip all even numbers, because we want to only sieve the odd multiplies of each prime. So, we create an additional set of primes and multiply each with two. Make sure the
start_index of the sieve is divisible by two.
Now calculate for each prime the first odd number in the sieve, which is divisible by that prime (called
pindex).
For each prime
p: mark the
pindex as composite, add
2 ∗ p to
pindex and mark it as composite, redo till we reach the end of the sieve.
For each remaining prime candidate, check primality with the Fermat-pseudo-prime-test as it is faster than the Miller-Rabin-test (Fermat is not as accurate as the Miller-Rabin and maybe some valid sieve results will not be accepted, but this should be very rare)Now scan the remaining (pseudo) primes for a big prime gap.
Additional notes:start_index can be
hash ∗ 2^shift + [0, 2^shift)max sieve size depends on
start_index, and is limited by
(hash + 2^shift) - start_index.
shift can theoretically be in range
[14, 2^16], but nodes can choose to only accept shifts till a given amount (e.g. 512 for the main nodes)
dcct’s improvementsWe do not check every remaining prime candidate with the fermat test. Instead we look how large the gap has to be to fit the required difficulty (max_length). Then we determine the first prime in the sieve (called
pstart). Now we scan the prime candidates in the range
(pstart, pstart + max_length). We start at the position
(pstart + max_length) and scan every prime candidate in reverse order till we reach
pstart.
If we find a prime within the range
(pstart, pstart + max_length) we can skip all other prime candidates within that range and set
pstart to that prime. We redo the above process till we reach the end of the sieve.
