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

Source abstract

In the isogeny-based track of post-quantum cryptography, optimal instances of the signature scheme SQISign rely on primes $p$ such that $p \pm 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 (checking a single solution at a time) fades. For a single PTE solution the search can be optimized for the corresponding $C$ and allows 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. Accepted: 12 March 2026