# Finding twin smooth integers by solving Pell equations

Jan Buzek, Junaid Hasan, Jason Liu, Michael Naehrig, Anthony Vigil

Submitted on 8 November 2022

## Abstract

Any pair of consecutive B-smooth integers for a given smoothness bound B
corresponds to a solution (x, y) of the equation x^2 - 2Dy^2 = 1 for a certain
square-free, B-smooth integer D and a B-smooth integer y. This paper describes
algorithms to find such twin B-smooth integers that lie in a given interval by
using the structure of solutions of the above Pell equation. The problem of
finding such twin smooth integers is motivated by the quest for suitable
parameters to efficiently instantiate recent isogeny-based cryptosystems. While
the Pell equation structure of twin B-smooth integers has previously been used
to describe and compute the full set of such pairs for very small values of B,
increasing B to allow for cryptographically sized solutions makes this approach
utterly infeasible. We start by revisiting the Pell solution structure of the
set of twin smooth integers. Instead of using it to enumerate all twin smooth
pairs, we focus on identifying only those that lie in a given interval. This
restriction allows us to describe algorithms that navigate the vast set of Pell
solutions in a more targeted way. Experiments run with these algorithms have
provided examples of twin B-smooth pairs that are larger and have smaller
smoothness bound B than previously reported pairs. Unfortunately, those
examples do not yet provide better parameters for cryptography, but we hope
that our methods can be generalized or used as subroutines in future work to
achieve that goal.