Understanding the XPM Algorithmn/Protocol (Attempting to write my own miner)

Hello All,

I hope you can help me with understanding how primecoin works. So far the actual knowledge I’m looking for is not on the wiki, the original white paper, or asked anywhere else, and this is pretty much my last stop before I start digging though the source code and trying to understand what is going on.

In my interest in understanding how primecoin works, I want to write my own miner. This will most likely start with a CPU affair, and be slower than the official, but hopefully it will help me understand how the whole thing works.

So, based on my understanding (and please, correct me if I am wrong), the primecoin algorithm works something like this:

1. You get a range of numbers, say 1-100
2. You then find out which ones in that range are prime numbers
3. Then you see which ones fulfill the requirements to be classed as a Cunningham chain (sequence of primes, that follow 2p+1)
4. The length of the chain is your difficulty (so e.g. if the difficulty is 5, you have to find a Cunningham chain of 5 primes).
5. This chain (once it meets the difficulty) is what is submitted to the network as proof of work.

Is the above correct? If it is, then to discover such a chain, I need two inputs:

1. The range of numbers within which to search for primes
2. The target chain length (difficulty)

However when I connect to the primecoin server, and issue a getwork command, I get this:

bitcoinrpc.data.WorkItem(
hash1=u’00000000000000000000000000000000000000000000000000000000000000000000008000000000000000000000000000000000000000000000000000010000’,
data=u’00000002f70dac11a77280011f3072fbd4a2a689f6103ab1e8ff7f1e158ab1acd5cc55815bb8d71f254092c155bb6feb3bbda2031f60388d33ef026d1fd3b9c00dcd91a552dd0e300a7011e200000000000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000’,
midstate=u’fa9784fcfc8f08f597b65164a4d4a1b75c0d51ebd904ab7e19b29c23119fa1fd’,
target=u’00000000000000e2117000000000000000000000000000000000000000000000’)

Which is the same format as the original BTC network. Now, out the above, what does it mean? Is there a protocol description somewhere? What is the range I need to search in, and what it the chain length I need to find? What is midstate and target in this context?

Or have I just misunderstood the algorithm completely?

Any helps/tips/pointers are appreciated

Read the white paper and use the search function:
http://www.peercointalk.org/index.php?topic=1989.0

Aah, thanks!

Interestingly, I did read the white paper (hence where I found out about Cunningham chains), and I did a search before posting (but didn’t find anything).

Thanks for the pointer, I will go have a look at the thread now.

Unixnut I’m at about the same point as u in understanding and desire to make a primecoin miner… ideally this would lead to a gpu miner as well. Am here to bounce ideas off and try working together on this if u want

Fuzzybear

Sent from my HTC Desire using Tapatalk 2

Also, check this out:

Read the white paper and use the search function: http://www.peercointalk.org/index.php?topic=1989.0

When someone asks for an explanation, saying “read the white paper” or “look at the source code” isn’t constructive in my opinion. I think for anyone who has read the white paper it contains a small fraction of the information you would need to piece together the algorithm. As for the source code, it would take someone 5 minutes to explain some things that would take an hour or more of looking through the code and possibly coming out without any answers.

Well, I posted some information about the algorithm yesterday:
http://www.peercointalk.org/index.php?topic=2000.msg16749#msg16749
http://www.peercointalk.org/index.php?topic=1989.msg16756#msg16756

Primecoin requires the chain origin to be a multiple of the so-called block header hash like this:
origin = headerHash * x

The task of the miner is to find the value ‘x’ such that there is a chain of primes at that location.
For example, a Cunningham chain of the first kind will look like this:
origin - 1
origin * 2 - 1
origin * 4 - 1
…
origin * 2^i - 1

The header hash can be calculated as follows:
headerHash = HASH(nVersion, hashPrevBlock, hashMerkleRoot, nTime, nBits, nNonce)

Your miner is free to choose nNonce. The rest you can query from the daemon. If you’re using getwork, you need to decode the “data” string it returns. That string is actually the block header encoded in hexadecimal.
32 bits -> nVersion
256 bits -> hashPrevBlock
256 bits -> hashMerkleRoot
32 bits -> nTime
32 bits -> nBits
32 bits -> nNonce

For example, the string begins with “00000002”, which is the version field with a value of 2.

NOTE: Block submission using getwork was broken for a long time in Primecoin. We merged a pull request from hg5fm that fixes it, but I don’t know how well that fix works. I recommend looking at getblocktemplate and submitblock RPC calls.

Your miner first needs to try different values of nNonce until it finds a suitable header hash. The header hash is required to be greater than 2^255 (i.e. the most significant bit needs to be 1). The v0.2 proposal also requires that the header hash is a probable prime passing the Fermat’s test.

After you have the header hash, the mining algorithm will proceed as follows:

1. Multiply the header hash with some nice primorial like 47#.
2. Use a sieve to find promising candidates for the value of ‘x’.
3. Test all the promising candidates.

I’ll leave the sieve algorithm for another day. It’s somewhat complicated and requires understanding of modular arithmetic.

The testing is fairly easy. Once you have the origin, you test every successive number in the chain until the Fermat’s test fails. If you are doing the Fermat’s then on the number N, you need to calculate 2^(N-1) mod N. If the result is 1, the number is probably prime. Otherwise, you use the result to calculate the fractional length.

Thank you Mikaelh! This is really interesting, and more like what I needed to find out

Unfortunately the API I am using does not support getblocktemplate and submitblock (I will see if I can add it to the API later on).

For now, I got a dump out of primecoind. This is quite a bit different to getwork:
[tt]
block = {
“version” : 2,
“previousblockhash” : “ab3d24812a7127f3282fc83c3dea3787c597ebe806cdd40493b359e27227fff0”,
“transactions” : [
{
“data” : “0100000003c05be14dcc5c246209a80384739b665b812e731789db8cd23a65e07330f1d98f010000006b483045022100cf980a28198f56ae9ac5b2b870f58dd75a4d4a0471d3ffa6105b75a7f25000b402206276dca4f69f3a7ac11f6f8b15075385e5f1b0501ef7564378013fe67e0d5f4701210379678e2be060a31b63989e29c05dc4c289c32baff83bcfe31d141831acf55cbeffffffff3a26b3e8a0dfbd99041a52da5a6497c1b930c87557a5cb0afff8e6bb78984bfe000000006c493046022100a518c3a88fa875ab0c4f97246f7e6d2a0078f2ea6909e764b91e29341f5f547b022100902dcdd8bc8ee6569d33ad08ca10e4bd659d3853516ebe95dc7e881960df95fa0121029490370f73d7fbb146eb3196fa77eea8ea2880e0a539976828687a718e6dfb14ffffffff4890774310203871abea63f51fb4c52dc2262dccdb4e9f858ed0273944684fa3000000006c4930460221008527a8af84486e688085e37e51e4c87b72d46fc0a9efc4415803ce588bc2b738022100f2683b98758c48cad8754c5d74056af42ff0b4dc5ccd5dbda70de17bb1c22c960121036be05eb600483edb161296d5c1db507830db1727656fee886e7911b4e84bd462ffffffff02c014cc22000000001976a91450936e593426aaec290edb43bf56b0b664d3fd6b88acb9151000000000001976a91433656ecc4cff52a28e19d41f5bfd9e72ff00b22788ac00000000”,
“hash” : “48f6126528c7ec4cb0dfd0756d0d780414ebfba3522bdbecdb331d37a132a32b”,
“depends” : [
],
“fee” : 1000000,
“sigops” : 2
}
],
“coinbaseaux” : {
“flags” : “062f503253482f”
},
“coinbasevalue” : 918000000,
“target” : “000000000000000000000000000000000000000000006fa65800000000000000”,
“mintime” : 1390407106,
“mutable” : [
“time”,
“transactions”,
“prevblock”
],
“noncerange” : “00000000ffffffff”,
“sigoplimit” : 20000,
“sizelimit” : 1000000,
“curtime” : 1390410184,
“bits” : “0a6fa658”,
“height” : 371217
}

[/tt]

In some ways it is simpler, as I get the previousblock hash, as well as the valid noncerange. Not sure what the rest is. Can I assume that “data” here is in the same format as the getwork result?

As for the sieve? In what context is that? Is that a prime number sieve, such as Eratosthenes’es one? In which case the sieve is being used to calculate primes, correct?

Thank you very much for your input. It was really helpful!

@FuzzyBear: Sure, I don’t mind help with this. At the moment I’m trying to get a Python version of the algorithm to work. Do you know Python? I figured we start with that, and once we have a working implementation, we can see about where to go. How does that sound?

No, the format is not the same because that’s transaction data.

It’s not really comparable to the traditional sieve of Eratosthenes. The sieve gives promising candidate multipliers that you can multiply the header hash with. You get the chain origin by using multiplication like this:
origin = headerHash * primorial * candidateMultiplier

The candidates are not guaranteed to produce primes but the probability is higher than normal. The sieve guarantees a high probability for the first 10 numbers to be prime.

Once again, thanks for your patience with me, while I try to understand what is going on. Right, so based on what you’ve written here, and on the other threads. I get the following algorithmic steps. Please correct me if I’m wrong. I’ve put questions/things I’m unsure of in bold:

[tt]

1. Try repeated generations of HASH(nVersion, hashPrevBlock, hashMerkleRoot. nTime, nBits, nNonce):

   • Each time vary nNonce (keeping within NonceRange) until the headerhash > 2^255
     * Which hash algorithm is used here? Is it a standard one like SHA?

2. Multiply header hash by a primorial sequence ( Can we keep this fixed at say, 47, as you mentioned?)

3. Find promising candidates for x, meaning:

   • Find all prime numbers
   • check to see which are Cunningham Chains (and find out which is the longest)
     * I’m right in thinking, this is the bit of the algorithm that involves the sieve you haven’t talked about yet? Although that works by using candidateMultipliers and a test for primality?

4. Calculate origin:

   • origin = headerHash * x

5. If prevBlockHeaderHash is divisible by origin:

   • Good to go! Submit block

All the above must happen within 1 minute, as the block changes every minute.
[/tt]

Is that the general execution flow of the algorithm? Also, where in the code could I find the sieve algorithm? I might take a stab at trying to understand it myself.

[quote=“Unixnut, post:9, topic:1848”]1. Try repeated generations of HASH(nVersion, hashPrevBlock, hashMerkleRoot. nTime, nBits, nNonce):
* Each time vary nNonce (keeping within NonceRange) until the headerhash > 2^255
* Which hash algorithm is used here? Is it a standard one like SHA? [/quote]
The hash algorithm is double SHA-256, i.e. you first run SHA-256, and then you take the output and run SHA-256 again.

47# should get you started at least. If you want maximum performance, you will need to change that.

[quote=“Unixnut, post:9, topic:1848”]3. Find promising candidates for x, meaning:
* Find all prime numbers
* check to see which are Cunningham Chains (and find out which is the longest)
* I’m right in thinking, this is the bit of the algorithm that involves the sieve you haven’t talked about yet? Although that works by using candidateMultipliers and a test for primality?[/quote]
I think you’re slightly on the wrong track here. In general, we are not interested in finding all the primes in some range of numbers. There’s a few reasons for that:

1. There’s a fair number of primes in the range we are interested in. For example, if you take one million numbers around 2^300, you would expect to find about 4500 primes there.
2. It’s easier to rule out numbers that are definitely composites than test for probable primality.
3. We are interested in chains of primes, not individual primes.

The sieve works by ruling out candidates where we know that one number in the chain is definitely a composite. In that sense, we don’t care if we some of the numbers are primes. We don’t care if 9 out of 10 numbers are primes if we know that one of them is a composite. Of course, if we really have that many primes somewhere, we should also check the surroundings, which is what the extended sieve algorithm does.

[quote=“Unixnut, post:9, topic:1848”]4. Calculate origin:

• origin = headerHash * x[/quote]
  Yes, and after this you need a step where you do the Fermat primality test on the chain that starts at ‘origin’.

[quote=“Unixnut, post:9, topic:1848”]5. If prevBlockHeaderHash is divisible by origin:
* Good to go! Submit block[/quote]
You don’t need to care about prevBlockHeaderHash in any way. You’re on the wrong track here too.

Yes, and ideally you want to get results a lot faster to be competitive with other miners.

I recommend looking at Sunny’s reference miner here:

You should look at the function BitcoinMiner() in main.cpp which is the top-level function for the mining threads. You can find the sieve implementation in the files prime.cpp and prime.h.

[quote=“mikaelh, post:6, topic:1848”]Well, I posted some information about the algorithm yesterday:
http://www.peercointalk.org/index.php?topic=2000.msg16749#msg16749

Primecoin requires the chain origin to be a multiple of the so-called block header hash like this:
origin = headerHash * x

The task of the miner is to find the value ‘x’ such that there is a chain of primes at that location.
For example, a Cunningham chain of the first kind will look like this:
origin - 1
origin * 2 - 1
origin * 4 - 1
…
origin * 2^i - 1

The header hash can be calculated as follows:
headerHash = HASH(nVersion, hashPrevBlock, hashMerkleRoot, nTime, nBits, nNonce)

Your miner is free to choose nNonce. The rest you can query from the daemon. If you’re using getwork, you need to decode the “data” string it returns. That string is actually the block header encoded in hexadecimal.
32 bits -> nVersion
256 bits -> hashPrevBlock
256 bits -> hashMerkleRoot
32 bits -> nTime
32 bits -> nBits
32 bits -> nNonce

For example, the string begins with “00000002”, which is the version field with a value of 2.

NOTE: Block submission using getwork was broken for a long time in Primecoin. We merged a pull request from hg5fm that fixes it, but I don’t know how well that fix works. I recommend looking at getblocktemplate and submitblock RPC calls.

Your miner first needs to try different values of nNonce until it finds a suitable header hash. The header hash is required to be greater than 2^255 (i.e. the most significant bit needs to be 1). The v0.2 proposal also requires that the header hash is a probable prime passing the Fermat’s test.

After you have the header hash, the mining algorithm will proceed as follows:

1. Multiply the header hash with some nice primorial like 47#.
2. Use a sieve to find promising candidates for the value of ‘x’.
3. Test all the promising candidates.

I’ll leave the sieve algorithm for another day. It’s somewhat complicated and requires understanding of modular arithmetic.

The testing is fairly easy. Once you have the origin, you test every successive number in the chain until the Fermat’s test fails. If you are doing the Fermat’s then on the number N, you need to calculate 2^(N-1) mod N. If the result is 1, the number is probably prime. Otherwise, you use the result to calculate the fractional length.[/quote]

Hi, I’m trying to undestand primecoin protocol/algorithm. I have a question about multiplier ‘x’ you mentioned in this post. I’ve understand what the primorial function is, to have a number that has a lot of prime factors, so that this number -1 or +1 is doesn’t have this prime factors. So now I have headerhash * primorial. Now I don’t understand why it is then necessary to multiply this with number ‘x’. Does it have the same function of multiply headerhash with primorial?
How this ‘x’ is calculate?
I’ve read that it is used the sieve but it’s not really evident why and how?
After that multiplication the origin it is obtained. Then to find the chain I use again the sieve? Or simply I try to see if the chain from the origin is a cunningham chain or not. I’ve searched for details about this questions on internet but it’s quite difficult. The only source I’ve found is the source code but it’s very very long and lot of file, I’ve seen main.cpp and prime.cpp but I don’t find answers.

Well, here’s a brief description of the idea behind the sieve. Note that you should understand modular arithmetic first.

The goal is to find some number x so that the numbers in the chain are not divisible by small primes (say the first 14,000 primes).

So the numbers look like this:
headerHash * primorial * x * 2^k - 1 (Cunningham chain of the first kind)
and/or
headerHash * primorial * x * 2^k + 1 (Cunningham chain of the second kind)

Here k = 0, 1, 2, …, N -1 where N is the length of the chain

Now the question is how do we filter out numbers that are composite (i.e. definitely not prime). Let’s say we want to filter out all numbers divisible by prime p. We can write this using modular arithmetic as:

headerHash * primorial * x * 2^k - 1 = 0 (mod p)

And solving for x gives:
x = inverse(headerHash * primorial) * inverse(2)^k (mod p)

Note that inverse() is the modular multiplicative inverse!

This equation actually tells us all the multipliers we can cross out as producing composites. For example, if we set k = 0 (first number in the chain), we get:
x = inverse(headerHash * primorial) (mod p)

Here inverse(headerHash * primorial) is the first multiplier (basically an offset) that gives a composite result. After that every p’th multiplier also produces a composite.

Below is an example with these values: headerHash = 1, primorial = 2 * 3 * 5 * 7 = 210, p = 53

First we calculate:
inverse(210) = 26 (mod 53)

So 26 is our first offset, and indeed 210 * 26 - 1 gives 5459 which is divisible by 53. We can check that every 53’th multiplier after this offset gives a result divisible by 53:
210 * (26 + 53) - 1 = 16589 is divisible by 53
210 * (26 + 2 * 53) - 1 = 27719 is divisible by 53
210 * (26 + 3 * 53) - 1 = 38849 is divisible by 53

So now we can cross out 26, 26 + 53, 26 + 2 * 53, etc. in our sieve because they clearly produce results divisible by 53 which cannot be prime.

Next we can eliminate composites divisible by 53 in the second number of the chain. We calculate:
inverse(2) = 27 (mod 53)
26 * 27 = 13 (mod 53)

So 13 is the offset for which the second number in the chain is composite. Now we get:
210 * 2 * 13 - 1 = 5459 is divisible by 53
210 * 2 * (13 + 53) - 1 = 27719 is divisible by 53
210 * 2 * (13 + 2 * 53) - 1 = 49979 is divisible by 53
210 * 2 * (13 + 3 * 53) - 1 = 72239 is divisible by 53

And again we can cross out 13, 13 + 53, 13 + 2 * 53, etc. in our sieve.

The third offset would be:
13 * 27 = 33 (mod 53)

And again we can check: 210 * 2^2 * 33 - 1 = 27719 is divisible by 53

In total there will be N offsets (right now N = 10 because difficulty is 10.9751). This means we can cross out a lot of multipliers in the sieve with minimal effort.

[quote=“mikaelh, post:12, topic:1848”]The goal is to find some number x so that the numbers in the chain are not divisible by small primes (say the first 14,000 primes).
…[/quote]

First thank you very much for your answer.
I think I’ve understood some parts of your answer, but I have also some doubts.

Question 1
I’ve understood that with this sort of sieve we works on number x.
So we necessarily need to mark valid or invalid x as a list or something like that so we have a list we delete values from?
Do we have a list of values for x from 1 to a very big number? Or it starts from some other value?
And what is the very big number limit?

Question 2
With the sieve we cross out all the x values that produces some numbers in their possible cunningham chain that are divisible for some first primes(assuming the first 14.000 primes). How many primes to consider is fixed by the protocol or everyone could choose this sort of limit? I imagine that highest is the number of primes considered highest is the possibility to find a valid origin, but anyway it is slower. Right?

Question 3
Assuming that our primorial is until 47, the first prime we check is p=53 and so we do the operations you describe and we delete 26, 26 + 53, 26 + 2 * 53, etc., 13, 13 + 53, 13 + 2 * 53, and so on.
We cross out all x + np values. N starts from 0 and ends when? I assume that if we have our list of possible x values we consider n until x + np is a number contained in the list. It is right?
After doing this for 10 offset we consider the next prime after 53 and we do the same operations and so we will delete some other values from the list and then we will go on until we do this operation with the 14,000th prime number. After that we have our huge list reduced, because we have deleted all the invalid x founded. Is it right?

Question 4
Now in our list we have possible x values that can produce chain with number not divisible for first 14,000 primes, but we don’t know if they are prime or not. So now we start to consider the first possible x value of the list, calculate the origin and build its cunningham Chain? Do we do Fermat and other test on these numbers? If all chain numbers pass the test we find our valid cunningham chain, we can build the primecoin block hashing block header hash and the proof of work certificate (primorial * x)?
If some numbers doesn’t pass the test we consider the next x possible value and so on? If no one of x values find a valid chain we change the nonce in the block header to generate a different header hash?

Thank you in advance

[quote=“smemo92, post:13, topic:1848”]Question 1
I’ve understood that with this sort of sieve we works on number x.
So we necessarily need to mark valid or invalid x as a list or something like that so we have a list we delete values from?
Do we have a list of values for x from 1 to a very big number? Or it starts from some other value?
And what is the very big number limit?[/quote]

This are implementation decisions. For example, in celtusminer I use a bitvector and the chain’s origin is something like: prevHashprimorialchainMultiplierpowerOfTwo (chainMultiplier is your x). If k is the exponent in powerOfTwo the bitvector[chainMultiplier][powerOfTwo] = 1 if prevHashprimorialchainMultiplierpowerOfTwo +/- 1 (depends on the chain type) is know to be composite. You can use a list instead of bitvector, but I think that deleting is going to be very expensive depending (bitvector O(1), list O(n), hashset O(1), set O(logN)).

Here is my code if you are interested: https://github.com/brtzsnr/celtusminer/blob/master/src/celtus/celtus.go#L43

[quote=“smemo92, post:13, topic:1848”]Question 2
With the sieve we cross out all the x values that produces some numbers in their possible cunningham chain that are divisible for some first primes(assuming the first 14.000 primes). How many primes to consider is fixed by the protocol or everyone could choose this sort of limit? I imagine that highest is the number of primes considered highest is the possibility to find a valid origin, but anyway it is slower. Right?[/quote]
IIRC, XPT v6 tries to fix the upperlimit for the sieving primes, but in general you pick them to get the best performance out of your miner.

[quote=“smemo92, post:13, topic:1848”]Question 3
Assuming that our primorial is until 47, the first prime we check is p=53 and so we do the operations you describe and we delete 26, 26 + 53, 26 + 2 * 53, etc., 13, 13 + 53, 13 + 2 * 53, and so on.
We cross out all x + np values. N starts from 0 and ends when? I assume that if we have our list of possible x values we consider n until x + np is a number contained in the list. It is right?
After doing this for 10 offset we consider the next prime after 53 and we do the same operations and so we will delete some other values from the list and then we will go on until we do this operation with the 14,000th prime number. After that we have our huge list reduced, because we have deleted all the invalid x founded. Is it right?[/quote]
Yes. Assuming ‘invalid’ here means ‘definitely composite’.

[quote=“smemo92, post:13, topic:1848”]Question 4
Now in our list we have possible x values that can produce chain with number not divisible for first 14,000 primes, but we don’t know if they are prime or not. So now we start to consider the first possible x value of the list, calculate the origin and build its cunningham Chain? Do we do Fermat and other test on these numbers? If all chain numbers pass the test we find our valid cunningham chain, we can build the primecoin block hashing block header hash and the proof of work certificate (primorial * x)?
If some numbers doesn’t pass the test we consider the next x possible value and so on? If no one of x values find a valid chain we change the nonce in the block header to generate a different header hash?[/quote]
If none of the number pass you have two options:

[ol][li]pick a new nonce (as you suggested) so you have another header hash[/li]
[li]search for larger fixed multipliers (another origin).[/li][/ol]

[quote=“smemo92, post:13, topic:1848”]Question 1
I’ve understood that with this sort of sieve we works on number x.
So we necessarily need to mark valid or invalid x as a list or something like that so we have a list we delete values from?
Do we have a list of values for x from 1 to a very big number? Or it starts from some other value?
And what is the very big number limit?[/quote]
All the fast CPU and GPU miners use a bitmap for the sieve. Say your sieve size is 1,000,000 numbers, then you have a bitmap of 1,000,000 bits. You can initialize all bits as zero and then set the composites to 1 (or vice versa if you want). Sieve size for CPU miners is about 1 million multiplied by the number of extensions (10). So about 10 million bits for each thread. GPU miners use bigger sieves (at least 50 million bits). This is shared between the threads though due to the nature of GPUs.

[quote=“smemo92, post:13, topic:1848”]Question 4
Now in our list we have possible x values that can produce chain with number not divisible for first 14,000 primes, but we don’t know if they are prime or not. So now we start to consider the first possible x value of the list, calculate the origin and build its cunningham Chain? Do we do Fermat and other test on these numbers? If all chain numbers pass the test we find our valid cunningham chain, we can build the primecoin block hashing block header hash and the proof of work certificate (primorial * x)?
If some numbers doesn’t pass the test we consider the next x possible value and so on? If no one of x values find a valid chain we change the nonce in the block header to generate a different header hash?[/quote]
The traditional method for primality testing is to use the Fermat test for the first number in a chain. For subsequent numbers we use Henri Lifchitz’s generalization of the Euler-Lagrange theorem (link). The Euler-Lagrange-Lifchitz primality test has an interesting property: if the first number is an actual prime (highly likely), then all subsequent numbers are guaranteed to be primes! So if you want to do deterministic testing to confirm the primality of the numbers, you only need to test the first number. Even if the first number happens to be composite, the others are still highly likely to be primes (Euler-Lagrange-Lifchitz test is pretty much equivalent to Fermat test in that case).

Thanks you for your answer.

I define invalid x because these x generate composite number for their chain, it’s not the x that is composite but the number it generates for its possible chain. Isn’t it? In mikaelh example we delete from possible x values the following values: 26, 26 + 53, 26 + 2 * 53, etc., 13, 13 + 53, 13 + 2 * 53, but the “definitely composite” numbers are 16589, 27719, 38849, 5459, 27719, 49979, 72239, but we don’t delete these but the x related to. Isn’t it? Maybe I confused something ideas or it’s just a terminological issue.

I will study this theorem, thanks