Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

I am writing a document in which I needed to include the description of the Number Field Sieve (NFS) algorithm as mentioned in the book by Crandall and Pomerance. The algorithm's pseudo code is lengthy enough to fill an A4 page, and I am facing the following two problems:

  1. The white spaces around the algorithm do not seem to be properly distributed; causing the algorithm to get chopped, instead of naturally proceeding on the next page, meanwhile covering the page number!
  2. The arrangement of the contents in previous pages is altered in such an unexpected way; a blank page is left, the sections/subsections look improperly spaced (scattered).

    \usepackage{amssymb}        % for some mathematical symbols
    \usepackage[format=hang, font=small, labelfont=bf]{caption} % makes the table caption in bold
    \usepackage{mathtools}      % for cieling function paranthesis
    \usepackage{float}          % for fixing the position of the tables and figures
    \usepackage[ruled, vlined, algosection, norelsize]{algorithm2e} % The algorithms writing 
    \SetAlFnt{\sf} % Set the algorithms font style to sans serif
    \caption{Number Field Sieve \label{alg:NFS}}
    \SetKwBlock{TheSieve}{The Sieve}{}
    \SetKwBlock{TheMatrix}{The Matrix}{}
    \SetKwBlock{LinearAlgebra}{Linear Algebra}{}
    \SetKwBlock{SquareRoots}{Square Roots}{}
    \SetAlFnt{\small \sf}
    \KwIn{An odd composite number $N$ that is not a power.}
    \KwOut{A nontrivial factorization of $N$}
    \nl \Setup
            $d = \left \lfloor 3 \left(\frac{\ln N}{\ln \ln N} \right)^{\frac{1}{3}} \right \rfloor$ \tcp*[r]{This $d$ has $d^{2d^2} < N$.}
            $B = \left \lfloor \exp((\frac{8}{9})^{1/3} (\ln N)^{1/3} (\ln \ln N)^{2/3}) \right \rfloor$ \tcp*[r]{Note that both $d$ and $B$ can be tuned to taste.}
            $m = \lfloor N^{1/d} \rfloor$\;
            Write $N$ in base $m$: $N = m^d + c_{d-1}m^{d-1} + \ldots + c_0$\;
            $f(x) = x^d + c_{d-1}x^{d-1} + \ldots + c_0$ \tcp*[r]{Establish the polynomial $f$.}
            Attempt to factor $f(x)$ into irreducible polynomials in $\mathbb{Z}[x]$ using the factoring algorithm in \cite{Lenstra et al. 1982} or a variant such as \cite{Cohen 2000}(p. 139)\;
            If $f(x)$ has the nontrivial factorization $g(x)h(x)$, return the (also nontrivial) factorization $N = g(m)h(m)$\;
            $F(x,y) = x^d + c_{d-1}x^{d-1}y + \ldots + c_0y^d$ \tcp*[r]{Establish the polynomial $F$.}
            $G(x, y) = x - my$\;
            \For {$(\text{prime } p \leq B)$}
                    compute the set $R(p) = \{ r \in [0, p-1]: f(r) \equiv 0 \pmod p \}$\;
            $k =\lfloor 3\lg N \rfloor$\;
            Compute the first $k$ primes $q_1, \ldots, q_k > B$ such that $R(q_j)$ contains some element $s_j$ with
            $f'(x_j) \not \equiv 0 \pmod {q_j}$ storing the $k$ pairs $(q_j, s_j)$\;
            $B' = \sum_{p \leq B}\#R(p)$\;
            $V = 1 + \pi(B) + B' + k$\;
            $M = B$\;
    \nl \TheSieve
            Use a sieve to find a set $\mathcal{S}'$ of coprime integer pairs $(a, b)$ with $0 < |a|, b \leq M$, and $F(a, b)G(a, b)$ being $B$-smooth, until $\#\mathcal{S}' > V$, or failing this, increase $M$ and try again, or goto      \textrm{\bf Setup} and increase $B$\;
    \nl \TheMatrix
            \tcp*[f]{We shall build a $\#\mathcal{S}' \times V$ binary matrix, one row per $(a, b)$ pair.}
            \tcp*[f]{We shall compute $\vec{v}(a - b\alpha)$, the binary exponent vector for $a - b\alpha$ having $V$ bits (coordinates) as follows:}\\
            Set the first bit of $\vec{v}$ to $1$ if $G(a, b) < 0$, else set this bit to 0\;
            \tcp*[f]{The next $\pi(B)$ bits depend on the primes $p \leq B$: Define $p^\gamma$ as the power of $p$ in the prime factorization of $|G(a, b)|$.}\\
            Set the bit for $p$ to $1$ if $\gamma$ is odd, else set this bit to 0\;
            \tcp*[f]{The next $B'$ bits are to correspond to the pairs $p, r$ where $p$ is a prime not exceeding $B$ and $r \in R(p)$.}\\
            Set the bit for $p, r$ to $1$ if $v_{p, r}(a - b\alpha)$ is odd, else set it to 0\;
            \tcp*[f]{Next, the last $k$ bits correspond to the pairs $q_j, s_j$.}\\
            Set the bit for $q_j, s_j$ to $1$ if $\left( \frac{a - bs_j}{q_j} \right)$ is $-1$, else set it to 0\;
            Install the exponent vector $\vec{v}(a - b\alpha)$ as the next row of the matrix\;
    \nl \LinearAlgebra
            By some method of linear algebra, find a nonempty subset $\mathcal{S}$ of $\mathcal{S}'$ such that
            $\sum_{(a, b) \in \mathcal{S}} \vec{v}(a - b\alpha)$ is the $0$-vector $(\bmod{2})$\;
    \nl \SquareRoots
            Use the known prime factorization of the integer square $\prod_{(a, b) \in \mathcal{S}}(a - bm)$ to find a residue $v \mod n$ with $\prod_{(a, b) \in \mathcal{S}}(a - bm) \equiv v^2 \pmod{N}$\;
            By the suitable method to find the square root $\gamma$ in $\mathbb{Z}[\alpha]$ of
            $f'(\alpha)^2 \prod_{(a, b) \in \mathcal{S}}(a - b\alpha)$, and, via a simple replacement $\alpha \to m$, compute
            $u = \phi(\gamma)\pmod{N}$\;
    \nl \Factorization
            return $\gcd((u - f'(m)v), n)$\;
share|improve this question
All of what you're describing is as a result of using the [H] float specifier. Unfortunately, all of this cannot be fixed by merely removing it... –  Werner Nov 28 '13 at 21:20
However, not forcing position (by removing the [H] float specifier), introduces further issues, like putting the algorithm at the end of the chapter (completely dropping the value of the section containing it)! –  Abdullah Heyari Nov 28 '13 at 21:29
You can set a \FloatBarrier to change this (or other features of the placeins package) –  masu Nov 29 '13 at 7:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.