Paper 2025/1462
Large smooth twins from short lattice vectors
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Minor revision. ANTS XVII
- Keywords
- Smooth integerSmooth twinLatticeSVPIsogenySQIsign
- Contact author(s)
-
erik mulder @ uib no
bsterner @ uwaterloo ca
wessel vanwoerden @ pqshield com - History
- 2026-06-18: last of 2 revisions
- 2025-08-12: received
- See all versions
- Short URL
- https://ia.cr/2025/1462
- License
-
CC0
BibTeX
@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}
}
