Welcome to the resource topic for 2020/1283
Title:
Sieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott problem
Authors: Craig Costello, Michael Meyer, 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. 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^{28}-smooth integers. Our analysis shows that using previously known methods to find high-security instances subject to these smoothness bounds is computationally infeasible.
ePrint: https://eprint.iacr.org/2020/1283
Talk: https://www.youtube.com/watch?v=Dn5ajBJkyMM
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .