Please help me to understand the math signs in Self Initializing Quadratic Sieve polynomial step

Question

In order for me to revise my implementation of the Multiple Polynomial Quadratic Sieve into the Self-Initializing Quadratic Sieve, I need help with some math symbols.

I am trying to follow Scott Contini's on Self Initializing Quadratic Sieve, where he gives an excellent summary of the required steps in the image below (Fig. 2.3). Please help me to understand all the math symbols there.

1. What is $tmem_p$?
2. What is the "x" sign?
3. What is the "/" sign?
4. What is "ainv"?
5. What is the "#" sign?
6. What is the "||" sign?
7. What is $soln1_p$?

---

Answer 1

Given that you've implemented the MPQS algorithm, I'll try to reply concisely to each of the "What is ... ?" items. Some of these indeed are "math signs", but others are more in the nature of variable names, etc.

As time permits I hope to come back and tie my replies in operational motivations, namely how SIQS revises the initialization step of MPQS.

1. What is $\mathit{tmem}_p$ ?
2. What is the "$\times$" sign ?
3. What is the "/" sign ?

This notation appears in the cited "Figure 2.3: summary of siqs initialization stages" on page 14 of Contini's Masters Thesis. It is the first statement within a loop over $\ell = 1 \text{ to } s$:

Compute $\gamma = \mathit{tmem}_p \times (a/q_\ell)^{-1} \bmod q_\ell$.

A clearer statement is found in the Prime Wiki for Self-initializing quadratic sieve, under the section "Generating the first polynomial".

The first term $\mathit{tmem}_p$ is an array previously filled with entries for each prime $p$ in the factor base. Referring back to "Figure 2.2: summary of mpqs algorithm" (on page 13), we find there (under Compute startup data) that for each prime $p$ we store a modular square root of $N \bmod p$, i.e. a solution $t$ of:

$$ t^2 \equiv N \bmod p $$

where $N$ is the composite (not a pure power) integer to be factored. Note that in this scheme of sieving we will only be interested in a factor base whose primes $p$ have $N$ as a quadratic residue. The setup entries $\mathit{tmem}_p$ are "realizations" of that property.

But the notation is at best confusing and arguably a slight typo. The array expression $\mathit{tmem}_p$ needs an index (or offset) to denote which modular square root of $N$ is intended. From the fact that we "compute" $\bmod q_\ell$, we can deduce that the $\mathit{tmem}_p$ entry for prime $q_\ell$ is needed in this expression.

Next the sign "$\times$" is just multiplication, here modular multiplication $\bmod q_\ell$.

Also the sign "/" can be understood as ordinary integer division, noting the caveat: here $a$ is product over some primes that include $q_\ell$. So the integer division is exact, and the quotient $(a/q_\ell)$ might be as well provided by multiplying together all those primes except omitting the particular $q_\ell$ designated by loop index $\ell$ (going from $1$ to $s$, so whatever step of the loop we are at).

4. What is "ainv"?

Actually this is an array $\mathit{ainv}_p$ in the next block of the algorithm. For each factor base prime $p$ that does not divide $a$ (i.e. those factor base primes which were not multiplied together to get $a$), we compute the multiplicative inverse of $a \bmod p$:

Compute $\mathit{ainv}_p = a^{-1} \bmod p$

The computation of the multiplicative inverse of $a$ with respect to the coprime modulus $p$ is a familiar division algorithm exercise.

5. What is the "#" sign ?

When this appears in the next section Initialization stage for the next $2^{s-1}-1$ polynomials, the pound sign is merely an abbreviation for "numbered". That is, that opening parenthetical sentence should be understood to say:

(Assume we just sieved polynomial numbered $i$, so we are initializing polynomial numbered $(i+1)$, $1\le i \le 2^{s-1} - 1$)

In other words this is more of a shorthand for proceeding to next numbered polynomial rather than a mathematical notation of some kind. The underlying "numbering" of the polynomials is mathematically related to a Gray code, for which see Appendix C of Contini's paper.

6. What is the "$||$" sign?

This is perhaps the least standard of notations employed here. It appears as:

Let $\nu$ be the integer satisfying $2^\nu || 2i$.

In other words this means $\nu$ is the highest power of $2$ which divides $2i$.

7. What is $\mathit{soln}1_p$ ?

This notation $\mathit{soln}1_p$ is a variable name for an array of values, one entry for each factor base prime $p$ that does not divide $a$. Its values get defined (as also $\mathit{soln}2_p$ will) for the first polynomial and subsequently updated serially for the next polynomials.