Creating Chinese Remainder Theorem (crt) files

Creating Chinese Remainder Theorem (crt) files

The ctr algorithm is divided into 2 parts. The first part is a simple greedy algorithm which tries to find offsets for each involved prime so that the desired number range has the least prime candidates as possible.

The second part is an evolutionary algorithm which tries to improve the results from the greedy algorithm. Therefore the greedy algorithm will be executed several times with slightly different parameters to produce ctrs which differ in quality which than can be used by the evolutionary algorithm.

The output is a text file which can be used by gapminer as an input for ctr sieving.

Parameter description:

--calc-ctr          Indicates that we want to calculate a ctr file.

--ctr-strength      This is used to vary the computing time spent
                    within the greedy algorithm. Higher strength
                    can yield better results.

--ctr-primes        The number of primes to use in the ctr file. The more
                    primes the better the ctr result but the shift
                    also increases. Minimum shift can be calculated as 
                    the binary logarithm of the product of all primes:
                    log2(p1 * p2 * ... *pn).

--ctr-evolution     Whether to use the evolutionary algorithm or not.

--ctr-fixed         This number indicates the number of starting primes
                    which would get touched by the evolutionary algorithm
                    the offsets for the primes 2,3,5,7,11... are mostly
                    perfect computed by the greedy algorithm and changing
                    them only declines the result.

--ctr-ivs           The number of individuals used in the evolutionary algorithm.
                    More increases computing time but mostly also the 
                    result quality.

--ctr-range         Percent deviation from the number of primes.
                    Useful if you don't want to look for a specific number 
                    of primes.

--ctr-bits -256     The shift value you later use for sieving has to be greater
                    than log2(p1*p2*..*pn). With this flag you can fine-tune a specific
                    shift by setting this to shift - log2(p1*p2*..*pn).

--ctr-merit         The target merit (while testing the ctr it seemed that 
                    sieving for target-merit - 1 yields the best results)

--ctr-file          The target ctr output file. You can open this with a 
                    text editor. Look for the n_candidates value, the smaller
                    it is the better the ctr file.

Calculating crt-bits:

In a j0nn9 post to bitcointalk…

If you want to generate a file for, e.g. shift 384 with ctr-primes = 58

ctr-bits = $shift\; -\; log2(p1*p2*..*pn)$

Or, expressed using primorial notation:

ctr-bits = $384\; -\; log2(58\#)$

ctr-bits = $384\; -\; 368\; =\; 16$

Achieving the above using Python 3

from sympy import primorial
>>> from math import log2
>>> log2(primorial(58))
367.0750275397664

For specific settings used to calculate the set of crt files, see:

• Settings used to create the standard set of 22m crt files as originally created by j0nn9 2015-04-04

• Settings used to create the standard set of 22m crt files as originally created by j0nn9 2015-04-04