LARGE SMOOTH TWINS FROM SHORT LATTICE VECTORS

ERIK MULDER, BRUNO STERNER, AND WESSEL VAN WOERDEN

ABSTRACT. Finding the largest pair of consecutive B-smooth integers for a fixed value of B, also called a B-smooth twin, is computationally challenging. It has only been provably done for $B \le 100$ and heuristically for $100 < B \le 113$. We improve this by detailing a new algorithm to find such smooth twins. The core idea is to solve the shortest vector problem (SVP) in a well-constructed lattice. Using a heuristic about smooth numbers in short intervals, we give an estimate of the size of the largest smooth twin for a given B. We are able to significantly increase B and notably report the heuristically largest twin with $B = 751$, which has 196 bits. By slightly modifying the lattice, we are able to find even larger twins, but the resulting smoothness bound will not always be optimal. This notably includes a 213-bit twin with $B = 997$, which is the largest twin found in this work.

> "Such pairs lead to sets of "nearly" dependent logarithms of primes. For instance the number $K = \log(63927525376) - \log(63927525375) = 13\log(2) - 3\log(3) - 3\log(5) - 7\log(7) + 4\log(11) + \log(13) - \log(23) + \log(41)$, which cannot be zero because of the unique factorisation theorem, is, however, less than $1.56427 \cdot 10^{-11}$."

- D.H. Lehmer [25]

1. INTRODUCTION

In 1991, during what can be considered the golden age of integer factorisation, Schnorr [32] proposed a factoring method<fnref n="1" /> based on solving the closest vector problem in the so-called *prime number lattice*. While his strategy looked promising, the growing and necessary lattice dimension when you increase the input integer provides an obstruction to the feasibility of the algorithm. As a result, it did not compete with other factoring algorithms such as the number field sieve [26].

Many modern integer factorisation techniques rely heavily on the use of smooth integers. These are integers with only small prime factors. We quantify this properly to say that an integer *n* is *B*-smooth if $p \mid n \Rightarrow p \le B$ for all primes *p*. We refer to Granville's survey [24] for the factoring relevance of these integers and beyond.

Recently the problem of finding pairs of consecutive smooth integers, which we call smooth twins, has attracted attention. The primary relevance of these smooth twins comes from isogeny-based cryptography. Certain cryptosystems, including the original versions of SQIsign [22, 23] and a variant of POKÉ [7, 15], either work with large smooth twins whose sum is prime or a small variant of this.

We formalise the definition of *B*-smooth twins.

**Definition 1.1.** We call a pair of consecutive integers $(r, r+1)$ a *B*-smooth twin if their product, $r \cdot (r+1)$, is *B*-smooth and drop *B* from this definition when it is polynomial in $\log(r)$. When *B* is included we call it the *smoothness bound*. We call a *B*-smooth twin *strictly *B*-smooth if it is not $(B-1)$-smooth.

<footnote n="2020">2020 Mathematics Subject Classification. Primary.</footnote>

<footnote n="1">¹Which was independently analysed by Adleman [2]</footnote>
It is known that the set of B-smooth twins is finite [36]. By solving exponentially many Pell equations in B one can find all such twins. This has been done for $B = 100$ [28] and heuristically for $B = 113$ [16] – the largest of these twins have 64 and 75 bits (respectively). We give terminology for the largest B-smooth twin.

**Definition 1.2.** We call the largest B-smooth twin an optimal twin. In the other direction, for an input bit size $b$, the optimal smoothness bound is the smallest smoothness bound $B$ such that there is a B-smooth twin $(r, r+1)$ with $r > 2^{b-1}$.

For cryptographic relevance one requires 256-bit smooth twins<fnref n="2" />. We call these cryptographic smooth twins. The optimal smoothness bound for such a twin is $B \approx 1250$. So finding them from solving (at least a large proportion of) Pell equations is far beyond computational reach.

**Contributions.** In this work we revisit Schnorr’s factoring idea and repurpose it to find large smooth twins. We observe that the shortest vectors in the prime number lattice often correspond to smooth twins. So using state-of-the-art SVP algorithms [5, 21, 38] we find short vectors in the lattice and see whether they correspond to smooth twins. By parametrising the lattice correctly, one can search for smooth twins of a particular size including the optimal twins. With the current state of SVP algorithms, we can find heuristically (close-to-)optimal twins with much larger smoothness bounds. For instance, we found the following 196-bit 751-smooth twin

$$ \begin{array}{l} r = 7^7 \cdot 11 \cdot 17 \cdot 29 \cdot 47 \cdot 59 \cdot 67 \cdot 83^2 \cdot 89 \cdot 151^3 \cdot 163 \cdot 173 \cdot 271 \cdot 347 \cdot 461 \\ \qquad \cdot 491 \cdot 547 \cdot 587 \cdot 619 \cdot 661 \cdot 683 \cdot 701, \text{ and} \\[1.5em] (1) \qquad r + 1 = 2 \cdot 3^9 \cdot 13^2 \cdot 19 \cdot 31 \cdot 41 \cdot 71 \cdot 73 \cdot 97 \cdot 157^2 \cdot 181^3 \cdot 191 \cdot 227 \cdot 241 \cdot 293 \\ \qquad \cdot 307^3 \cdot 337 \cdot 557 \cdot 617 \cdot 727 \cdot 751 \end{array} $$

which we believe is optimal. As mentioned earlier, the only known provable optimal twins have $B \le 100$. For $100 < B \le 113$ optimal twins are only known heuristically.

In order to convince the reader that this 751-smooth twin is likely the optimal twin, we develop theoretical bounds and estimates for optimal twins based on some heuristics. In particular, the standout result is the following.

**Theorem 1.3.** *Assuming Heuristic 3.1, as $B \to \infty$ we have the following asymptotic for optimal B-smooth twins $(r, r+1)$:*

$$r \sim e^{2e\sqrt{B}}.$$

This result explains the asymptotic behaviour of optimal twins, but for concrete and small $B$ this estimate deviates from the precise size. For this regime one can use numerical techniques to get a better approximation for optimal twins.

By introducing some trade-offs in the lattice, one can find even larger twins. One cannot expect the resulting twins to be optimal using these trade-offs. For instance

<footnote n="2">²Smaller twins of at least 240 bits could also be used to give conservative parameters.</footnote>
we found the following 213-bit 997-smooth twin

$$ \begin{array}{l} r = 19^2 \cdot 41 \cdot 43^2 \cdot 53 \cdot 59^2 \cdot 73^2 \cdot 83 \cdot 173 \cdot 227 \cdot 241 \cdot 281 \cdot 337 \cdot 397^2 \cdot 433 \\ \qquad \cdot 541 \cdot 577 \cdot 593 \cdot 787 \cdot 821 \cdot 839 \cdot 857^2 \cdot 967, \text{ and} \\[1.5em] (2) \qquad r + 1 = 2^2 \cdot 3 \cdot 5^2 \cdot 13^3 \cdot 23 \cdot 37 \cdot 47 \cdot 79 \cdot 107 \cdot 127 \cdot 131 \cdot 151 \cdot 157 \cdot 167 \cdot 179 \\ \qquad \cdot 181^2 \cdot 193 \cdot 223 \cdot 283 \cdot 317 \cdot 367 \cdot 379 \cdot 601 \cdot 709^2 \cdot 743 \cdot 941 \cdot 997 \end{array} $$

and, with the estimates that will be developed in Section 3, we suspect that the optimal 997-smooth twin should have approximately 227 bits. We discuss the challenges to find larger smooth twins relevant for cryptography.

For some fixed values of $B$, we attempt to find all $B$-smooth twins from our approach by expanding a known set of smooth twins [9]. In particular we conjecture to have the complete set of 200-smooth twins. The only known way to verify this is to comprehensively solve $2^{46}$ Pell equations which is at present computationally challenging.

In addition, we put our algorithm in a cryptographic context. While we cannot find cryptographic smooth twins, we are still able to use smaller twins and boost these to cryptographic parameters for the original version of the SQIsign signature scheme [22]. We get parameters with smaller smoothness bounds than those in the submission to NIST's call for additional post-quantum signatures [11] and with a theoretical decrease of 19.85% for the signing time, these new parameters are a competitive alternative that could be considered for future use.

**Notation.** $B$ will be a smoothness bound, $P_B := \{2,3,\dots,q\} = \{p \le B\}$ will be the set of primes up to $B$ with cardinality $\pi(B) = \#P_B$ and $(r, r+1)$ will be a $B$-smooth twin. We will denote $\log(\cdot)$ and $\log_2(\cdot)$ for the natural and base-2 logarithm respectively. We denote $\text{val}_p(y)$ for the valuation of $y \in \mathbb{Q}$ at $p$. For two functions $f,g: \mathbb{N} \to \mathbb{R}$ we write $f(n) = O(g(n))$ if there is some $C > 0$ and $N \in \mathbb{N}$ such that for all $n \ge N$ we have $|f(n)| \le C|g(n)|$. We write $f(n) = \Omega(g(n))$ if $g(n) = O(f(n))$; write $f(n) = o(g(n))$ if $f(n)/g(n) \to 0$ as $n \to \infty$; and also write $f(n) \sim g(n)$ when $f(n)/g(n) \to 1$ as $n \to \infty$.

**Acknowledgements.** The second author was supported by the HYPERFORM consortium funded through Bpifrance and l'Agence nationale de la recherche through a Plan France 2030 grant (ANR-22-PETQ-0008 PQ-TLS). Part of this work was executed while the third author was employed by IMB at Université de Bordeaux under the CHARM ANR-NSF grant (ANR-21-CE94-0003). Experiments presented in this paper were carried out using the PlaFRIM experimental testbed, supported by Inria, CNRS (LABRI and IMB), Université de Bordeaux, Bordeaux INP and Conseil Régional d'Aquitaine $^3$.

## 2. EXISTING METHODS FOR FINDING SMOOTH TWINS

We give a short summary of the algorithms that exist to find smooth twins.

### 2.1. Constructive Methods.
The methods presented here attempt to find all or almost all $B$-smooth twins for a fixed and small smoothness bound $B$.

<footnote>$^3$See https://www.plafrim.fr.</footnote>
**Solving Pell equations.** Let $x = 2r + 1$ so that $x^2 - 1 = 4r(r + 1)$ is B-smooth. Decompose this into its squarefree part, $D$, and its square part, $y^2$. Then the pair $(x, y)$ is a solution to the Pell equation $X^2 - DY^2 = 1$. One reverses this to solve all $2^{\pi(B)}$ Pell equations, one for each $D = \prod_{\ell \in P_B} \ell^{e_\ell}$ with $e_\ell \in \{0, 1\}$. Lehmer [25] gives provable conditions on these equations to ensure all B-smooth twins are found.

This is computationally infeasible for large $B$ – the complexity to solve these equations is at least $O(2^{\pi(B)+o(\pi(B))})$. This ignores the fact that the fundamental solution is (in the worst case) doubly exponential in $B$. Finding such solutions would add another exponential to this complexity<fnref n="4" />. In practice one can adopt an early abort strategy that only considers solutions up to some reasonable bound. If this bound is exponential in $B$, then processing each discriminant becomes polynomial in $B$ and the total complexity becomes $O(2^{\pi(B)+o(\pi(B))})$. With this, one could heuristically get all B-smooth twins (as done for $B = 113$ [16]).

**Remark 1.** The authors of [10] found cryptographic smooth twins in this manner. Instead of solving all Pell equations they only solved equations with a small number of prime factors in $D$. This requires choosing a much larger $B$ than the optimal.

**Conrey-Holmstrom-McLaughlin (CHM).** This algorithm [12] recursively builds an increasing chain of B-smooth twins $S^{(0)} = \{1, \dots, B-1\} \subseteq S^{(1)} \subseteq \dots \subseteq S^{(i)} \subseteq S^{(i+1)} \subseteq \dots \subseteq S^{(n-1)} = S^{(n)}$ until no more twins are found (which is ensured by Størmer’s [36] result). For each $r, s \in S^{(i)}$ with $r < s$ compute

$$ \frac{t}{t'} = \frac{r}{r+1} \cdot \frac{s+1}{s}, $$

where $\gcd(t, t') = 1$, and include $t$ in the next set $S^{(i+1)}$ when $t' = t + 1$. This produces a B-smooth twin $(t, t+1)$ and shows the correctness of the recursion.

This procedure produces a large but incomplete set of B-smooth twins. It is conjectured that the proportion of B-smooth twins not found with CHM is $o(1)$ as $B \to \infty$. The experiments in [9] report the results with $B = 547$. The largest twin found in that run has 122 bits which we will see later is far from optimal.

## 2.2. Probabilistic Methods.
The methods described here search for smooth twins of a fixed target size including cryptographic smooth twins. We give a brief account here and refer to [17, 35] for more concrete details.

**Searching using polynomial pairs.** The state-of-the-art here is to work with polynomial pairs $f, g \in \mathbb{Z}[x]$ with $g - f \equiv C \in \mathbb{Z}_{>0}$. One carefully evaluates these polynomials to get a smooth twin: $(r, r+1) = (f(m)/C, g(m)/C)$. This strategy is most effective when $\deg(f)$ is not too large and $f, g$ admit nice factorisations. This includes the circumstance when $f, g$ are a product of linear factors [17]; as well as those with some repeated and slightly larger degree factors [16, 35].

For smooth twins in the bit range (240, 256] the smallest $B$ reported with these polynomials is $B = 17341$. For those with a prime sum, the smallest is $B = 32039$.

<footnote n="4">⁴We refer to [25, §6] and [28] for some discussion on getting around this.</footnote>
### 3. SMOOTHNESS HEURISTICS

The Dickman-De Bruijn [19, 18] function is the continuously differentiable function $\rho: [0, \infty) \to [0, 1]$ that satisfies the following difference differential equation

$$ (3) \qquad \begin{aligned} \rho(u) &= 1, && (0 \le u \le 1); \\ u\rho'(u) &= -\rho(u-1), && (u > 1). \end{aligned} $$

Other than $\rho(u) = 1 - \log(u)$ for $1 < u \le 2$, there is no closed form for $\rho(u)$ in terms of elementary functions for arbitrary $u > 1$. A simple approximation of this function is $\rho(u) \approx u^{-u}$ and a better one is given by $\rho(u) \approx e^u(u \log(u))^{-u}$. These approximations are derived from the asymptotic expression [24, §3.9]

$$ (4) \qquad \rho(u) = \left( \frac{e + o(1)}{u \log(u)} \right)^u, $$

as well as a more precise statement due to De Bruijn [18, Eqn (1.8)]. From a computational perspective, numerical methods [37] exist for evaluating this function which are built into many popular computer algebra packages.

This function is related to the distribution of smooth integers at an asymptotic level. More precisely, if $\Psi(N, B)$ denotes the number of B-smooth integers $m \le N$, then for a fixed $u > 0$ and as $N \to \infty$ we have [19, 18]

$$ \Psi(N, N^{1/u}) \sim \rho(u)N. $$

While this expression is asymptotic, experimentally $\rho(u)$ is a good estimate for the probability that an integer of size $N$ is $N^{1/u}$-smooth.

Throughout this article we are interested in smooth integers with small smoothness bounds. In this scenario, for $A > 1$ and as $N \to \infty$, it is known that

$$ \Psi(N, \log(N)^A) = N^{1-1/A+o(1)}. $$

This is a special case of a result due to Rankin which is detailed in [24, §3.10].

3.1. **Heuristics on the optimal twin.** It is believed that the smoothness property in very short intervals is mutually independent. A more formal and general statement is conjectured which has only been proven in a small range [29]. This fact has been utilised in practice [17, 35] owing to its accuracy for concrete instances. This would imply that the probability that two close integers of size $N$ are $N^{1/u}$-smooth is $\rho(u)^2$. Therefore, for large enough $N$, the number of $N^{1/u}$-smooth twins in the interval $[N/2, 3N/2]$ is heuristically roughly $\rho(u)^2N$. This means that if $\rho(u)^2N = 1$, then we expect roughly one $N^{1/u}$-smooth twin of size $N$, and not many greater than $N$. This gives us the following heuristic on the optimal B-smooth twin, which we generalise to more than two consecutive smooth numbers.

**Heuristic 3.1.** Fix an integer $m \ge 2$ and a sequence of small positive integers $0 = a_0 < a_1 < \dots < a_{m-1} < m^{1+O(1)}$. As $B \to \infty$, the largest integer $r$ such that $r + a_i$ are all B-smooth satisfies

$$ \rho(u) \sim r^{-1/m} $$

where $u = \log(r)/\log(B)$. For the special case giving B-smooth twins ($m = 2$ and $a_1 = 1$) the above condition is $\rho(u) = 1/\sqrt{r}$.
We get some validity of Theorem 1.3 assuming this heuristic when using the above estimate for $\Psi(N, \log(N))^A$ with $A = 2$ and $N = r$. To make this more precise we need to solve the equation in Heuristic 3.1. For instance, solving $\rho(u) = 1/\sqrt{r}$ using the crude estimate $\rho(u) \approx u^{-u}$ gives $\log(r) \approx \log(B)\sqrt{B}$. This additional factor $\log(B)$, which deviates from our Theorem 1.3, emerges since this approximation deviates quite a bit from its actual value for large $u$. We improve this by replacing the crude estimate with the asymptotic expression in (4).

As a precursor, we need the principal branch of the Lambert W function – the function $W_0: \mathbb{R}_{>0} \to \mathbb{R}_{>0}$ such that for any $x > 0$ and $y = W_0(x) > 0$ we have $ye^y = x$. It is known that $W_0(x) = \log(x) - \log(\log(x)) + o(1)$ as $x \to \infty$ [13]. We need a slight modification of this which is summarised in this short lemma.

**Lemma 3.2.** Consider the function $x \mapsto x \log(x)$ for $x > 1$ (so that $x \log(x) > 0$). Then the principal branch of its inverse is the function $x \mapsto x/W_0(x)$ for $x > 0$.

*Proof.* We start with $y \log(y) = x$ and assume that $x > 0$ and $y > 1$. We express $y$ solely in terms of $x$ by first rewriting this as $(x/y)e^{x/y} = x$ and then obtain $x/y = W_0(x)$. This proves the lemma. $\square$

*Proof of Theorem 1.3.* We start with the equation $\rho(u) = 1/\sqrt{r}$ from Heuristic 3.1. Using the asymptotic expression from (4) and $u = \log(r)/\log(B)$, this can be rearranged to

$$ (5) \qquad u \log(u) = (e + o(1))\sqrt{B}. $$

Using Lemma 3.2 we can express $u$ as

$$ (6) \qquad u = \frac{(e + o(1))\sqrt{B}}{W_0((e + o(1))\sqrt{B})} = \frac{(e + o(1))\sqrt{B}}{1 + \frac{1}{2}\log(B) - \log(1 + \frac{1}{2}\log(B)) + o(1)}. $$

Concluding the proof amounts to looking at $\log(r)/\sqrt{B} = u \log(B)/\sqrt{B}$ and assessing its limit as $B \to \infty$. Before we calculate this, one needs to address the $o(1)$ term in (at least) the numerator of (6) since this is a priori with respect to $u$ and not $B$. It is necessary to show that this is also the case for $B$.

Fortunately this is straightforward to prove. By the right-hand side of (5) we have $u \log(u) \to \infty$ as $B \to \infty$ and, since the map $x \mapsto x \log(x)$ has no poles other than $\infty$, we must have $u \to \infty$ as $B \to \infty$.

So the $o(1)$ in (6) is also with respect to $B$ and one can easily take limits. This gives $u \log(B)/\sqrt{B} \to 2e$ as $B \to \infty$ and proves the Theorem. $\square$

One can mimic this proof of Theorem 1.3 in the more general setting of smooth integers in short intervals. We simply state the result in the following theorem.

**Theorem 3.3 (More generally).** Fix an integer $m \ge 2$ and a sequence of small positive integers $a_0 = 0 < a_1 < \dots < a_{m-1} < m^{1+O(1)}$. Let $r$ be the largest integer such that $r + a_i$ is B-smooth for all $i = 0, \dots, m-1$. Assuming the generalised form of Heuristic 3.1, as $B \to \infty$ we have the asymptotic

$$ r \sim e^{meB^{1/m}}. $$
*Numerical computations for small B.* Theorem 1.3 gives a strong description of the asymptotic behaviour of optimal B-smooth twins. However for concrete and small *B* this is not effective and one needs a more explicit solution to the equation $r\rho(u)^2 = 1$ underlying Heuristic 3.1. One cannot solve this equation exactly and so we resort to numerical techniques to approximate the solution.

One can start with an initial guess for $r$, such as the one given in Theorem 1.3, and use a root-finding algorithm to iteratively get a better approximation for $r$. The easiest of such algorithms is perhaps the bisection method. Other methods include Newton's numerical method (and exploit the differentiable condition from (3)). Here one would expect a faster rate of convergence compared to the bisection method. But, in practice we found that the bisection method was sufficiently fast for the values of $B$ we were interested in.

<figure><img src="image_1.png" /><figcaption>**Figure 1.** Comparing the numerical estimates for optimal *B*-smooth twins (marked with a blue plus) against the provable and heuristic optimal twins with $B \le 113$. The red dots mark the sizes of the largest *strictly* *B*-smooth twins, while the orange line indicates the largest twin up to smoothness bound *B*.</figcaption></figure>

For small $B \le 113$ these numerical estimates for optimal twins correlate well to actual optimal twins found with by solving Pell equations, see Figure 1. As a result we estimate the size of optimal twins for larger $B$. Table 1 reports these computations for various $B \le 10000$. As we shall see in Section 7 the approximations for the smaller $B$ in this table also correlate well with twins found in this work.

4. LATTICE THEORY

A lattice $\mathcal{L}$ is a discrete subgroup of the Euclidean space $\mathbb{R}^m$. Equivalently, any lattice $\mathcal{L}$ can be described by a basis $\mathbf{B} \in \mathbb{R}^{m \times n}$ with $\mathbb{R}$-linearly independent
<table><caption>**Table 1.** Heuristic size of optimal twins for various smoothness bounds $B$, i.e. approximate solutions to $\rho(u) = 1/\sqrt{r}$.</caption><thead><tr><th>Smoothness bound <i>B</i></th><th>Approximate log<sub>2</sub>(<i>r</i>)</th><th>Smoothness bound <i>B</i></th><th>Approximate log<sub>2</sub>(<i>r</i>)</th></tr></thead><tbody><tr><td>200</td><td>91.138890</td><td>1500</td><td>282.426575</td></tr><tr><td>500</td><td>154.417132</td><td>2000</td><td>329.581941</td></tr><tr><td>750</td><td>193.534196</td><td>2500</td><td>371.202628</td></tr><tr><td>1000</td><td>226.657489</td><td>3000</td><td>408.877910</td></tr><tr><td>1100</td><td>238.750073</td><td>4500</td><td>506.210979</td></tr><tr><td>1250</td><td>255.920233</td><td>10000</td><td>767.101783</td></tr></tbody></table>

columns $b_1, \dots, b_n$ such that

$$ \mathcal{L} = \mathcal{L}(\mathbf{B}) := \left\{ \sum_{i=1}^{n} x_i b_i : x_i \in \mathbb{Z} \right\}. $$

We denote rk($\mathcal{L}$) = $n$ for the rank of the lattice, which coincides with the dimension of its $\mathbb{R}$-linear span.

The discrete nature of a lattice allows us to define some geometric properties. For a lattice $\mathcal{L}$ the minimal distance between any two distinct lattice points is called its first minimum, denoted by $\lambda_1(\mathcal{L})$. Equivalently, it equals the length of the shortest non-zero vector:

$$ \lambda_1(\mathcal{L}) := \min_{\mathbf{v} \in \mathcal{L} \setminus \{\mathbf{0}\}} \|\mathbf{v}\|. $$

Next, we have the (co)volume vol($\mathcal{L}$) of a lattice which equals the volume of the quotient space span$_{\mathbb{R}}(\mathcal{L})/\mathcal{L}$. For any basis $\mathbf{B}$ of $\mathcal{L}$ we have:

$$ \mathrm{vol}(\mathcal{L}) := \mathrm{vol}(\mathrm{span}_{\mathbb{R}}(\mathcal{L})/\mathcal{L}) = \det(\mathbf{B}^{\top}\mathbf{B})^{1/2}. $$

The volume vol($\mathcal{L}$) of a lattice can be seen as the inverse density of the lattice, i.e., vol($\mathcal{L}$)$^{-1}$ is roughly the number of lattice vectors per unit volume. In a dense enough lattice of rank $n$ there must always be some short non-zero lattice vector, which is quantified by Minkowski's theorem saying that

$$ \lambda_1(\mathcal{L}) \le \frac{2 \mathrm{vol}(\mathcal{L})^{1/n}}{\mathrm{vol}(\mathcal{B}^n)^{1/n}} \approx \sqrt{2n/\pi e} \cdot \mathrm{vol}(\mathcal{L})^{1/n}, $$

where vol($\mathcal{B}^n$) is the volume of a unit ball of dimension $n$. In a typical random lattice$^5$ one can give a more precise estimate of the first minimum. In practice, we usually never have precisely such a random lattice, however, unless they have some special structure, most lattices still satisfy the following simplified heuristic.

**Heuristic 4.1** (Gaussian Heuristic). Let $\mathcal{L}$ be a lattice and let $S \subset \mathrm{span}_{\mathbb{R}}(\mathcal{L})$ be a sufficiently nice body with positive Euclidean volume. Then the expected number of non-zero lattice points in $S$ roughly equals

$$ |\mathcal{L} \cap S \setminus \{0\}| \approx \frac{\mathrm{vol}_{\mathrm{span}(\mathcal{L})}(S)}{\mathrm{vol}(\mathcal{L})}. $$

<footnote>$^5$One can make this precise by considering a finite measure defined on the space of lattices induced by the Haar measure on $SL_n(\mathbb{R})$.</footnote>
In particular, for a lattice of rank n this implies that

$$ \lambda_1(\mathcal{L}) \approx \mathrm{gh}(\mathcal{L}) := \frac{\mathrm{vol}(\mathcal{L})^{1/n}}{\mathrm{vol}(\mathcal{B}^n)^{1/n}} \approx \sqrt{n/2\pi e} \cdot \mathrm{vol}(\mathcal{L})^{1/n}. $$

4.1. **The shortest vector problem (SVP).** One of the main computational lattice problems is that of finding short non-zero lattice vectors. Finding a lattice vector $v \in \mathcal{L}$ of minimal length $\|v\| = \lambda_1(\mathcal{L})$ is known as the shortest vector problem (SVP). While the best provable algorithm for SVP runs in time and space $2^{n+o(n)}$ in the rank $n$ of the lattice [3, 4], heuristic versions can be much better. The fastest heuristic algorithm for SVP runs in time $(3/2)^{n/2+o(n)} \approx 2^{0.292n+o(n)}$ and space $(4/3)^{n/2+o(n)} \approx 2^{0.2075n+o(n)}$ [8]. In practice, these algorithms can solve SVP up to dimensions 150 in reasonable time [5], with record computations stretching up to dimension 200 [21, 38].

The above complexities are for finding an (almost) shortest vector in a typical lattice for which $\lambda_1(\mathcal{L}) \approx \mathrm{gh}(\mathcal{L})$. These seem to be the hardest cases to find a shortest vector both in theory as in practice. The lattice we will consider has some special structure and therefore does not always fall into this regime. For example, when the short vector $v \in \mathcal{L}$ we aim to find is shorter than what the Gaussian Heuristic predicts. Alternatively, even if the lattice satisfies $\lambda_1(\mathcal{L}) \approx \mathrm{gh}(\mathcal{L})$, the short vector $v \in \mathcal{L}$ we aim to find does not always have to be the shortest vector. We consider these two regimes or variants of SVP.

**The case $\|v\| < \mathrm{gh}(\mathcal{L})$.** If $\|v\| = \lambda_1(\mathcal{L}) < \mathrm{gh}(\mathcal{L})$ we call a shortest vector $v \in \mathcal{L}$ **unusually short**. Finding such an unusually short vector $v \in \mathcal{L}$ is typically easier. In particular, such a short vector can be found by running a lattice reduction algorithm such as BKZ [33] which makes polynomially many calls to an exact SVP oracle in dimension $\beta \le n$ and thus heuristically runs in time $2^{0.292\beta+o(n)}$. The dimension $\beta$ depends on the dimension $n$ and the ratio $\mathrm{gh}(\mathcal{L})/\lambda_1(\mathcal{L})$ which is also called the **gap**. The larger the gap, the lower $\beta$ will be relative to $n$.

**The case $\|v\| \ge \mathrm{gh}(\mathcal{L})$.** We consider the case where one wants to find a sufficiently short vector $v \in \mathcal{L}$ for which $\mathrm{gh}(\mathcal{L}) \le \|v\| \le C \cdot \mathrm{gh}(\mathcal{L})$ for some $C \ge 1$. Finding any such short vector is typically easier than finding a shortest vector, again by the use of a lattice reduction algorithm. In fact, in a typical lattice there are according to the Gaussian Heuristic roughly $C^n$ of such vectors. However, in our case we will be interested in finding a specific (or a few specific) vectors among those $C^n$ vectors. Finding a needle in such a haystack will quickly become infeasible, and thus we are typically constrained to quite low values of $C$. The current best heuristic algorithms for SVP naturally compute almost all vectors up to length $\sqrt{4/3} \cdot \mathrm{gh}(\mathcal{L})$ and thus in practice we typically constrain ourselves to $C \le \sqrt{4/3}$ in large dimensions.

**Dimensions for free.** Because the best heuristic algorithms for SVP do not only compute a shortest vector but almost all vectors up to length $\sqrt{4/3} \cdot \mathrm{gh}(\mathcal{L})$, one can try to use this fact if one is only interested in a single shortest vector. Namely, given some short (primitive) lattice vectors $b_1, \dots, b_k \in \mathcal{L}$ one can consider the projected lattice $\pi(\mathcal{L})$ of rank $n-k$ where $\pi$ projects away from these $k$ lattice vectors. For a shortest vector $v \in \mathcal{L}$ its projection $\pi(v)$ might still be shorter than $\sqrt{4/3} \cdot \mathrm{gh}(\pi(\mathcal{L}))$ and thus $\pi(v)$ can be found by running the SVP algorithm on $\pi(\mathcal{L})$. Then $v$ can be recovered by an appropriate lifting. One thus decreases the
rank of the SVP by $k$ dimensions, which for typical lattices can heuristically be picked as $k = \theta(n/\log(n))$ [20]. In practice values of 10 to 35 are typical.

## 5. GENERALISED PRIME NUMBER LATTICE

Here we reintroduce and generalise the prime number lattice that will be the main subject throughout the rest of this work. We remark that other names have been used for the lattice including the “Schnorr-Adleman lattice”.

Let $\alpha, \alpha_i \in \mathbb{R}$, for $i \in \{1, \dots, n\}$, and $P = \{p_i\}_{i=1}^n$ be a finite subset of distinct primes of size $n$. We call the $\alpha_i$'s weights and call $P$ a factor base. We say that a positive integer is $P$-smooth if all its prime divisors are in $P$. Note that for $P = P_B = \{p \le B\}$ this coincides with being $B$-smooth.

**Definition 5.1.** We define the prime number lattice adjoined to $\alpha, \alpha_i$ and a factor base $P$, denoted $\mathcal{L}_{\alpha, \alpha_i, P}$, to be the lattice with the following basis matrix:

$$ B_{\alpha, \alpha_i, P} := \begin{pmatrix} \log(p_1)\alpha & \log(p_2)\alpha & \cdots & \log(p_n)\alpha \\ \alpha_1 & 0 & \cdots & 0 \\ 0 & \alpha_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \alpha_n \end{pmatrix}. $$

When $P = P_B$ we call this lattice the full prime number lattice (or simply the full lattice) with respect to the smoothness bound $B$.

Besides the relevance of this lattice to integer factoring which was alluded to in the introduction, the lattice also plays a role in lattice sphere packings, where it was used to prove the NP-hardness of SVP under randomised reductions [30]. Historically one restricts the weights $\alpha_i$ to be either $\log(p_i)$ or $\sqrt{\log(p_i)}$. We write $\alpha$ and $\alpha_i$ abstractly for the time being and make concrete choices later on.

A vector $B_{\alpha, \alpha_i, P}x$ in this lattice where $x \in \mathbb{Z}^n$ can be associated to a quotient of coprime $P$-smooth integers $a, b$ which we call a $P$-smooth rational (or just a smooth rational). The concrete smooth rational is apparent in the first entry of the lattice vector: $\alpha \sum_{i=1}^n \log(p_i)x_i = \alpha \log(a/b)$ for some $P$-smooth rational $a/b$. One gets a quotient here since the $x_i$ can be negative. Moreover the association goes the other way since $x_i = \text{val}_{p_i}(a/b)$, so we get the following correspondence:

**Lemma 5.2.** For each $\alpha$ and $\alpha_i$, there is a one-to-one correspondence$^6$ between $P$-smooth rationals and lattice vectors in $\mathcal{L}_{\alpha, P}$ given by:

$$ \prod_{i=1}^{n} p_i^{x_i} \in \mathbb{Q} \longleftrightarrow B_{\alpha, \alpha_i, P} x \in \mathcal{L}. $$

The other entries in the lattice vector are $\alpha_i x_i$ for each $i$. These help to balance out the contribution of the first coefficient $\alpha \log(a/b)$ with the size of the exponents $|x_i|$. If these $\alpha_i$ would be 0 instead, then $\mathcal{L}_{\alpha, P}$ would no longer be discrete (and thus a lattice) and $\log(a/b)$ could be arbitrarily close to 0, leading to a very short vector without producing a smooth twin.

<footnote>$^6$A more appropriate name for this lattice might be the “smooth rational lattice” given this correspondence. But we chose to call it the “prime number lattice” for historical context.</footnote>
5.1. Properties of the prime number lattice. Due to Lemma 5.2 the length of each vector can directly be computed from the smooth rational a/b and its rational prime factorisation.

**Lemma 5.3.** Let $\mathbf{v} = \mathbf{B}_{\alpha,\alpha_i,P} \mathbf{x} \in \mathcal{L}_{\alpha,\alpha_i,P}$ be a lattice vector corresponding to a $P$-smooth rational $a/b = \prod_{i=1}^n p_i^{x_i}$ with $\gcd(a,b) = 1$. Then we have

$$ \|\mathbf{v}\|^2 = \alpha^2 \cdot \log\left(\frac{a}{b}\right)^2 + \sum_{i=1}^{n} (x_i \alpha_i)^2. $$

Moreover we have the following bounds

$$ \frac{(\sum_{i=1}^{n} |x_i \alpha_i|)^2}{n} \le \|\mathbf{v}\|^2 - \alpha^2 \cdot \log\left(\frac{a}{b}\right)^2 \le \left(\sum_{i=1}^{n} |x_i \alpha_i|\right)^2. $$

*Proof.* The first statement follows straightforwardly from the correspondence in Lemma 5.2. For the bounds, note that $\|\mathbf{v}\|^2 - \alpha^2 \cdot \log\left(\frac{a}{b}\right)^2 = \sum_{i=1}^n (x_i \alpha_i)^2 = \|\mathbf{y}\|^2$ for $\mathbf{y} := (x_i \alpha_i)_{i=1}^n \in \mathbb{R}^n$. Furthermore $\|\mathbf{y}\|_1 = \sum_{i=1}^n |x_i \alpha_i|$ when taking the 1-norm of the same vector. The result then follows from the general norm-inequalities $\frac{1}{n} \|\mathbf{y}\|_1^2 \le \|\mathbf{y}\|_2^2 \le \|\mathbf{y}\|_1^2$. $\square$

The length of the lattice vectors should be considered relative to the Gaussian Heuristic and thus the (normalised) volume of the lattice.

**Lemma 5.4 (Volume).** We have

$$ \mathrm{vol}(\mathcal{L}_{\alpha,\alpha_i,P}) = \sqrt{\alpha^2 \cdot \sum_{i=1}^{n} (\log(p_i)/\alpha_i)^2 + 1 \cdot \prod_{i=1}^{n} \alpha_i}. $$

If $\alpha_i := \log(p_i)$, the above simplifies to $\mathrm{vol}(\mathcal{L}_{\alpha,\log(p_i),P}) = \sqrt{\alpha^2 n + 1} \cdot \prod_{i=1}^{n} \log(p_i)$.

*Proof.* Let $\mathcal{C}$ be the basis where each $i$-th column of $\mathbf{B}_{\alpha,\alpha_i,P}$ is divided by $\alpha_i$. Then $\mathrm{vol}(\mathcal{L}_{\alpha,\alpha_i,P}) = \mathrm{vol}(\mathcal{L}(\mathcal{C})) \cdot \prod_{i=1}^n \alpha_i$. The first row of $\mathcal{C}$ is a vector $\mathbf{c}^\top = (\log(p_i) \cdot \alpha/\alpha_i)_{i=1}^n$, and the remaining $n$ rows form an identity matrix $I_n$. We thus get that $\mathcal{C}^\top \mathcal{C} = I_n^\top I_n + \mathcal{C}\mathcal{C}^\top$ which has eigenvalues $1 + \|\mathbf{c}\|^2, 1, \dots, 1$ and thus determinant $1 + \|\mathbf{c}\|^2$. So $\mathrm{vol}(\mathcal{L}_{\alpha,\alpha_i,P}) = \sqrt{1 + \|\mathbf{c}\|^2} \cdot \prod_{i=1}^n \alpha_i$ from which we obtain the result. $\square$

5.2. Finding smooth twins from the prime number lattice. We now give some intuition for finding smooth twins from this lattice. Recall from Section 4 that one can find a short vector $\mathbf{v}$ in a lattice $\mathcal{L}$ if the ratio $\|\mathbf{v}\|/\mathrm{gh}(\mathcal{L})$ is not too large.

First we consider the norm of the vector $\mathbf{v} = \mathbf{B}\mathbf{x} \in \mathcal{L}_{\alpha,\alpha_i,P}$ corresponding to a smooth rational $a/b$. Lemma 5.3 says that

$$ \|\mathbf{v}\|^2 = \alpha^2 \cdot \log\left(\frac{a}{b}\right)^2 + \sum_{i=1}^{n} (x_i \alpha_i)^2. $$

Observe that for a smooth twin $(a,b) = (r, r+1)$ we have that $a/b$ is very close to 1 and thus $\log(a/b) \approx 0$, while for other smooth rationals the contribution of $|\log(a/b)|$ can be much larger. More precisely, for large enough $r$ we have the approximation $\alpha^2 \log(a/b)^2 \approx (\alpha/(r+1))^2$. From this we see that we can actually pick $\alpha$ up to size $O(r)$ to get $\alpha^2 \cdot \log(a/b)^2 = O(1)$. In other words, we can increase $\alpha$ significantly without increasing the length of $\mathbf{v}$ much.
For the ratio of the vector $v$ relative to the Gaussian Heuristic, we also have to consider the sparsity or equivalently the volume of the lattice. From Lemma 5.4 we see that this is mainly determined by $\alpha$, in particular increasing $\alpha$ makes the lattice sparser. As we can freely increase $\alpha$ up to $O(r)$ essentially without increasing the norm of $v$ one could hope that the lattice becomes sparse enough for $v$ to be a short vector in the lattice. To make this reasoning more precise we first give a concrete and optimal choice of $\alpha$ in the following proposition.

**Proposition 5.5 (Optimal $\alpha$).** Let $a/b$ be a B-smooth rational whose set of prime factors are $P_{a,b} = \{p \in P_B : p \mid ab\}$. Choose a factor base $P = \{p_i\}$ with $P_{a,b} \subseteq P \subseteq P_B$ and weights $\alpha_i \in \mathbb{R}$ for $i = 1, \dots, n$. Let $n = \#P$, $\beta_1 = \log^2(a/b)$ and $\beta_2 = \sum_{i=1}^n (x_i \alpha_i)^2$ where $x_i = \text{val}_{p_i}(a/b)$. Then the choice

$$ \alpha = \alpha_{\text{opt}} \approx \sqrt{\frac{\beta_2}{(n-1)\beta_1}} $$

minimises $\|v\|$ / gh($\mathcal{L}_{\alpha,\alpha_i,P}$), among all $\alpha \in \mathbb{R}$, where $v \in \mathcal{L}_{\alpha,\alpha_i,P}$ is the corresponding vector to the smooth rational $a/b$.

*Proof.* Consider the following function $f(\alpha) = \|v\|^2 / \text{gh}(\mathcal{L}_{\alpha,\alpha_i,P_B})^2$ as a one variable function in terms of $\alpha$. With Lemma 5.3 and Lemma 5.4, we approximate$^7$ $f(\alpha)$ as

$$ f(\alpha) \approx \frac{\alpha^{2-2/n}\beta_1}{\gamma^2} + \frac{\beta_2}{\gamma^2\alpha^{2/n}}, $$

where

$$ \gamma = \sqrt{\frac{n}{2\pi e}} \left[ \sqrt{\sum_{i=1}^{n} \left( \frac{\log(p_i)}{\alpha_i} \right)^2} \prod_{i=1}^{n} \alpha_i \right]^{\frac{1}{n}}. $$

Minimising this expression in $\alpha$ is a straightforward calculus exercise. The result of this exercise gives the desired expression for $\alpha_{\text{opt}}$. Moreover, when $a/b \approx 1$, we can approximate $\beta_1 \approx (b/|a-b|)^2$ so we have

$$ \alpha_{\text{opt}} \approx \sqrt{\frac{\beta_2}{n-1}} \cdot \frac{b}{|a-b|}. $$

□

With this optimal choice of $\alpha$ we can simplify the ratio between the lattice vector and the Gaussian Heuristic.

**Corollary 5.6.** With $P, n, \beta_1, \beta_2$ and $\gamma$ defined in the Proposition 5.5 and the optimal choice $\alpha = \alpha_{\text{opt}}$, we have

$$ \frac{\|v\|}{\text{gh}(\mathcal{L}_{\alpha,\alpha_i,P})} \approx \left( \sqrt{\frac{\beta_2}{n-1}} \right)^{1-1/n} \cdot \frac{\sqrt{n\beta_1^{1/n}}}{\gamma}. $$

In Section 6 we analyse this expression for $f(\alpha_{\text{opt}})$ and show that, for at least the optimal smooth twins, the corresponding lattice vector for this choice is either the shortest vector or one of the shortest. A priori computing this $\alpha$ requires knowledge of the smooth rational itself since the terms use it and their factorisations. However

<footnote>$^7$Two approximations are made here: (1) is to remove the 1 from Lemma 5.4 which contributes negligibly to the volume; and (2) is the Gaussian heuristic approximation from Heuristic 4.1.</footnote>
by estimating $\beta_1$ and $\beta_2$ one can choose $\alpha$ approximately but close to $\alpha_{opt}$. It might not give the absolute shortest vector among all $\alpha$'s but it will still correspond to a short vector. One can also pick several $\alpha$ over some well-informed range in the hope to pick one very close to $\alpha_{opt}$.

The straight forward strategy to find smooth twins is now as follows: first one picks some smoothness bound $B$ and uses the factor base $P_B$. Then one makes a choice of $\alpha$, which is hopefully close to $\alpha_{opt}$ (based on Proposition 5.5 and estimates for $\beta_1, \beta_2$), before constructing the full lattice $\mathcal{L} = \mathcal{L}_{\alpha, \alpha_i, P_B}$. Then one computes short vectors in $\mathcal{L}$ using the techniques from §4.1. Finally, for each short vector $\mathbf{v} = \mathbf{B}_{\alpha, \alpha_i, P}\mathbf{x}$, one computes $a = \prod_{i:x_i>0} p_i^{x_i}$ and $b = \prod_{i:x_i<0} p_i^{-x_i}$ and checks if $|a-b|=1$.

Note that the best approach for finding the appropriate short vector $\mathbf{v} \in \mathcal{L}$ corresponding to a smooth twin depends on the ratio $\|\mathbf{v}\|/\mathrm{gh}(\mathcal{L})$ as discussed in Section 4. In short, if $\|\mathbf{v}\|/\mathrm{gh}(\mathcal{L}) \in [1, \sqrt{4/3}]$ one uses a lattice sieving algorithm to enumerate all lattice vectors with a length in that range, if $\|\mathbf{v}\| = \lambda_1(\mathcal{L})$ and $\|\mathbf{v}\|/\mathrm{gh}(\mathcal{L}) < 1$ one can use the BKZ lattice-reduction algorithm and dimensions for free to find that one unusually short vector at a lower cost.

**Remark 2.** We note that the CHM algorithm (see §2.1) is similar to a sieving-based SVP solver (like the one we use). The CHM algorithm multiplicatively combines two smooth twins together to form a new smooth twin. On the other hand the SVP solver takes the difference of two vectors to make a shorter vector. Modulo the multiplicative versus additive subtlety (since we work with logarithms), these procedures correspond to the same process – yet the two algorithms take different paths to find large smooth twins. The CHM method starts with small pairs that are already very close and constructs pairs of increasing size. Whereas the lattice siever starts with large pairs that are far apart and reduces their difference.

While the optimal twins will typically correspond to the shortest vectors, i.e., $\|\mathbf{v}\|/\mathrm{gh}(\mathcal{L}) = \lambda_1(\mathcal{L})/\mathrm{gh}(\mathcal{L})$ with a ratio less than or close to 1, the same cannot be said about the smaller twins simply because there are more of them. So one will not be able to find these twins by finding the shortest vector in the full prime number lattice. Furthermore, in high dimension when $\|\mathbf{v}\|/\mathrm{gh}(\mathcal{L}) > 1$, and especially above $\sqrt{4/3}$, recovering $\mathbf{v}$ can quickly become infeasible. Fortunately there are a few some solutions to this problem which we highlight here and discuss further in Section 7.

*Guessing.* Instead of working with full lattice to find B-smooth twins, one can guess some of the prime factors that do not appear in the smooth twin and work with the factor base $P = P_B \setminus Q$. The idea is that a B-smooth twin typically only uses a small fraction of primes from $P_B$ in its factorisation. More precisely, with this factor base $P$ we work in a sublattice of the full lattice by removing all vectors that correspond to smooth rationals containing a factor in $Q$. If the guess is correct this decreases both the lattice dimension as well as the ratio $\|\mathbf{v}\|/\mathrm{gh}(\mathcal{L})$.

*Dimensions for free.* Instead of guessing we can also reduce the dimension in which one has to run the lattice sieving algorithm by the dimensions for free technique as explained in Section 4. Even if the vector we want to recover is not unusually short, one could still hope to find it with a lowered probability when using this technique. We will refer to the number of dimensions $\ell \ge 0$ we decrease the lattice by as the amount of *lifting* we perform. Just as for the guessing strategy varying the amount of lifting gives a trade-off between success probability and the cost.
Non-continuous weights $\alpha_i$. We have yet to discuss how to choose $\alpha_i$. In Section 6 we discuss continuous choices of $\alpha_i$ (in terms of $\log(p_i)$). Alternatively one might instead want non-continuous weights – for instance a choice $\alpha_1 = \log(p_1)/\eta$, for some $\eta > 1$, and $\alpha_i = \log(p_i)$ for $i \ge 2$. This might be necessary when one needs to (say) find smooth twins with a large prime power (e.g. see Section 8).

## 6. ANALYSIS

We analyse the resulting expression from Corollary 5.6 to determine the shortness of vectors in the full prime number lattice corresponding to optimal smooth twins. In other words we make a blanket estimate of $r = e^{2e\sqrt{B}}$ for optimal twins (coming from Theorem 1.3) and analyse $\|v\|/\operatorname{gh}(\mathcal{L}_{\alpha_{\operatorname{opt}},\alpha_i,P_B})$. We give both theoretical and experimental analyses for various continuous choices of $\alpha_i$ (in terms of $\log(p_i)$).

We recall the generic expressions for $\beta_1$, $\beta_2$ and $\gamma$ which are used in the ratio $\|v\|/\operatorname{gh}(\mathcal{L}_{\alpha_{\operatorname{opt}},\alpha_i,P_B})$ as

$$ \beta_1 = \log^2(a/b), \quad \beta_2 = \sum_{i=1}^{n} (x_i \alpha_i)^2 \quad \text{and} \quad \gamma = \sqrt{\frac{n}{2\pi e}} \left[ \sqrt{\sum_{i=1}^{n} \left( \frac{\log(p_i)}{\alpha_i} \right)^2} \prod_{i=1}^{n} \alpha_i \right]^{\frac{1}{n}}, $$

where with our choice of factor base $P = P_B$ we have $n = \pi(B)$. The expression $\beta_1$ (and more precisely $\beta_1^{1/n}$) is straightforward to analyse. An estimate for $\beta_1^{1/n}$ was given during the proof of Proposition 5.5 and we make this more precise for optimal twins.

**Lemma 6.1.** *Assuming the optimal twin estimate for smooth twins, $r = e^{2e\sqrt{B}}$, as $n \to \infty$ we have*

$$ \beta_1^{1/n} \to 1. $$

*Proof.* Start with this asymptotically more precise statement $\beta_1 = 1/r^2 + O(1/r^3) = e^{-4e\sqrt{B}} + O(e^{-6e\sqrt{B}})$. Additionally we recall the elementary fact that $(1+x)^{1/k} = 1+x/k + O(x^2/k)$ for a positive integer $k$ and $|x| < 1$. So we have

$$ \begin{aligned} \beta_1^{\frac{1}{n}} &= e^{-\frac{4e\sqrt{B}}{n}} \left(1 + O(e^{-2e\sqrt{B}})\right)^{1/n} \\ &= e^{-\frac{4e\sqrt{B}}{n}} \left(1 + O\left(\frac{e^{-2e\sqrt{B}}}{n}\right)\right) \\ &= e^{-\frac{4e\sqrt{B}}{n}} + O\left(\frac{e^{-2e\sqrt{B}(1+2/n)}}{n}\right). \end{aligned} $$

We estimate $B$ in terms of $n = \pi(B)$ by the prime number theorem, i.e. $B = n \log(n) + O(n \log(\log(n)))$. With this we see that the main term approaches 1 and the error term approaches 0 as $n \to \infty$, completing the proof. $\square$

6.1. **Theoretical analysis with $\alpha_i = \log(p_i)$**. Now we deal with analysing $\beta_2$ and $\gamma$. This is non-trivial to do generically, i.e. without an explicit choice of $\alpha_i$. The most challenging aspect in doing this generically is analysing $\beta_2$ in its entirety as well as the sum $\sum_{i=1}^n ((\log(p_i)/\alpha_i)^2)$ in $\gamma$. For certain choices of $\alpha_i$ these quantities can be analysed. In particular we make a choice of $\alpha_i = \log(p_i)$ for this analysis.
**Lemma 6.2.** Taking $\alpha_i = \log(p_i)$, as $n \to \infty$ we have

$$ \gamma \sim \sqrt{\frac{n}{2\pi e}} (\log(n) + \log(\log(n)) - 1). $$

*Proof.* With our choice of $\alpha_i$ we can write $\gamma$ as

$$ \gamma = \sqrt{\frac{n}{2\pi e}} \left( n \prod_{j=1}^{n} \log(p_j) \right)^{1/n}. $$

By Lemma A.1 we have $(\prod_{i=1}^n \log(p_i))^{1/n} \sim \log(B) - 1$. Since $n^{1/n} \to 1$ and (once again) $B \sim n \log(n)$ we obtain the desired result. $\square$

**Lemma 6.3.** Taking $\alpha_i = \log(p_i)$ and the optimal twin estimate, we have

$$ \frac{16e^2 B}{n} \le \beta_2 \le 4 \left( 2e\sqrt{B} + \frac{1}{r} \right)^2. $$

*Proof.* Recall that $\beta_2 = \sum_{i=1}^n x_i^2 \log^2(p_i)$ and, by Lemma 5.3, we have the inequality

$$ (7) \qquad \frac{(\sum_{i=1}^n |x_i \log(p_i)|)^2}{n} \le \beta_2 \le \left( \sum_{i=1}^n |x_i \log(p_i)| \right)^2. $$

One can calculate that $\sum_{i=1}^n |x_i \log(p_i)| = \log(r) + \log(r+1)$. Using the optimal twin estimate, this is bounded below by $4e\sqrt{B}$ and bounded above by $4e\sqrt{B} + 2/r$. Substituting these bounds in (7) gives the desired lower and upper bounds. $\square$

We are now able to bring everything together.

**Proposition 6.4.** Let $v \in \mathcal{L} = \mathcal{L}_{\alpha, \alpha_i, P_B}$ be the lattice vector corresponding to an optimal B-smooth twin $(r, r+1)$ with the optimal choice $\alpha = \alpha_{\text{opt}}$ and weights $\alpha_i = \log(p_i)$. Then we have

$$ \frac{\|v\|}{\operatorname{gh}(\mathcal{L}_{\alpha, \alpha_i, P_B})} = O\left(\frac{1}{\sqrt{\log(n)}}\right). $$

*Proof.* Combining Lemma 6.1 and Lemma 6.2 we get

$$ \frac{\sqrt{n\beta_1^{1/n}}}{\gamma} \sim \frac{\sqrt{2\pi e}}{\log(n) + \log(\log(n)) - 1}, $$

and Lemma 6.3 gives an upper bound for $(\sqrt{\beta_2/(n-1)})^{1-1/n}$ which again by the prime number theorem can be solely expressed in terms of $n$. In particular we have

$$ \left( \sqrt{\frac{\beta_2}{n-1}} \right)^{1-1/n} = O\left( \sqrt{\log(n)} \right). $$

Combining these together with Corollary 5.6 gives the intended result. Moreover with the lower bound in Lemma 6.3 we also have $\|v\|/\operatorname{gh}(\mathcal{L}) = \Omega(1/(n \log(n)))^{1/2}$. $\square$
<figure><img src="image_2.png" /><figcaption>**Figure 2.** On the left a comparison of the GH ratios achieved for varying exponents $e$ in $\alpha_i = \log^e(p_i)$ on the set of all strictly 199-smooth twins. On the right a scatter plot of the GH ratio versus the bit size of the 199-smooth twins.</figcaption></figure>

## 6.2. Experimental analysis with different $\alpha_i$. 
The theoretical analysis suggests that, for large enough $B$, the lattice vector corresponding to an optimal $B$-smooth twin is unusually short and one should be able to find it with BKZ. However this expression abstracts the constant in the big $O$ term that one gets from the generic bounds (notably for $\beta_2$) and it is unclear from this analysis whether the ratio is less than or greater than 1 for small $B$. So we conduct experimental analysis not only for large $B$-smooth twins but also smaller smooth twins to assess their GH ratios $\|v\|/\operatorname{gh}(\mathcal{L})$. We will observe that for the largest twins we are in the scenario where either $\|v\|/\operatorname{gh}(\mathcal{L}) \approx 1$ or $1 < \|v\|/\operatorname{gh}(\mathcal{L}) < \sqrt{4/3}$ – so one needs to do lattice sieving to find them.

We also experiment with a more generic expression $\alpha_i = \log^e(p_i)$ which is non-trivial to analyse theoretically primarily due to the $\beta_2$ analysis. One could plausibly try to minimise the resulting expression in Corollary 5.6 with this generic $\alpha_i$ (in a similar manner to Proposition 5.5) but the analysis becomes difficult to get precise.

The influence of different $\alpha_i$ is considered further experimentally in Section 7.2. For now we consider the GH ratio $\|v\|/\operatorname{gh}(\mathcal{L})$ one obtains for several exponents $e$ in $\alpha_i = \log^e(p_i)$ on the set of strictly 199-smooth twins. We think our set of such smooth twins is complete, see Conjecture 7.1, and it should therefore give a good representation.

In the left plot of Figure 2 we see that exponents of $e = 1$ or $e = 1.25$ lead to the most twins with a small GH ratio. Among all strictly 199-smooth twins the ratio $\|v\|/\operatorname{gh}(\mathcal{L}_{\alpha_{\operatorname{opt}}, \alpha_i, P_B})$ is on average 1.28 and no larger than 2.3 for $\alpha_i = \log(p_i)$. When minimising the ratio with respect to the exponent $e$ (through numerical computations) the average and largest ratio among these twins is roughly 1.25 and 2.2 respectively. The twins with a larger ratio typically contain an unusually large prime power due to the larger contribution from $|x_i\alpha_i|$. For instance this is the case for the 199-smooth twin $(r, r+1)$ where $r = 107^6 - 1$ which clearly has a large power of 107. In the right plot in Figure 2 we see a dependency between the GH ratio and the size of the twins. In particular, for larger twins we observe that the ratio generally becomes better, which is in line with our theoretical analysis.
**Remark 3.** The plots in Figure 2 use the optimal $\alpha = \alpha_{opt}$ for each twin which does not correspond to the same $\alpha$ across the board. If one fixes a single $\alpha$ then the largest ratio will far exceed 2. Moreover the choice of $\alpha$ influences the size of the resulting twin that one gets as a shortest vector. This is implied by Proposition 6.4 and is emphasised more explicitly in §7.1.

## 7. SMOOTH TWIN RESULTS

We record the results of our experiments finding smooth twins from the prime number lattice. All experiments were performed on the PlaFRIM cluster on two types of nodes: for the CPU-only experiments nodes with 64 ZEN2 cores at 2.35GHz and 256GB memory, and for the GPU experiments nodes with 64 ZEN3 cores at 2.60GHz, 2 NVIDIA A100 GPUs and 512GB memory.

We used the lattice sieving library G6K [5] for our experiments, along with the extension from [21] that accelerates the sieving procedure by using modern GPUs <fnref n="8" />. These were developed to serve cryptanalytic efforts for lattice based cryptosystems, with SVP-record computations up to dimension 180 [21].

### 7.1. Optimal twins from CPU sieving.
We will use the heuristic estimates from §3.1 as well as work with the full lattice to find large heuristically optimal twins. We restrict to CPU sieving for the time being.

Recall from Proposition 5.5 that for a known B-smooth twin $(r, r+1)$ the optimal $\alpha$ is $\alpha_{opt} \approx \sqrt{\beta_2/(n-1)} \cdot r$. For the weight choice $\alpha_i = \log(p_i)$, we saw in the proof of Proposition 6.4 that $\sqrt{\beta_2/(n-1)} = O(\sqrt{\log(n)})$. Now suppose this twin (of say $b$ bits) is unknown and one wants to find it. By approximating the size of the optimal $\alpha$ as $\log_2(\alpha) = \log_2(\mu) + \log_2(\sqrt{\log(n)}) + b$ for a small $\mu$, one should expect to find this twin. More generally the experimental analysis suggests that the ratio $\sqrt{\beta_2/(n-1)}$ is not large for other continuous choices of $\alpha_i = \log^e(p_i)$. So once again $\log_2(\alpha)$ can be chosen to be a little larger than the target bit size. We observe this further in §7.2.

For example lets take $B = 200$. The optimal 200-smooth twins is estimated to have $\log_2(r) \approx 91.139$ (see Table 1). With a choice of weights $\alpha_i = \log(p_i)$ and choosing $\alpha = 2^{94}$ (say) we find the shortest vectors in the lattice $L_{2^{94},\log(p_i),P_{200}}$. The 9th shortest vector in this lattice corresponds to the following 95-bit 199-smooth twin which was not known prior to this work

$$r = 3^2 \cdot 5^2 \cdot 7^5 \cdot 11^3 \cdot 59 \cdot 71^2 \cdot 101 \cdot 127 \cdot 173^2 \cdot 197 \cdot 199 \text{ and} \\ r + 1 = 2^{10} \cdot 13 \cdot 17^2 \cdot 23 \cdot 37^2 \cdot 41 \cdot 47 \cdot 61 \cdot 79 \cdot 107^2 \cdot 113^2 \cdot 137.$$

This twin exceeds the heuristic estimate, so one can claim this is the optimal 200-smooth twin. Moreover the optimal $\alpha = \alpha_{opt}$ is $\log_2(\alpha_{opt}) \approx 96.324$ for this twin; which now corresponds to the 5th shortest vector in the lattice $L_{\alpha_{opt},\log(p_i),P_{200}}$.

The dimension of the full lattice $L_{2^{94},\alpha_i,P_{200}}$ is $\pi(200) = 46$ and SVP records have much larger dimension. More specifically one SVP call comes at a cost of $2^{0.292\pi(B)+o(\pi(B))}$. Previously one could only (heuristically) find optimal twins by solving lots of Pell equations (see §2.1) at a lower bound cost of $2^{\pi(B)+o(\pi(B))}$. This saving in the exponent is the main contributing factor that will allow us to choose larger smoothness bounds and find larger optimal twins. We include Figure 3 – an

<footnote n="8">⁸Available at https://github.com/fplll/g6k and https://github.com/WvanWoerden/G6K-GPU-Tensor respectively</footnote>
<figure><img src="image_3.png" /><figcaption>**Figure 3.** Comparing the numerical estimates for optimal B-smooth twins (marked with a blue plus) against known largest twins with $B \le 547$. The red dots mark the sizes of the largest strictly B-smooth twins, while the orange line indicates the largest twin up to the smoothness bound $B$. All twins up to the dotted vertical line were found by the Pell equation method. Between the vertical line and $B = 227$ the largest twins were either found by CHM or our lattice method. Beyond that all largest twins were all found by our method.</figcaption></figure>

analogue comparison done in Figure 1 to cover the largest B-smooth twins that we found for $B \le 547$. We list these twins in Appendix B.

The largest twin B-smooth twin that we found using CPU lattice sieving and conjecture to be optimal is the following 180-bit 647-smooth twin. It was found from the lattice $\mathcal{L}_{2^{182},\log(p_i),p_{647}}$ and has factorisations:

$$r = 2^4 \cdot 7^3 \cdot 17^2 \cdot 23 \cdot 47 \cdot 61 \cdot 131^4 \cdot 139^2 \cdot 163 \cdot 179 \cdot 197 \cdot 223 \cdot 257 \cdot 293 \cdot 379 \cdot 443 \cdot 563 \cdot 569 \cdot 617 \cdot 647, \text{ and}$$

$$r + 1 = 3 \cdot 5 \cdot 13 \cdot 19 \cdot 31^2 \cdot 41 \cdot 59 \cdot 71 \cdot 127 \cdot 137 \cdot 151^2 \cdot 233 \cdot 263 \cdot 307^2 \cdot 349^3 \cdot 431 \cdot 467 \cdot 509 \cdot 523 \cdot 601 \cdot 643.$$

## 7.2. Influence of parameters.
We first consider the influence of the parameters we can choose for the search of smooth twins. All experiments done in this section are by the CPU-only implementation of G6K. For these experiments we consider a smoothness bound of $B = 691$ and a factor base among the 125 primes less than $B$. For each set of parameters we did 64 trials, each with a different seed. We will typically plot histograms with the normalised frequency, i.e., the total number of smooth twins found normalised by the 64 trials, on the y-axis. Unless otherwise stated we only consider the number of unique smooth twins found over all 64 trials.

We fix some default parameters, each of which we will change in individual experiments. By default we leave out $k = 15$ primes in the guessing phase and lift
<figure><img src="image_4.png" /><figcaption>**Figure 5.** Histogram of the normalised number of smooth twins found when changing the diagonal exponent $e$ in $\alpha_i = \log_2(p_i)^e$. The left plot is in the normal regime and plotted against the size $\log_2(r)$ of each smooth twin $(r, r+1)$, while the right plot is in the powers-of-two regime and plotted against the power-of-two exponent $\text{val}_2(r(r+1))$.</figcaption></figure>

*Guessing versus lifting.* The guessing and dimensions for free lifting approach both give a trade-off between the lattice dimension one sieves in and the success probability of finding smooth twins. We therefore compare their usage by considering $k$ guessing dimensions and $l$ lifting dimensions such that $k + l = 20$ is constant and vary<fnref n="9" /> $k \in \{5, 10, 15, 20\}$. Both regimes are considered for this comparison and we make separate plots counting the normalised frequency for the number of found twins with or without duplicates.

We first consider the results for the normal regime in Figure 6. In the left plot, counting with duplicates, we see that a somewhat even division $(k, l) = (10, 10)$ and favouring guessing (15, 5) are comparable, and significantly better than a lot of lifting (5, 15) or no lifting (20, 0). In the right plot, only counting unique smooth twins, we however see that the balance shifts to favouring guessing $(k, l) = (15, 5)$ being optimal. One explanation could be that the lifting technique disproportionately favours exceptionally short twins, which are thereby found multiple times in different trials once they can be represented by the guessed factor base.

In the powers-of-two regime we see a similar result in Figure 7. Here favouring guessing $(k, l) = (15, 5)$ is optimal when counting duplicates, but in the unique regime we see that (20, 0) comes close to the same performance.

*Scaling and exponent trick for finding large powers of two.* One could be interested in finding smooth twins $(r, r+1)$ such that the factorisation of $r(r+1)$ contains a large power of two (see Section 8 for instance). We consider two methods to guide the search to such smooth twins. Firstly, one could simply replace $p_1 = 2$ in the factor base by $p_1 = 2^f$ for some $f > 1$. In this case all smooth twins that are found in the corresponding lattice are guaranteed to have $f|\text{val}_2(r(r+1))$ and $\text{val}_2(r(r+1)) \ge f$ (as $\text{val}_2(r(r+1)) \ge 1$). Furthermore, increasing $f$ makes the

<footnote n="9">⁹The case $k=0$ is not considered as otherwise each trial would use exactly the same lattice.</footnote>
<figure><img src="image_5.png" /><figcaption>**Figure 6.** Comparison of two dimension reducing techniques, guessing versus lifting (d4f), in the normal regime. We vary the guessing and lifting dimensions $(k, l)$ while keeping their sum $k + l = 20$ fixed. We show the normalised frequency with and without duplicates on the left and right respectively.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Figure 7.** Same as Figure 6 but in the power-of-two regime.</figcaption></figure>

lattice sparser, and could therefore improve the chances of finding smooth twins that has a larger power of $2^f$. This is however a downside to this method since one cannot find smooth twins such that the exponent on 2 is not a multiple of $f$.

The second method decreases the weight $\alpha_1$ by a factor $\eta > 1$ so that the norm contribution from $|x_1\alpha_1| = \text{val}_2(r(r+1))|\alpha_1|$ is not as significant when $\text{val}_2(r(r+1))$ is large. Informally, by decreasing the weight of $\alpha_1$, the lattice vectors corresponding to a large power of two get a relatively lower norm. At the same time decreasing $\alpha_1$ also makes the lattice denser and thus one has to balance the choice of $\alpha_1$. We consider $\alpha_1 = \log(p_1)/\eta$ for scalars $\eta \in \{1, 5, 10, 20, 40\}$, where $\eta = 1$ corresponds to the normal regime.

The results are shown in Figure 8. In the left plot we observe that replacing $p_1 = 2$ by $p_1 = 2^f$ for $f > 1$ does find more smooth twins with $f | \text{val}_2(r(r+1))$. In the right plot we observe the effect of downscaling $\alpha_1$. With a factor $\eta = 5$ we find smooth twins with $\text{val}_2(r(r+1)) \ge 35$; while with $\eta = 1$ we essentially do not find
<figure><img src="image_7.png" /><figcaption>**Figure 8.** Influence of the scalar $\eta$ in $\alpha_1 = \log(p_1)/\eta$ and the exponent $f$ in power-of-two factor $p_1 = 2^f$ in the factor case on finding smooth twins $(r, r+1)$ with a large power of two in $r(r+1)$.</figcaption></figure>

any smooth twins with $\text{val}_2(r(r+1)) \ge 25$. Furthermore the influence of choosing a larger $\eta > 5$ is small compared to $\eta = 5$.

### 7.3. Results from GPU lattice sieving.
We now detail the results from our GPU experiments. Due to memory limitations we can work in these experiments with a maximal lattice sieving dimension of 137 when accounting for lifting and guessing. Lattice sieving in this dimension takes half a day on a single node of the PlaFRIM cluster.

When working with the full lattice with no lifting nor guessing we are able to find larger optimal twins compared to those found with CPU sieving in §7.1. In particular with $B = 773$ (where $\pi(B) = 137$) we found the following 195-bit 743-smooth twin with factorisations:

$$r = 7 \cdot 19^3 \cdot 23 \cdot 37 \cdot 47^2 \cdot 79 \cdot 89 \cdot 97^3 \cdot 103 \cdot 211 \cdot 229^2 \cdot 271^2 \cdot 283 \cdot 307 \cdot 401^2 \\ \cdot 503 \cdot 541 \cdot 557 \cdot 631 \cdot 643, \text{ and}$$

$$r + 1 = 2^{11} \cdot 5^2 \cdot 11 \cdot 13 \cdot 43^2 \cdot 53 \cdot 59 \cdot 131 \cdot 137 \cdot 149 \cdot 163 \cdot 223^3 \cdot 281 \cdot 313 \cdot 337 \\ \cdot 353 \cdot 409 \cdot 449 \cdot 547 \cdot 563 \cdot 653 \cdot 709 \cdot 743,$$

as well as the 196-bit 751-smooth twin mentioned in (1). Both of these twins are believed to be optimal in accordance to the heuristic estimates.

Working with a larger $B$ (where $\pi(B) > 137$) and finding optimal twins from the full lattice becomes computationally challenging. So we incorporate a combination of lifting and guessing to our lattice and start with lifting only. For instance, with $B = 823$ and a lifting amount of $l = 5$ in the full lattice, we found the following 200-bit 809-smooth twin

$$r = 2^6 \cdot 17^3 \cdot 23 \cdot 29^2 \cdot 47 \cdot 53^2 \cdot 59 \cdot 67^2 \cdot 107 \cdot 131 \cdot 137 \cdot 163 \cdot 193 \cdot 271 \\ \cdot 277 \cdot 283 \cdot 313 \cdot 359 \cdot 397 \cdot 433 \cdot 523 \cdot 751 \cdot 787 \cdot 809, \text{ and}$$

$$r + 1 = 3^{13} \cdot 5^2 \cdot 7^2 \cdot 11 \cdot 19 \cdot 41^2 \cdot 71 \cdot 73 \cdot 89 \cdot 139 \cdot 179 \cdot 263^2 \cdot 269 \cdot 557^2 \cdot 577 \\ \cdot 587^2 \cdot 607 \cdot 677 \cdot 683 \cdot 709 \cdot 733.$$
This smooth twin is close to the estimates for optimal 809-smooth twins which is predicted to have 202 bits. So we are unsure whether this twin is optimal or not. Alternatively this twin can be found by solely guessing with (say) $B = 823$ and $k = 5$. To have success with this, one should choose a removal subset $Q \subseteq P_B$ that has no primes in the factorisation of $r(r+1)$. Generally, small primes should not be placed in $Q$, as these primes are more likely to appear in the large twin. The probability of choosing an appropriate subset $Q \subseteq P_B \setminus P_{300}$ of size $\#Q = 5$ is roughly $(\binom{65}{5})/\binom{81}{5} \approx 0.3224$ which is not too small.

By increasing the amount of lifting and guessing we can find larger B-smooth twins than this 809-smooth twin. However, one cannot expect to find twins that are close to optimal anymore, especially if the combined lifting and guessing is large. For instance we did experiments with $B = 997$ (where $\pi(B) = 168$). We fixed the lattice sieving dimension to be 137 and chose several lifting and guessing amounts, $l$ and $k$ (respectively), such that $k+l = 168-137 = 31$ and $k > l$ (in accordance to the analysis in §7.2). In particular, in one of these runs with $l = 11$ and $k = 18$, we found the 213-bit 997-smooth twin mentioned in (2). According to the heuristic estimates, this twin is not at all close to the estimated largest 997-smooth twin which is predicted to have 227 bits.

Additionally we did experiments with larger B with more combined lifting and guessing. However we did not find any larger twins than this 997-smooth twin.

*Cryptographic smooth twins.* For smooth twins suitable for isogeny-based cryptography, we recall that 256-bit twins are necessary. In Section 8 we will see that smooth twins are not strictly necessary for certain cryptographic applications, as a few larger factors are allowed. However for the purpose of this discussion we discuss the challenges of finding cryptographic smooth twins.

According to Table 1, one should at least expect to find such a 256-bit B-smooth twin with $B \approx 1250$ where $\pi(B) = 204$. This is larger than what we were able to do, but records in SVP computations are getting closer to these dimensions [5, 21, 38] with the current record<fnref n="10" /> at dimension 200 which includes a large amount of lifting. So finding these twins is just beyond computational reach. Even if one incorporates lifting and guessing, one would need a large amount of trials in order to find the desired smooth twin – adding to the computational cost.

## 7.4. Towards enumerating all B-smooth twins.
We now address the problem of finding all B-smooth twins for some fixed $B > 113$. The main obstruction to doing this with our lattice approach is that not all smooth twins correspond to particularly short vectors in the full lattice (see Figure 2). To find them through SVP instances a sufficient amount of guessing is required (which might be large depending on the specific twin). If $k$ is a guessing amount then there are a total of $(\pi(B))$ subsets $P \subseteq P_B$ of size $n-k$. The cost of sieving in this prime number lattice with factor base $P$ is $O(2^{0.292(\pi(B)-k)})$. So the total cost of going through each subset $P$ for a fixed guessing amount $k$ is

$$ (8) \qquad O\left(\kappa_{k,\alpha} \binom{\pi(B)}{k} 2^{0.292(\pi(B)-k)}\right) $$

where $\kappa_{k,\alpha}$ is the number of distinct $\alpha$'s that are chosen. To make this more precise, one would need a provable guessing amount $k$ as well as a bound on $\kappa_{k,\alpha}$ to assert

<footnote n="10">¹⁰For SVP records see https://www.latticechallenge.org/svp-challenge/.</footnote>
all B-smooth twins have been found. It is beyond the scope of this work to ascertain such provable results.

**Remark 4.** By Theorem 1.3, the number of prime factors in B-smooth twins is heuristically at most $O(\sqrt{B}/\log(B))$, which when B is large, is only a small fraction of all $O(B/\log(B))$ primes up to B. Therefore, by doing a very large amount of guessing, e.g. taking $k = \pi(B) - O(\sqrt{B}/\log(B))$ in (8), we get a resulting complexity of

$$O(\kappa_{k,\alpha}e^{O(\sqrt{B})+o(\sqrt{B})})$$

to find all B-smooth twins. While this gives a subexponential complexity, it is not practical for the small values of B we have worked with. A similar heuristic analysis can be made with the Pell equation approach. One would early abort solving the equation $x^2 - Dy^2 = 1$ using the continued fraction of $\sqrt{D}$, namely when x becomes larger than $e^{4e\sqrt{B}}$, instead of concretely solving all $2^{\pi(B)}$ equations. This should also give a subexponential complexity, but which only pays off for huge B.

Alternatively one can start with a known set of B-smooth twins and use the lattice approach to add previously undiscovered twins to this set. One still needs to incorporate guessing in order to find the obscure twins but if the known set is quite large then one can minimise the amount of necessary searching. and plausibly conjecture the complete set of B-smooth twins.

A large proportion of B-smooth twins for $B \le 547$ was found using the CHM algorithm [9] (described in §2.1). Notably the larger B-smooth twins are not found with the CHM algorithm, most of which our SVP solver should be able to find with minimal guessing. We extensively searched for B-smooth twins with $B < 400$ and found many new twins. In particular we conjecture to have the complete set of 200-smooth twins as summarised below.

**Conjecture 7.1.** There are exactly 348,865 many 200-smooth twins.

<table><caption>**Table 2.** Cumulative number of B-smooth twins found using lattices and CHM. The subscript in CHM<sub>B</sub> denotes applying the CHM algorithm with B as input.</caption><thead><tr><th></th><th>CHM<sub>B</sub></th><th>CHM<sub>547</sub></th><th>SVP</th></tr></thead><tbody><tr><td>B = 150 :</td><td>73,694</td><td>74,006 (+312)</td><td>74,007 (+1)</td></tr><tr><td>B = 200 :</td><td>346,192</td><td>348,840 (+2,648)</td><td>348,865 (+25)</td></tr><tr><td>B = 250 :</td><td>826,750</td><td>835,613 (+8,863)</td><td>835,880 (+267)</td></tr><tr><td>B = 300 :</td><td>2,316,631</td><td>2,350,100 (+33,469)</td><td>2,353,597 (+3,497)</td></tr><tr><td>B = 350 :</td><td>—</td><td>5,431,970</td><td>5,456,953 (+24,983)</td></tr><tr><td>B = 400 :</td><td>—</td><td>11,840,978</td><td>11,980,459 (+139,481)</td></tr></tbody></table>

No formal claims are made for larger B but we note down in Table 2 the cumulative number of B-smooth twins found in this and prior work. We did not extend our experiments to B = 547 due to the increasing computational effort.
Asymptotic cardinality of B-smooth twins. Let $N_B$ denote the number of B-smooth twins. A natural question to ask is how $N_B$ grows. By solving Pell equations, the bound $N_B \le (B+1)(2^{\pi(B)}-1)/2$ for $B \ge 5$ is known [25, Theorem 4]. This is a bad measurement of $N_B$ based on the known and conjectured B. Taking inspiration from Theorem 1.3 one might expect a better bound where $\pi(B)$ in the exponent is replaced by $\Theta(\sqrt{\pi(B)})$. When interpolating the data for $B < 200$ this trend does appear and one can claim that $N_B \sim \exp(C\sqrt{\pi(B)})$ as $B \to \infty$ for some constant $0.5 < C < 1.5$. We do not give a proof nor provide an explicit constant C for this and hence we leave these details open to the reader.

## 8. APPLICATIONS

### 8.1. SQIsign parameters.
SQIsign is a family of post-quantum signature schemes based on the Deuring correspondence. The high-level idea in each variant is the same but the algorithmic tools in practice differ. For accessible resources on SQIsign and its variants we refer the reader to [22, 23, 27, 11, 14, 6, 31, 1].

We revisit the original version of SQIsign, which we call SQIsign1D, and find new parameters. In particular one works with a prime $p$ such that $2^f \cdot T \mid p^2 - 1$ where $f$ is as large as possible and $T \approx p^{5/4}$ is odd and B-smooth. This condition implies that not all of $p^2 - 1$ needs to be smooth, which differs from the fully smooth twin scenario, i.e. a smooth twin $(r, r+1)$ with $p = 2r+1$ so that $p^2 - 1 = 4r(r+1)$.

The main idea in the SQIsign1D prime search is to adopt a boosting strategy. For 256-bit primes the idea is to use the polynomial $p_2(x) = 2x^2 - 1$ (emblematic of the ideas in §2.2). For such a $p = p_2(r)$ we need smooth divisors in $r-1, r, r+1$ since $p^2 - 1 = 4r^2(r-1)(r+1)$. There are two ways of choosing $r$ that maximises the chances of meeting all requirements. In both cases one ensures that $r$ is smooth and has a large power of two (which is amplified by the squaring in $p_2 + 1$).

### Sieve-and-boost approach.
Instead of doing an exhaustive search on smooth $r$ which is expensive, one can do a tailored exhaustive search over integers of the form$^{11}$ $r = 2^{f'} \cdot 3^{g'} \cdot m$ where $m$ is smooth. Then for each such $r$ factorise the smooth parts of $r-1$ and $r+1$ and see if this gives the necessary amount of smoothness. This strategy was adopted for the first round of the NIST submission [11] and found the prime $p = p_2(r)$ where $r = 2^{37} \cdot 3^{18} \cdot 2053899652631121509$ with factorisations

$$p+1 = 2^{75} \cdot 3^{36} \cdot 23^2 \cdot 59^2 \cdot 101^2 \cdot 109^2 \cdot 197^2 \cdot 491^2 \cdot 743^2 \cdot 1913^2, \text{ and}$$

$$\begin{aligned} p-1 = & 2 \cdot 7^4 \cdot 11 \cdot 13 \cdot 37 \cdot 89 \cdot 97 \cdot 107 \cdot 131 \cdot 137 \cdot 223 \cdot 239 \cdot 383 \cdot 389 \cdot 499 \\ & \cdot 607 \cdot 1033 \cdot 1049 \cdot 1193 \cdot 1973 \cdot 32587069 \cdot 275446333 \\ & \cdot 1031359276391767. \end{aligned}$$

The factors highlighted in grey are the non-smooth factors which are not used in SQIsign1D. A more in-depth description of this strategy is given in [15].

### Twin-and-boost approach.
Recall that $p^2 - 1 = 4r^2(r-1)(r+1)$ for $p = p_2(r)$. Observe that if $(r, r \pm 1)$ is a smooth twin for at least one choice of the sign and $2^{f'} \mid r$ then $p^2 - 1$ has a smooth factor of size $p^{3/2}$; and if $f = 2f' + 1 \le \log_2(p)/4$ then $2^f \cdot T \le p^{3/2}$. So if $f \le \log_2(p)/4$ then it is sufficient to simply check the primality of $p$. If $f > \log_2(p)/4$ then we need to hope for enough small prime

<footnote>$^{11}$The inclusion of the power of three is not mandatory but it simplifies certain steps in the signing procedure and was a design choice made in the original NIST submission [11].</footnote>
factors in $r \neq 1$. Depending on how much larger $f$ is relative to $\log_2(p)/4$, the probability that one has these factors is not too small [34].

So a sufficiently good smooth twin oracle producing smooth twins with a large power of two can efficiently give SQIsign1D parameters. This observation was first noted in [9] but they were unable to instantiate this oracle with the CHM algorithm. On the other hand we can instantiate this properly with our lattice approach aimed at finding smooth twins with a large power of two. For more details on tailoring the search for such smooth twins see §7.2. In particular we found the exceptional prime $p = p_2(r)$ where $r = 2^{31} \cdot 2493490582368659543466244025$ with factorisations

$$p+1 = 2^{63} \cdot 5^4 \cdot 23^4 \cdot 67^2 \cdot 71^2 \cdot 73^2 \cdot 89^2 \cdot 113^2 \cdot 137^4 \cdot 163^2 \cdot 229^2 \cdot 263^2 \cdot 293^2, \text{ and}$$

$$p-1 = 2 \cdot 3 \cdot 7^2 \cdot 11 \cdot 13^2 \cdot 31 \cdot 47^2 \cdot 79^2 \cdot 103 \cdot 151 \cdot 241^2 \cdot 353 \cdot 367 \cdot 389 \cdot 449 \cdot 463 \cdot 499 \cdot 50355971 \cdot 1032403334060991048097384477.$$

With a significantly smaller smoothness bound compared to the previous parameter, this offers a better signing performance in accordance to the SQIsign1D estimator sage script provided in [15]. In particular one could theoretically get a modest 19.85% improvement on the signing performance, but we remark that practical considerations are needed in order to materialise this improvement. However we note that this will not compete with the latest versions of SQIsign and notably the second round submission to NIST's signature call [1]. So we present this prime to expand diversity of SQIsign1D primes.

## REFERENCES

[1] M. A. Aardal, G. Adj, D. F. Aranha, A. Basso, I. A. Canales Martínez, J. Chávez-Saab, M. Corte-Real Santos, P. Dartois, L. De Feo, M. Duparc, J. K. Eriksen, T. B. Fouotsa, D. L. Gazzoni Filho, B. Hess, D. Kohel, A. Leroux, P. Longa, L. Maino, M. Meyer, K. Nakagawa, H. Onuki, L. Panny, S. Patranabis, C. Petit, G. Pope, K. Reijnders, D. Robert, F. Rodríguez-Henríquez, S. Schaeffler, and B. Wesolowski, *SQIsign*, Tech. report, National Institute of Standards and Technology, 2025, Version 2.0, available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-2/spec-files/sqisign-spec-round2-web.pdf.

[2] L. A. Adleman, *Factoring and Lattice Reduction*, Manuscript, 1995.

[3] D. Aggarwal, D. Dadush, O. Regev, and N. Stephens-Davidowitz, *Solving the shortest vector problem in $2^n$ time using discrete Gaussian sampling*, STOC, ACM Press, 2015, pp. 733-742.

[4] D. Aggarwal, D. Dadush, and N. Stephens-Davidowitz, *Solving the closest vector problem in $2^n$ time-the discrete Gaussian strikes again!* FOCS, IEEE, 2015, pp. 563-582.

[5] M. R. Albrecht, L. Ducas, G. Herold, E. Kirshanova, E. W. Postlethwaite, and M. Stevens, *The general sieve kernel and new records in lattice reduction*, EUROCRYPT, Lecture Notes in Computer Science, vol. 11477, Springer, 2019, pp. 717-746.

[6] A. Basso, P. Dartois, L. De Feo, A. Leroux, L. Maino, G. Pope, D. Robert, and B. Wesolowski, *SQIsign2D-West: The fast, the small, and the safer*, ASIACRYPT, Lecture Notes in Computer Science, vol. 15486, Springer, 2024, pp. 339-370.

[7] A. Basso and L. Maino, *Poké: A compact and efficient PKE from higher-dimensional isogenies*, EUROCRYPT, Lecture Notes in Computer Science, vol. 15602, Springer, 2025, pp. 94-123.

[8] A. Becker, L. Ducas, N. Gama, and T. Laarhoven, *New directions in nearest neighbor searching with applications to lattice sieving*, SODA, ACM-SIAM, 2016, pp. 10-24.

[9] G. Bruno, M. Corte-Real Santos, C. Costello, J. K. Eriksen, M. Meyer, M. Naehrig, and B. Sterner, *Cryptographic smooth neighbors*, ASIACRYPT, Lecture Notes in Computer Science, vol. 14444, Springer, 2023, pp. 190-221.
[10] J. Buzek, J. Hasan, J. Liu, M. Naehrig, and A. Vigil, *Finding twin smooth integers by solving Pell equations*, (2022).

[11] J. Chávez-Saab, M. Corte-Real Santos, L. De Feo, J. K. Eriksen, B. Hess, D. Kohel, A. Leroux, P. Longa, M. Meyer, L. Panny, S. Patranabis, C. Petit, F. Rodríguez-Henríquez, S. Schaeffler, and B. Wesolowski, *SQIsign*, Tech. report, National Institute of Standards and Technology, 2023, Version 1.0, available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/sqisign-spec-web.pdf.

[12] J. B. Conrey, M. A. Holmstrom, and T. L. McLaughlin, *Smooth neighbors*, Experimental Mathematics **22** (2013), no. 2, 195-202.

[13] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, *On the Lambert W function*, Advances in Computational mathematics **5** (1996), 329-359.

[14] M. Corte-Real Santos, J. K. Eriksen, M. Meyer, and K. Reijnders, *Aprèssqi: Extra fast verification for sqisign using extension-field signing*, EUROCRYPT, Lecture Notes in Computer Science, vol. 14651, Springer, 2024, pp. 63-93.

[15] M. Corte-Real Santos, J. K. Eriksen, M. Meyer, and F. Rodríguez-Henríquez, *Finding practical parameters for isogeny-based cryptography*, IACR Communications in Cryptology **1** (2024), no. 3.

[16] C. Costello, *B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion*, ASIACRYPT, Lecture Notes in Computer Science, vol. 12492, Springer, 2020, pp. 440-463.

[17] C. Costello, M. Meyer, and M. Naehrig, *Sieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott problem*, EUROCRYPT, Lecture Notes in Computer Science, vol. 12696, Springer, 2021, pp. 272-301.

[18] N. G. de Bruijn, *The asymptotic behaviour of a function occurring in the theory of primes*, Journal of the Indian Mathematical Society. New Series **15** (1951), 25-32.

[19] K. Dickman, *On the frequency of numbers containing prime factors of a certain relative magnitude*, Arkiv for matematik, astronomi och fysik **22** (1930), no. 10, A-10.

[20] L. Ducas, *Shortest vector from lattice sieving: a few dimensions for free*, EUROCRYPT, Lecture Notes in Computer Science, vol. 10820, Springer, 2018, pp. 125-145.

[21] L. Ducas, M. Stevens, and W. van Woerden, *Advanced lattice sieving on gpus, with tensor cores*, EUROCRYPT, Lecture Notes in Computer Science, vol. 12697, Springer, 2021, pp. 249-279.

[22] L. De Feo, D. Kohel, A. Leroux, C. Petit, and B. Wesolowski, *SQISign: compact post-quantum signatures from quaternions and isogenies*, ASIACRYPT, Lecture Notes in Computer Science, vol. 12491, Springer, 2020, pp. 64-93.

[23] L. De Feo, A. Leroux, P. Longa, and B. Wesolowski, *New algorithms for the Deuring correspondence - towards practical and secure SQISign signatures*, EUROCRYPT, Lecture Notes in Computer Science, vol. 14008, Springer, 2023, pp. 659-690.

[24] A. Granville, *Smooth numbers: computational number theory and beyond*, Algorithmic number theory: lattices, number fields, curves and cryptography **44** (2008), 267-323.

[25] D. H. Lehmer, *On a problem of Störmer*, Illinois Journal of Mathematics **8** (1964), no. 1, 57-79.

[26] A. K. Lenstra and H. W. Lenstra, *The development of the number field sieve*, Lecture Notes in Mathematics, vol. 1554, Springer Science & Business Media, 1993.

[27] A. Leroux, *Quaternion algebra and isogeny-based cryptography*, Theses, Ecole doctorale de l'Institut Polytechnique de Paris (2022).

[28] F. Luca and F. Najman, *On the largest prime factor of $x^2 - 1$, Mathematics of computation* **80** (2011), no. 273, 429-435.

[29] G. Martin, *An asymptotic formula for the number of smooth values of a polynomial*, Journal of Number Theory **93** (1999), 108-182.

[30] D. Micciancio and S. Goldwasser, *Complexity of lattice problems: a cryptographic perspective*, The Springer International Series in Engineering and Computer Science, vol. 671, Springer Science & Business Media, 2002.

[31] K. Nakagawa, H. Onuki, W. Castryck, M. Chen, R. Invernizzi, G. Lorenzon, and F. Vercauteren, *SQIsign2D-East: A new signature scheme using 2-dimensional isogenies*, ASIACRYPT, Lecture Notes in Computer Science, vol. 15486, Springer, 2024, pp. 272-303.

[32] C. P. Schnorr, *Factoring integers and computing discrete logarithms via diophantine approximation*, EUROCRYPT, Lecture Notes in Computer Science, vol. 547, Springer, 1991, pp. 281-293.
[33] C. P. Schnorr and M. Euchner, *Lattice basis reduction: Improved practical algorithms and solving subset sum problems*, Mathematical programming **66** (1994), 181–199.

[34] I Shparlinsky, *Integers with a large smooth divisor*, Electronic journal of combinatorial number theory **7** (2007).

[35] B. Sterner, *Towards optimally small smoothness bounds for cryptographic-sized smooth twins and their isogeny-based applications*, Selected Areas in Cryptography, Lecture Notes in Computer Science, vol. 15516, Springer, 2025, pp. 178–202.

[36] C. Størmer, *Quelques théorèmes sur l'équation de Pell $x^2 - dy^2 = \pm 1$ et leurs applications*, Christiania Videnskabens Selskabs Skrifter, Math. Nat. Kl (1897), no. 2, 48.

[37] J. van de Lune and E. Wattel, *On the numerical solution of a differential-difference equation arising in analytic number theory*, Mathematics of Computation **23** (1969), no. 106, 417–421.

[38] Z. Zhao, J. Ding, and B. Y. Yang, *Sieving with streaming memory access*, IACR Transactions on Cryptographic Hardware and Embedded Systems **2025** (2025), no. 2, 362–384.

## APPENDIX A. ASYMPTOTICS FOR THE GEOMETRIC MEAN OF THE LOGARITHMIC PRIMES

We provide an elementary proof of the following statement:

**Lemma A.1.** As $x \to \infty$ we have

$$ \prod_{p \le x} \log(p) = (\log(x) - 1 - o(1))^{\pi(x)}, $$

where the product is over the primes less than $x$.

*Proof.* We consider $\sum_{p \le x} \log(\log(p))$ which by Abel summation (or summation by parts) is

$$ \sum_{p \le x} \log(\log(p)) = \pi(x) \log(\log(x)) - \int_2^x \frac{\pi(t)}{t \log(t)} dt. $$

Using the prime number theorem in the integral term we have

$$ \begin{aligned} \int_2^x \frac{\pi(t)}{t \log(t)} dt &= \int_2^x \frac{t/\log(t) + O(t/\log^2(t))}{t \log(t)} dt \\ &= \int_2^x \left[ \frac{1}{\log^2(t)} + O\left(\frac{1}{\log^3(t)}\right) \right] dt \\ &= \frac{x}{\log^2(x)} + O\left(\frac{x}{\log^3(x)}\right) = \frac{\pi(x)}{\log(x)} + O\left(\frac{\pi(x)}{\log^2(x)}\right). \end{aligned} $$

So we have

$$ \sum_{p \le x} \log(\log(p)) = \pi(x) \left( \log(\log(x)) - \frac{1}{\log(x)} - O\left( \frac{1}{\log^2(x)} \right) \right) $$

and exponentiating gives

$$ \prod_{p \le x} \log(p) = \left( \log(x) \exp \left\{ -\frac{1}{\log(x)} - O\left(\frac{1}{\log^2(x)}\right) \right\} \right)^{\pi(x)}. $$

Finally, using the elementary fact that $e^{f(x)} = 1 + f(x) + o(1)$ when $f(x) = o(1)$, we obtain the intended result. □
<table><caption>**Table 3.** Largest strictly *B*-smooth twins for $127 \le B \le 547$, where they were found and our confidence in their optimality among the set of strictly *B*-smooth twins. We refer our optimality confidence as *strong* if it is above the estimate and simply *conjectured* if it lies on the estimate.</caption><thead><tr><th>B</th><th>r</th><th>Where</th><th>Optimality confidence</th></tr></thead><tbody><tr><td>127</td><td>53234795127882729824</td><td>[9]</td><td>Strong</td></tr><tr><td>131</td><td>4114304445616636016031</td><td>[9]</td><td>Strong</td></tr><tr><td>137</td><td>124225935845233319439173</td><td>[9]</td><td>Strong</td></tr><tr><td>139</td><td>348243554325338530939</td><td>Here</td><td>Strong</td></tr><tr><td>149</td><td>6418869735251219360209</td><td>[9]</td><td>Strong</td></tr><tr><td>151</td><td>5937710767815990134895</td><td>[9]</td><td>Strong</td></tr><tr><td>157</td><td>27129807647978258459761875</td><td>[9]</td><td>Strong</td></tr><tr><td>163</td><td>236092129213120444248216</td><td>Here</td><td>Strong</td></tr><tr><td>167</td><td>2730144006466475742187499</td><td>[9]</td><td>Strong</td></tr><tr><td>173</td><td>68832539267939977798585217</td><td>Here</td><td>Strong</td></tr><tr><td>179</td><td>93291810104851337149247</td><td>[9]</td><td>Strong</td></tr><tr><td>181</td><td>111363376732759509058791999</td><td>[9]</td><td>Strong</td></tr><tr><td>191</td><td>48052397088838594215891280</td><td>Here</td><td>Strong</td></tr><tr><td>193</td><td>41663827656330805415526399</td><td>Here</td><td>Strong</td></tr><tr><td>197</td><td>1768233329507766850247016575</td><td>Here</td><td>Strong</td></tr><tr><td>199</td><td>2252973514651334575995484575</td><td>Here</td><td>Strong</td></tr><tr><td>211</td><td>93902269999049136406357784</td><td>[9]</td><td>Conjected</td></tr><tr><td>223</td><td>8201296201736479132428107480</td><td>Here</td><td>Conjected</td></tr><tr><td>227</td><td>3752678821402907019077562900</td><td>[9]</td><td>Conjected</td></tr><tr><td>229</td><td>330882386435563679339125734371</td><td>Here</td><td>Conjected</td></tr><tr><td>233</td><td>5848334259354911158409294720</td><td>Here</td><td>Conjected</td></tr><tr><td>239</td><td>2622143744404213074275507412500</td><td>Here</td><td>Conjected</td></tr><tr><td>241</td><td>4628056410905928814029734098944</td><td>Here</td><td>Strong</td></tr><tr><td>251</td><td>592585561815510157202281925376</td><td>Here</td><td>Conjected</td></tr><tr><td>257</td><td>5559838662858616763776420328538775</td><td>Here</td><td>Strong</td></tr><tr><td>263</td><td>16172952549312489102079169991794</td><td>Here</td><td>Conjected</td></tr><tr><td>269</td><td>5175360440808596933703632663840</td><td>Here</td><td>Conjected</td></tr><tr><td>271</td><td>87929507961242828072747563801599</td><td>Here</td><td>Conjected</td></tr><tr><td>277</td><td>11568803308305983962724754825625</td><td>Here</td><td>Strong</td></tr><tr><td>281</td><td>92884898678862582897289179746549759</td><td>Here</td><td>Strong</td></tr><tr><td>283</td><td>3161718954986200183537251257791250</td><td>Here</td><td>Conjected</td></tr><tr><td>293</td><td>157148216359173408737214976695264</td><td>Here</td><td>Strong</td></tr><tr><td>307</td><td>8772167231265135880894204337250519</td><td>Here</td><td>Conjected</td></tr><tr><td>311</td><td>89443831930280392954450733255149999</td><td>Here</td><td>Strong</td></tr><tr><td>313</td><td>1389002392827843915483112680314149642</td><td>Here</td><td>Strong</td></tr><tr><td>317</td><td>180243795678197719372862505135757625</td><td>Here</td><td>Conjected</td></tr><tr><td>331</td><td>405235055486365672469126661251479124999</td><td>Here</td><td>Strong</td></tr><tr><td>337</td><td>85477499454961080411694536406997135</td><td>Here</td><td>Strong</td></tr><tr><td>347</td><td>7825271587408102011397171378934209695</td><td>Here</td><td>Conjected</td></tr><tr><td>349</td><td>66634945590443827011550630921860890624</td><td>Here</td><td>Conjected</td></tr><tr><td>353</td><td>35408140740413063652393523840533059375</td><td>Here</td><td>Conjected</td></tr><tr><td>359</td><td>263455432747659210060186232546956249</td><td>Here</td><td>Strong</td></tr><tr><td>367</td><td>675061621595239219713254605179783856148</td><td>Here</td><td>Conjected</td></tr><tr><td>373</td><td>3080523132525564477025145487317299374</td><td>Here</td><td>Conjected</td></tr><tr><td>379</td><td>41429044413844360175142847690761212415</td><td>Here</td><td>Strong</td></tr><tr><td>383</td><td>109700462541349693230774237216752511659775</td><td>Here</td><td>Strong</td></tr><tr><td>389</td><td>26251549205868140750016147797867134975</td><td>Here</td><td>Strong</td></tr><tr><td>397</td><td>48513551816873021796145948442762858579489</td><td>Here</td><td>Conjected</td></tr><tr><td>401</td><td>1108736175300558453046228340766437576703</td><td>Here</td><td>Strong</td></tr><tr><td>409</td><td>271834242832551380963119342533180653567</td><td>Here</td><td>Strong</td></tr><tr><td>419</td><td>13087493037557955170005751424386725924956</td><td>Here</td><td>Strong</td></tr><tr><td>421</td><td>21751470813972355927816959692101220811249</td><td>Here</td><td>Strong</td></tr><tr><td>431</td><td>10394361802587451964305517345060821862807</td><td>Here</td><td>Conjected</td></tr><tr><td>433</td><td>23887759897295124307321927477187246681477375</td><td>Here</td><td>Strong</td></tr><tr><td>439</td><td>110696280715958686247092176796896376308495</td><td>Here</td><td>Conjected</td></tr><tr><td>443</td><td>12703939878820449536208758637662441491160</td><td>Here</td><td>Strong</td></tr><tr><td>449</td><td>922419153215099188628203822871162545639424</td><td>Here</td><td>Conjected</td></tr><tr><td>457</td><td>100219012203867604301812073658057115196348124</td><td>Here</td><td>Conjected</td></tr><tr><td>461</td><td>3422111828214075376631678360763021667377120</td><td>Here</td><td>Strong</td></tr><tr><td>463</td><td>1883915780273552168108746051993230463476639</td><td>Here</td><td>Strong</td></tr><tr><td>467</td><td>839328399233789967915303395265005287676198124</td><td>Here</td><td>Strong</td></tr><tr><td>479</td><td>873921852842838203186240292400433354544</td><td>Here</td><td>Strong</td></tr><tr><td>487</td><td>25875182880632028107739429394848525297803007</td><td>Here</td><td>Strong</td></tr><tr><td>491</td><td>2423604524745690031304438266262129360000000</td><td>Here</td><td>Strong</td></tr><tr><td>499</td><td>178906349213593152248817474720832242569815163684</td><td>Here</td><td>Strong</td></tr><tr><td>503</td><td>151014857405244045031959958774399184138093696</td><td>Here</td><td>Strong</td></tr><tr><td>509</td><td>42889659586515527948353985751885587691246547968</td><td>Here</td><td>Conjected</td></tr><tr><td>521</td><td>743036103216222378196724920946486197247016960</td><td>Here</td><td>Strong</td></tr><tr><td>523</td><td>1621772139546094952834968552508554362980292519</td><td>Here</td><td>Strong</td></tr><tr><td>541</td><td>12337643614378538072574917289230058709828652400</td><td>Here</td><td>Strong</td></tr><tr><td>547</td><td>54402483212060891755452764781276292632569951935</td><td>Here</td><td>Strong</td></tr></tbody></table>
# APPENDIX B. LARGEST KNOWN B-SMOOTH TWINS FOR $113 < B < 500$

In Table 3 we list the known largest B-smooth twins for $113 < B < 500$, stating
where they were found and whether or not we think they are optimal.

NIJMEGEN, THE NETHERLANDS

*Email address: erik-baltasar@live.nl*

INRIA AND ÉCOLE POLYTECHNIQUE, INSTITUT POLYTECHNIQUE DE PARIS, PALAISEAU, FRANCE

*Email address: bruno-sydney.sterner@inria.fr*

PQSHIELD, AMSTERDAM, THE NETHERLANDS

*Email address: wessel.vanwoerden@pqshield.com*