Paper 2025/1462

Large smooth twins from short lattice vectors

Bruno Sterner, Inria Saclay - Île-de-France Research Centre, University of Waterloo

Wessel van Woerden, PQShield

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 \leq 100$ and heuristically for $100 < B \leq 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.

@misc{cryptoeprint:2025/1462,
      author = {Erik Mulder and Bruno Sterner and Wessel van Woerden},
      title = {Large smooth twins from short lattice vectors},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1462},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1462}
}