Sieving for large twin smooth integers using single solutions to Prouhet-Tarry-Escott

Abstract

In the isogeny-based track of post-quantum cryptography, optimal instances of the signature scheme SQISign rely on primes p such that p ± 1 is smooth. In 2021, a new approach to find those numbers was discovered using solutions to the Prouhet-Tarry-Escott (PTE) problem. With these solutions, we can sieve for smooth integers A and B with a difference of |A − B| = C fixed by the solution. Then some 2A/C and 2B/C are smooth integers hopefully enclosing a prime.

They took many different PTE solutions and combined them into a tree to process them more efficiently. But for larger numbers, there are fewer promising PTE solutions, so their advantage over the naive approach, namely checking a single solution at a time, fades. For a single PTE solution, the search can be optimized for the corresponding C and allows one to check smoothness only for those integers that are divisible by C. In this work, we investigate such optimisations and show a significant speed-up compared to the naive approach, both heuristically and empirically. Along the way, we compute the number of roots of a given polynomial modulo prime powers and give an upper bound for the number of roots modulo a composite number.