Welcome to the resource topic for 2022/1113
Title:
A new algorithm for solving the rSUM problem
Authors: Valerii Sopin
Abstract:A determined algorithm is presented for solving the rSUM problem for any natural r with a sub-quadratic assessment of time complexity in some cases. In terms of an amount of memory used the obtained algorithm is the nlog^3(n) order.
The idea of the obtained algorithm is based not considering integer numbers, but rather k (is a natural) successive bits of these numbers in the binary numeration system. It is shown that if a sum of integer numbers is equal to zero, then the sum of numbers presented by any k successive bits of these numbers must be sufficiently “close” to zero. This makes it possible to discard the numbers, which a fortiori, do not establish the solution.
ePrint: https://eprint.iacr.org/2022/1113
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 .