Sieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott problem

We give a sieving algorithm for finding pairs of consecutive smooth numbers that utilizes solutions to the Prouhet-Tarry-Escott (PTE) problem. Any such solution induces two degree-\(n\) polynomials, \(a(x)\) and \(b(x)\), that differ by a constant integer \(C\) and completely split into linear factors in \(\Z[x]\). It follows that for any \(\ell \in \Z\) such that \(a(\ell) \equiv b(\ell) \equiv 0 \bmod{C}\), the two integers \(a(\ell)/C\) and \(b(\ell)/C\) differ by 1 and necessarily contain \(n\) factors of roughly the same size. For a fixed smoothness bound \(B\), restricting the search to pairs of integers that are parameterized in this way increases the probability that they are \(B\)-smooth. Our algorithm combines a simple sieve with parametrizations given by a collection of solutions to the PTE problem.

The motivation for finding large twin smooth integers lies in their application to compact isogeny-based post-quantum protocols. The recent key exchange scheme B-SIDH and the recent digital signature scheme SQISign both require large primes that lie between two smooth integers; finding such a prime can be seen as a special case of finding twin smooth integers under the additional stipulation that their sum is a prime \(p\).

When searching for cryptographic parameters with \(2^{240} \leq p <2^{256}\), an implementation of our sieve found primes \(p\) where \(p+1\) and \(p-1\) are $2^{15}$-smooth; the smoothest prior parameters had a similar sized prime for which \(p-1\) and \(p+1\) were $2^{19}$-smooth. In targeting higher security levels, our sieve found a 376-bit prime lying between two $2^{21}$-smooth integers, a 384-bit prime lying between two $2^{22}$-smooth integers, and a 512-bit prime lying between two $2^{29}$-smooth integers. Our analysis shows that using previously known methods to find high-security instances subject to these smoothness bounds is computationally infeasible.