The primes of the sieve are the odd primes below \(1024\) in increasing order (primes.h:29-40), which decide checks; ratpoints chooses its moduli among the \(\mathrm{numPrimes}\) of them below \(2^{\mathrm{maxBitsInPrime}}\), the \(53\) primes up to \(251\) for the \(8\) bits of the default build, whose Makefile passes PRIME_SIZE \(= 8\) in place of the header’s own default \(7\) (rp-private.h:321-323, rp-private.h:325-361). The table of a prime \(p\) has \(p + 1\) entries: entry \(x {\lt} p\) says whether \(f(x)\) is a square modulo \(p\), and entry \(p\) whether there are points at infinity modulo \(p\), that is, whether \(d\) is odd or \(c_d\) is a square modulo \(p\); it is kept with \(p\) and the inverses modulo \(p\) (rp-private.h:542-555). The row of the denominator \(b\) admits the numerator \(a\) when, for \(r = b \bmod p\) and \(x = a \bmod p\), the entry at \(x r^{-1} \bmod p\) is true if \(r \ne 0\), and \(x \ne 0\) if \(r = 0\). This admission test is what the bit of \(a\) in the row of \(r\) says in ratpoints.

The loop of sieving_info over the primes of the table while fewer than the number to look at, the normalized value of -p, have been looked at (find_points.c:2601-2605). The examination of a prime (find_points.c:2606-2626) gives its table, the coefficients modulo \(p\), its density (the share of the numerators that its rows let through) and a code: \(-1\), the exit, when the curve has no points modulo \(p\) (Chapter 4); \(0\) when the prime says nothing; \(2\) when it says only that numerator and denominator are coprime; \(1\) otherwise. A prime that says something becomes a candidate with its key for the first stage, and its table of rows goes into the store; while fewer than their bound have been found, the coefficients modulo \(p\) give the forbidden divisor of \(p\) (Chapter 8). When the caller left the number of primes to the library, the loop looks at one more prime, at most \(\mathrm{numPrimes}\) in all, while the first two stages would be short of candidates that say more than coprimality (find_points.c:2694-2705).

The contract: for options that look at no more than \(\mathrm{numPrimes}\) primes, an exit means that the curve has no points of any height; otherwise at most \(\mathrm{numPrimes}\) primes are to be looked at, each table that the loop keeps, that of a prime that says something, is that of Definition 6.1 for one of the first \(\mathrm{numPrimes}\) primes, every candidate is a prime of the table with the sieve entry of its table, the forbidden divisors are sound, and the store holds the tables of rows of the primes.

The tables of a prime power \(q = p^e\) are the bit arrays fsq, bit \(x {\lt} q\) set when \(f(x)\) is a square modulo \(q\), and gsq, bit \(t\) set when \(p \mid t\) and \(\tilde f(t)\) is a square modulo \(q\), with the inverses of the units (rp-private.h:531-534). Its row of \(b\) admits \(a\), for \(r = b \bmod q\) and \(x = a \bmod q\), when bit \(x r^{-1}\) of fsq is set if \(p \nmid r\), and when \(p \nmid x\) and bit \(r x^{-1}\) of gsq is set if \(p \mid r\). A factor is a prime with its table or a prime power with its tables. The sieve entry of a modulus \(m\) holds its factors, the reciprocal of \(m\), with which the sieve reduces, the fields of the packing (Chapter 9), the reference to its table of rows and the kind of its builder (Chapter 7), its density, and the count of its factors, \(0\) for a prime, \(1\) for a prime power and their number for a product (rp-private.h:542-555). Its row of \(b\) admits \(a\) when the row of every factor admits \(a \bmod m\) at \(b \bmod m\); a numerator survives a list of entries for \(b\) when the row of \(b\) of every entry admits it, the interface between the sieve and the check.

A candidate modulus carries its density, key and cost, its mask of primes, its sieve entry and the codes of its factors (find_points.c:147-149). Its cost per word swept, in units of an and of the first stage, is a part for every word, the cost of its entry in the list of the moduli of a denominator and, in the first two stages, the costs of its set-up and, for a positive cost of a row, of its table of rows, spread over the \(U\) words and the \(V\) denominators of the run (find_points.c:1220-1235); its key is that cost over \(-\log r\) (find_points.c:1241-1247), with a variant for the first stage (find_points.c:1256-1270). The rule of the first stage always takes the first candidate and then the next while the survivors per word that it removes, weighted by what a surviving word costs further on, exceed a target times its cost (find_points.c:1583-1589); the second stage adds as many moduli as an offset, \(11\) by default, scaled by \(1/(1 + u_0/U)\) (find_points.c:1619-1626). The run is estimated from \(64\) samples of each segment of the loop over the denominators (find_points.c:1939-1944), and the cost of an exact check from the bit lengths of the coefficients and of \(H\) (find_points.c:1285-1318). Every expression is computed in Float, in the order of the operations of the C code; there is no contract.

The choice for the curve, with the options of the sieve as the search normalizes them (Definition 2.11), takes these steps:

1. (1)

   the tuning, from -r, -R, -U and -C or the defaults (find_points.c:2569-2575);

2. (2)

   the first estimate, the loop of the tables with its exit, which returns the prime, and the further forbidden divisors (find_points.c:2522-2532);

3. (3)

   the estimate and the keys again, the composite moduli with their entries (add_moduli, Section 6.2) and the sort (find_points.c:2808-2812, find_points.c:2816-2823, find_points.c:2826-2826);

4. (4)

   the first stage, the value of -n or as many as its rule wants, and the second, the value of -N or the offset, each taking candidates in their order (find_points.c:2490-2508, find_points.c:2843-2846, find_points.c:2864-2871);

5. (5)

   the third stage, up to the value of -P more or while each prime pays for itself, looking at further primes, with the exit, when no prime left pays (find_points.c:2973-2975, find_points.c:3009-3016);

6. (6)

   the end: the third stage and the reserve sorted by density from \(s_2\) on, the entries of all the candidates, their reciprocals and the store with the tables of rows of every entry (find_points.c:3024-3034).

The result holds the cut points \(s_1 \le s_2 \le s_3\), the ends of the three stages, the number of primes looked at and the estimates of the run (ratpoints.h:395-397), with the sieve entries of all the moduli, the reserve included, their reciprocals, the forbidden divisors, the store of the tables of rows and the switch of the checked loop.

The steps of a shape form segments (find_points.c:3812-3837): the \(k\) of the squares \(k^2\), for each divisor \(s\) of the divisor shape the \(k\) of \(s k^2\), both within \([b_{\mathrm{low}}, b_{\mathrm{high}}]\), or the words of \(64\) denominators, or the denominators. The blocks have length \(\lfloor \mathrm{steps}/1024 \rfloor + 1\), at least \(16\), or the length that the build fixes (find_points.c:3838-3842), and cut each segment into consecutive pieces (find_points.c:3843-3850). A decision of the correction is the first block that it is for, with the ends \(s_2\) and \(s_3\) from that block on; the decision in force for block \(i\) is the last whose first block is at most \(i\) (find_points.c:3908-3910). Block \(i\) (find_points.c:3889-3898) hands each denominator of its steps that passes the tests of the shape to the sieve of one denominator, with the sieve entries cut by the decision in force into the first two stages, the first ending at \(s_1\), and the third; it returns when the callback stops the search, and reports its counters with its decision.

The counters of the run, the sums of the counters of the blocks folded (Definition 9.1), those from the extracted numerators on restarted when a block sifted with another \(s_2\) is folded (find_points.c:1363-1367). The correction (find_points.c:1383-1388), when the run has swept enough words, sets the next one at twice the words swept and computes the rates, the walk of \(s_2\) under -A 2 or more and the end of the third stage, every double in the order of the C code. The fold of block \(j\) (find_points.c:4114-4127) adds its counters to the state of the correction and appends a decision for the blocks from \(j + \mathrm{adaptLag} + 1\) on when the correction changes an end. The run starts from the decision of the choice for block \(0\), sifts each block with the decisions made before it and folds its report, returns after the block in which the callback stopped the search, and gives the ends \(s_2\) and \(s_3\) of the last block folded, the moduli used (find_points.c:5152-5160).