Welcome to the resource topic for 2023/219
Title:
Sieving for large twin smooth integers using single solutions to Prouhet-Tarry-Escott
Authors: Knud Ahrens
Abstract:In the isogeny-based track of post-quantum cryptography the signature scheme SQISign relies on primes p such that p\pm1 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 one 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 bigger 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 optimised for the corresponding C and allows to only sieve 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.
ePrint: https://eprint.iacr.org/2023/219
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 .