Sieving for Twin Smooth Integers with Solutions to the Prouhet-Tarry-Escott Problem - Costello, Craig; Meyer, Michael; Naehrig, Michael (EUROCRYPT 2021, 2021)
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 \([Z][x]\). It follows that for any \([Z]\) such that \(a() b() 0 [C]\), the two integers \(a()/C\) and \(b()/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.