Following this on page 12, I understand the first steps of the general number field sieve (GNFS) algorithm for factoring as follows:
Step 1:
Let
$$N = 77$$
and choose
$$m = 4$$
Then
$$N=77 = 1(4^3) + 0(4^2) + 3(4^1) + 1(4^0)$$
so
$$f = x^3 + 3x + 1$$
Let $\alpha$ be any root of this equation, ie. $f(\alpha) = 0$.
Step 2:
Choose a set of small prime exponents basis
$$p = \{2,3,5,7\}$$
and compute pairs of integers $(i, p)$ where $f(i) = 0 \mod{p}$:
$$\{(2,3),(1,5),(2,5),(4,7)\}$$
Further choose a few prime numbers not already previously included in $p$:
$$q = \{11,13\}$$
and compute pairs of integers $(i, q)$ where $f(i) = 0 \mod{q}$:
$$\{(4,11),(11,13)\}$$
I am having trouble sieving this in order to get the smooth pair results next, for instance:
$$smoothpair \rightarrow (-10,1)$$
I can verify a smooth number on the integer prime exponents basis
$$ a + bm = -10 + 1(4) = -6 = -2^1 3^1$$
but I don't understand what it means to be smooth number $a+b\alpha$ over the factor base $\{(2,3),(1,5),(2,5),(4,7)\}$?
So in summary, the question is what needs to be calculated to verify whether
$$-10 + 1(\alpha)$$ is a smooth number over the factor base $\{(2,3),(1,5),(2,5),(4,7)\}$?
Edit: there is a comment by @KevinJohnson here:
The condition that there exist some pair $(r,p)$ for which
$$a + br \mod{p} = 0$$ seems to be always satisfied for $(a,b)$ to be flagged smooth over the factor base$(r,p)$:
Randomly constructed integer pairs set $(a,b)$ generally never satisfy this condition 100/100:
Step 3 may been completed according to [this] (page 14):
where the formulas are
$$N_1 = a - bm$$
$$N_2 = b^3 - f(\frac{a}{b})$$
and $QC$ are quadratic residue flags computed very similarly to the Legendre symbol (explained in ref).
Step 4:
Construct matrix M, with each row with entries cycled modulo $2$ as follows:
$$\begin{bmatrix} sign_{N_1} & 2^a & 3^b & 5^c & 7^d & 3^e & 5^f & 5^g & 7^h & QC_1 & QC_2\end{bmatrix}^T$$
For instance the first row becomes
$$\begin{bmatrix}1 & 1&0&0&1&1&0&0&1&1&1 \end{bmatrix}^T$$
$N_2$ composition in the diagram is ambiguous since there are actually $2$ different entries of base $5$ in the factor base which have been combined under the table:
It can be easily verified that the 3 solutions to
$$MX = 0$$
are indeed (working in modulo $2$):
Step 5:
$$X_1 = \begin{bmatrix} 1&1&1&0&0&0&1&0&0&0&0&0 \end{bmatrix}$$
implies
the solution pairs set
$$\{(-10,1),(-4,1),(-3,1),(-1,2)\}$$
Thus since $m=4$,
$$LHS = (-10 - 1(4))(-4-1(4))(-3-1(4))(-1-2(4)) = 7056$$
$$\sqrt{LHS} = 84$$
and by residue of polynomial long division
$$RHS = (-10 - 1(x))(-4-1(x))(-3-1(x))(-1-2(x)) mod {f(x)} = 175 x^2 + 215x + 85$$
It can be verified by reverse computation that the polynomial square root
$$\sqrt{RHS} \mod{(x^3+3x+1)} = -3x^2+14x-1 $$
Substituting $x=m$,
$$\sqrt{RHS} =7 \mod{(x^3+3x+1)}$$
Finally,
$$gcd(\sqrt{LHS}+\sqrt{RHS}, 77) = gcd(84+7,7) = gcd(91,7) = 7$$
is a factor of $N=77$.
Alternative numerical factor base calculation:
giving the modulo-2 matrix
which has a solution for example:
in which the included products are of $(a,b)$ pairs as follows:
which gives an integer square root on the LHS:
and a polynomial on the RHS (in ascending powers or $x^i$):
whose polynomial root modulo $1 + 3x + 0x^2 + x^3$ is:
which when evaluated at $m=4$ gives:
Finally,
$$LHS+RHS = 504+196=700$$
so
$$gcd(700,N) = gcd(700,77) = 7$$
is a factor of N.