Cryptology ePrint Archive: Report 2020/1283

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

Craig Costello and Michael Meyer and Michael Naehrig

Abstract: 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 $\mathbb{Z}[x]$. It follows that for any $\ell \in \mathbb{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.

Category / Keywords: public-key cryptography / Post-quantum cryptography, isogeny-based cryptography, Prouhet-Tarry-Escott problem, twin smooth integers, B-SIDH, SQISign

Date: received 14 Oct 2020

Contact author: michael meyer at hs-rm de

Available format(s): PDF | BibTeX Citation

Version: 20201014:182723 (All versions of this report)

Short URL: ia.cr/2020/1283