The earlier submit checked out a method for inverting a number of integers mod m on the similar time, utilizing fewer compute cycles than inverting every integer individually. This submit will do one thing analogous for prime chains, revisiting a submit from a number of days in the past about testing prime chains.
A first-rate chain is a sequence of primes through which every is twice its predecessor, plus or minus 1. In a Cunningham chain of the primary variety, it’s all the time plus, and in a Cunningham chain of the second variety, it’s all the time minus.
Primecoin is a cryptocurrency that makes use of discovering prime chains as its proof-of-work (PoW) process. The miner has a alternative of discovering considered one of three sorts of prime chain: a Cunningham chain of the primary or second variety, or a bi-twin chain. The size of the mandatory chain varies over time to maintain the issue comparatively fixed. Different PoW blockchains do one thing comparable.
Some individuals say that Primecoin has miners seek for primes for PoW. That’s not fairly proper. Miners should discover a chain of medium-sized primes relatively than discovering one huge prime. This results in extra predictable compute occasions.
There’s a technique to take a look at a candidate Cunningham chain of the second variety unexpectedly. Henri Lifchitz provides his algorithm right here. Given a sequence of numbers
n1, n2, n3, …, nokay
the place ni = 2ni−1 − 1 for every i and n0 = 1 mod 4, all of the numbers within the sequence are in all probability prime if
For instance, contemplate the chain
31029721, 62059441, 124118881
Observe that 31029721 mod 4 = 1 and 31029721 = 2*15514861 − 1. The next code demonstrates that the numbers within the chain are possible primes as a result of it prints 1.
n0 = 15514861 n1 = 2*n0 - 1 n2 = 2*n1 - 1 n3 = 2*n2 - 1 prod = n0*n1*n2*n3 print( pow(2, n2 - 1, prod) )
Subsequent I wished to attempt the algorithm on a lot bigger numbers the place its effectivity can be extra obvious, as within the earlier submit. However once I did, the take a look at returned a end result apart from 1 on a recognized Cunningham chain of the second variety. For instance, once I change the primary two traces of code above to
n1 = 49325406476*primorial(9811, False) + 1 n0 = (n1 + 1) // 2
the code returns a big end result. I verified that every of the numbers within the chain are prime utilizing Sympy’s isprime perform.
Often a possible prime take a look at can have false positives however by no means a false detrimental. I haven’t checked out Lifschitz technique carefully sufficient to inform whether or not it could have false negatives, however the code above suggests it could.
