Topic: [XPM] [Bounty claimed] A couple of primecoin implementation questions (Read 1660 times)

Received. Thank YOU!

Thanks for the great explanation, definitely cleared up the parts I didn't understand.

I've sent your 0.2 BTC, thanks again.

I don't know how much detail do you require in the explanation... let's try this:

the chain origin is at hash * something
the more primes the origin has in it's factorization, the higher the probability of it having a long chain
that's why it looks for primorials: we want hash*something to be a multiple of the higher primorial possible, but we also want it to be a small number in order to make math faster
the "something" part is divided into a fixed part and a variable part. So the chain origin is hash * fixed * varMultiplier, where fixed*varMultiplier is the proof of work, and once the fixed part is selected, then the sieve to look for "varMultiplier" is generated
if hash is already multiple of some primorial, that fixed part could be smaller and the origin is still guarranteed to be part of a primorial. The varMultiplier part will be searched for starting from 1 and up to whatever the sieveSize.
The origin needs to be multiple of the primorial up to 7 to meet the minimum diff (this can be mathematically proven) otherwise it cannot generate the prime chain. That primorial is stored in bnHashFactor.
So we change the nonce until the hash is a multiple of bnHashFactor.
the origin (or the first prime of the chain, which is origin +/- 1) needs to be larger than bnPrimeMin, I guess this is to guarrantee that a minimum effort is required.
Now, we want a fixed part so origin is multiple of a primorial, we want it to be small because small numbers mean less RAM and faster math, but we want it to be large so that we meet the minimum value requirement (that minimum value is bnPrimeMin). Also, since the hash is already a multiple of bnHashFactor, we don't need to include that in the fixed part. So the fixed part is not actually a primorial, but a priomrial divided by bnHashFactor. Let's write this as
fixed = somePrimorial / bnHashFactor
What is the minimum possible value for that somePrimorial?
hash * somePrimorial / bnHashFactor > bnPrimeMin
so we get
somePrimorial  > bnPrimeMin * bnPrimeMin / hash
so it's minimum possible value is
somePrimorialMin  = bnPrimeMin * bnPrimeMin / hash + 1
and that's your first line of code

Then when we start with varMultiplier = 1, then origin is "origin = hash * fixed". If hash is multiple of primorial(7) then we don't need primorial(7) to be part of fixed. So instead of fixed being a primorial, it can be a somePrimorial / bnHashFactor, so it has a lower value.

This is done with the second line:
CBigNum bnFixedMultiplier = (bnPrimorial > bnHashFactor)? (bnPrimorial / bnHashFactor) : 1;

if our selected primorial "bnPrimorial"  is larger than bnHashFactor, (since both bnPrimorial and bnHashFactor are primorials, it means bnPrimorial is a multiple of bnHashFactor) we can remove the factors of bnHashFactor from bnPrimorial and don't worry because hash * bnFixedMultiplier will still be a multiple of the desired primorial.
Now the else part: If bnPrimorial  <= bnHashFactor, our selected primorial is less that the primorial factor needed to find a chain, which is already a divisor of hash, so our fixed part can be 1.

In practice, I never saw bnFixedMultiplier to be less than 11, so bnPrimorial was 2*3*5*7*11 and bnHashFactor was the constant 2*3*5*7. At least in the few cases I debugged I never saw it to be 1.

mmmm this post looks disorganized, I hope this is not a mess and you can understand something of it, sorry but it's late here

I believe it's sad that Sunny didn't explain any of this in the paper or the comments in the cod,e and we have to resort to deciphering what he's trying to do...
let me know if something is not clear

cheers

Thanks for the unhelpful posts.

Still waiting on a valid explanation or some evidence that the logic really is arbitrary.

yes

I've been trying to wrap my head around the maths / implementation of primecoin and I think I understand most of it now apart from a few details which I hope someone can fill me in on:

What's the reasoning/logic behind the minimum multiplier calculation? (main.cpp:4642)

What's the reasoning behind the fixed multiplier selection? (main.cpp:4649)

0.2 BTC bounty for a good explanation of the two!

Thanks in advance.