Barrett’s reduction of \(u\) modulo \(p\) with the reciprocal \(m\) is \(r = u - \lfloor u m / 2^{64} \rfloor \, p\), and \(r - p\) when \(r \ge p\) (find_points.c:1639-1650); the value of \(f\) at \(a\) modulo \(p\) is Horner’s rule from \(c_d\) on the coefficients reduced modulo \(p\), with Barrett’s reduction at the end and, for \(d {\gt} \mathrm{hornerSteps}\), after every \(\mathrm{hornerSteps}\) steps (find_points.c:1726-1731, find_points.c:1737-1744); the table is made of these values and handed back with the coefficients modulo \(p\), or none, the exit, when no entry of it is true (find_points.c:1683-1697). Then:

1. (1)

   for \(p {\gt} 0\) and \(u {\lt} 2^{64}\), Barrett’s reduction with \(m = \lfloor (2^{64} - 1)/p \rfloor \) gives \(u \bmod p\);

2. (2)

   for \(p {\lt} \mathrm{maxPrimeEven}\), \(a {\lt} p\) and coefficients below \(p\), the schedule gives \(f(a) \bmod p\), and the accumulator stays below \(p^{\mathrm{hornerSteps} + 1} {\lt} 2^{64}\);

3. (3)

   for \(0 {\lt} p {\lt} \mathrm{maxPrimeEven}\) the computed entry, the prime with its table and its inverses, is that of Definition 6.1, with the coefficients modulo \(p\), or none exactly when no entry of that table is true.

The tables of \(m = p^e\) as examine_power makes them from the coefficients reduced modulo \(m\) (find_points.c:2267-2282), in bit arrays of \(\mathrm{modWords} = \lceil \mathrm{maxPrimeEven}/64 \rceil \) words, bit \(x\) in bit \(x \bmod 64\) of word \(\lfloor x/64 \rfloor \) (rp-private.h:523-523): the bits of the squares \(x^2 \bmod m\), \(x {\lt} m\), set in a bit array sq (find_points.c:2283-2284); the bits of fsq and gsq set where the values of \(f\) and of the reversed polynomial, by Horner’s rule, are marked in sq; and the inverses by the extended Euclidean algorithm modinv (find_points.c:2241-2252), \(0\) for the residues divisible by \(p\) (find_points.c:2302-2303). Then:

1. (1)

   for \(1 {\lt} m\) and \(x\) prime to \(m\), modinv gives the inverse of \(x\) modulo \(m\) in \([0, m)\); for a prime \(p\) and \(e \ge 1\), every entry of the inverses is below \(p^e\), and the entry of a unit \(x {\lt} p^e\) is its inverse;

2. (2)

   \(\mathrm{maxPrimeEven} \le 64\, \mathrm{modWords}\), and for \(m \le 64\, \mathrm{modWords}\) a bit array of \(\mathrm{modWords}\) words gets the bit of every square modulo \(m\) set;

3. (3)

   for a prime \(p\), \(e \ge 1\) and \(p^e \le 64\, \mathrm{modWords}\), the tables of \(p^e\) have these inverses, bit \(x {\lt} p^e\) of fsq set whenever \(f(x)\) is a square modulo \(p^e\), and bit \(t {\lt} p^e\) of gsq, for \(p \mid t\), set whenever the reversed polynomial of the even degree \(D = 2 \lceil d/2 \rceil \) takes a square value at \(t\); only this direction is needed, since a further bit loses no point.

The closed form of the row of a residue \(r\) modulo \(m\), for an admission test \(\mathrm{adm}\), which says whether the row of \(r\) admits a number \(N\), is the array of \((m + \mathrm{chunk} - 1)\, \mathrm{rbaPack}\) words whose word \(j\) has bit \(t\) set exactly when \(t {\lt} 64\) and \(\mathrm{adm}(r)\) admits \(64 j + t\). With the admission test of a sieve entry, of the table of a prime or of the tables of a prime power, it is the row that ratpoints builds; it has no C code of its own. Then:

1. (1)

   bit \(t\) of word \(j {\lt} (m + \mathrm{chunk} - 1)\, \mathrm{rbaPack}\) is \(t {\lt} 64\) and \(\mathrm{adm}(r)(64 j + t)\);

2. (2)

   for \(m {\gt} 0\) and a test that does not change when a multiple of \(m\) is added to the number, word \(j\) is word \(j \bmod m\, \mathrm{rbaPack}\), so that the closed form of a row of a sieve entry of positive modulus repeats its first \(m\) bit arrays after them;

3. (3)

   a word holds \(n \le 64\) bits of a pattern \(g\) of period \(m\) from \(s\) on when its bit \(t {\lt} n\) is \(g((s + t) \bmod m)\) and its other bits are clear; if \(g(N \bmod m) = \mathrm{adm}(r)(N)\) for every \(N\), an array of \((m + \mathrm{chunk} - 1)\, \mathrm{rbaPack}\) words whose word \(j\) holds the 64 bits of \(g\) from \(64 j\) on is the closed form; the contracts of the builders conclude by this.

The row of \(0\) of a prime \(p\): the \(p\) words of the forbidden divisor \(p\), whose word \(r\) has bit \(t\) clear exactly when \(p \mid 64 r + t\) (Ratpoints.Sieve.forbiddenRow), written \(\mathrm{rbaPack}\) times and followed by the copies (gen_find_points_h.c:122-134). The other rows by one function for the primes below \(64\) and one for those above, from the table of the prime, the reference, the residue \(b\) and the store: bit \(a {\lt} p\) of the pattern the entry of the table at \(a d \bmod p\) for the inverse \(d\) of \(b\), by a loop that steps four residues by \(4 d \bmod p\) (init.c:72-83), rotated into the first \(p\) words, the copies (init.c:99-111), and the row published in the table of the reference (init.c:178-183, init.c:239-244). Then:

1. (1)

   for \(p {\gt} 0\) the row of \(0\) is the closed form of the row of \(0\) of every table of \(p\), and its first \(p\) words are those that the forbidden divisors read (Chapter 8);

2. (2)

   for the table of a prime \(p {\lt} 64\) and \(0 {\lt} b {\lt} p\) whose inverse in the table is below \(p\), the function from CODE_INIT_SIEVE1 returns the closed form of the row of \(b\), and the store with it published in the table of the reference; the same holds for \(p \ge 64\) with \(p \bmod 64 \ne 0\) and the function from CODE_INIT_SIEVE2.

The builders need no primality and nothing of the table of squares.

The layout of a pattern of period \(m\): word \(x {\lt} m\, \mathrm{rbaPack}\) of the row the 64 bits from the offset \(64 x \bmod m\) on of the pattern repeated through \(w = \lfloor (m + 127)/64 \rfloor \) words, then the copies (init.c:259-267, init.c:280-297). The row of the residue \(b\) of a prime power \(m\), from its tables, the reference and the store: for a unit \(b\), bit \(x\) of the pattern set when bit \(x b^{-1} \bmod m\) of fsq is (init.c:369-375), and for \(p \mid b\), bit \(x\) of a unit \(x\) set when bit \(b x^{-1} \bmod m\) of gsq is (init.c:378-385); the pattern laid out, and the row published in the table of the reference (init.c:391-393). Then:

1. (1)

   for \(0 {\lt} m \le 64\, \mathrm{modWords}\) and a pattern whose bits \(x\) with \(m \le x {\lt} 64 \lceil m/64 \rceil \) are clear, word \(j\) of the row holds the 64 bits of the pattern, read with period \(m\), from \(64 j\) on;

2. (2)

   for \(b {\lt} m \le 64\, \mathrm{modWords}\) whose entry in the table of inverses is below \(m\), the builder returns the closed form of the row of \(b\), and the store with it published in the table of the reference.

The row of the residue \(b\) of a product: the rows of its factors at \(b\) modulo their moduli, read from their tables or built into them through the pointer of the entry of each factor (init.c:407-414); the first laid down in blocks of its length (init.c:419-423), the others and-ed in (init.c:424-429), the copies (init.c:430-430), and the row published (init.c:443-445). A factor is buildable when its builder has what it needs: a prime \(p {\gt} 0\) with its inverses below \(p\) and \(p \bmod 64 \ne 0\) for \(p \ge 64\), or a prime power \(0 {\lt} m \le 64\, \mathrm{modWords}\) with its inverses below \(m\); it may be called below its modulus, for a prime not at \(0\). Then:

1. (1)

   a buildable factor called where it may be called returns the closed form of its row and publishes it in the table given;

2. (2)

   if the product has a positive modulus \(m\) and a factor, the moduli of its factors divide \(m\), its factors are buildable, the rows present in their tables are closed forms, a row absent below the modulus of a factor is one where its builder may be called, and two factors with one reference have the same closed forms, then the builder returns the closed form of the row of \(b\), and the store has grown by rows of the factors (the tables keep their sizes, no row is replaced, every new row is the closed form of a factor whose table it is in), with the row of the product published.

A store holds a function \(R\) of the references and the residues for a list of entries when every row present in the table of a reference \(\rho \) at \(r\) is \(R(\rho , r)\) and the table of every prime factor of the entries has its row of \(0\). An entry at the position \(n\) fits \(R\) when it has the reference and the kind of builder of that position (and, with one factor, the modulus of that factor), a positive modulus, a factor, moduli of the factors dividing its modulus and buildable factors, and \(R\) at its reference and at those of its factors is the closed form of their rows; a store fits a list of entries when it holds some \(R\) for them that every entry fits. The rows of the references of a run are the closed forms of the rows of the table of a prime, of the tables of a prime power and of the entry of a product at its position; a store is made for a list of entries when it holds the rows of the references of every run whose entries begin with the list, and every table of rows of a prime in it, or of a prime factor of the entries, has its row of \(0\). Then:

1. (1)

   if the row present in the table of an entry at \(b\) is the closed form, and the builder has what it needs when the row is absent, the row read or built is the closed form of the row of \(b\), and the store is the same or has grown by rows of the factors, with the row published;

2. (2)

   the store of the loop of the tables, which holds the rows of \(0\) of the primes and no others, is made for no entries; adding the tables of rows of further entries, each with the reference and the kind of builder of its position and with positive primes, gives a store made for the longer list; a store made for the entries of a run holds the rows of their references for them; and an entry of a modulus as the choice makes it (Chapter 6) fits the rows of the references of the run at its position;

3. (3)

   for a store that holds \(R\) for a list \(L\), entries of \(L\) that fit \(R\) at their positions and residues below their moduli, the sieve specs that set_rows makes and the missing rows complete have the closed forms of the rows of their entries at their residues, the offsets of the class, the start \(0\) and the end \(p\), and the store after them holds \(R\) for \(L\); so a store that fits the entries of a run fits them after each denominator.

The row of \(b\) of a sound entry admits \(a\) for every triple \((a, y, b)\) with \(\gcd (a, b) = 1\) and \(y^2 = F(a, b)\), and the numerator of every point with the denominator \(b\) that the brute-force reference lists (Ratpoints.BruteForce.pointsOfDen) survives every list of sound entries for \(b\).