The problem of finding a low-weight multiple of a polynomial is of great importance in the field of cryptography. Some applications are distinguishing and correlations attacks on stream ciphers. Another area is finite-field arithmetic.

We define problem as follows. Given a polynomial P(x), find another polynomial u(x) such that the resulting product has low weight (or consists of few terms).

It is not known exactly how hard the problem over 𝔽₂ is, but it is believed to be hard. One simple reduction is to represent the polynomial as a linear code and finding a minimum-weight codeword using information-set decoding. Other methods such as time--memory trade-offs are applicable as well as k-sum algorithms. Also memory-less constructions are possible. Such an algorithm is possible by defining two functions f and g, that act in any input as a random oracle to ℤ_m, where m is close to the degree of K(x). Then, a cycle-finding algorithm can be run for the recursion y = x^f(y) + x^g(y). When the two runners collide, there are two values y and y' such that x^f(y) + x^g(y) = x^f(y') + x^g(y') which gives the exponents for the multiple K(x) if y ≠ y'.

For the case w = 4, a 4-sum algorithm (generalized-birthday algorithm) is used. By extending the range from 2^d/3 to 2^{d/3 + α}, the probability increases considerably. To see this, assume that K(x) = xⁱ + x^j + x^k + x^l has degree m = 2^d/3. By the extension of the range, there are N = 2^{d/3 + α} - 2^d/3 = 2^d/3 ( 2^α - 1) shifts of the form xⁱ K(x) in this set. Using a mask (defined as the function φ) of weight d/3, the probability that φ (xⁱ + x^j) = 0 is 2^-d/3, and φ (x^k + x^l) = 0 follows by definition. Since this is repeated for all N shifts, the probability that one passes through the filter is overwhelmingly large.

The implementation is a threaded and scalable to up arbitrarily many cores. It is also constructed in a way such that mutexes are not needed.