# Hamming Weight of Solutions to the Frobenius Equation

My area of research is algorithms for calculating optimal addition chains. I have a new high performance algorithm that at its core benefits from estimating the number of set bits ($$v(n)$$ Hamming weight) in a solution to the Frobenius equation. So for example with a given $$n$$ and $$a_i\geq 1$$ if

$$n=\sum_{i=1}^z a_i x_i,\ x_i\geq1$$

Then if I can bound $$\max_{i=1}^z v(x_i)$$ from below it makes a huge impact on the performance.

To my untrained eye this seems like something that might come up in cryptography. Trying to extract information about a pre-image from the image. I my case the number of set bits.

We can cleary use a simple bit counting technique as a first level:

$$\max_{i=1}^{z}v(x_{i})\geq\left\lceil \frac{v(n)}{\sum_{i=1}^{z}v(a_{i})}\right\rceil$$

Magically though (and I hope people have seen something similar to this) we can generalize this to:

$$\max_{i=1}^{z}v(x_{i})\geq\left\lceil \frac{v(n\bmod m)}{\sum_{i=1}^{z}v(a_{i}\bmod m)}\right\rceil ,\,m=2^{j}-2^{k},\,j>k$$

Here $$n\bmod m$$ is the least non-negative value from the residue class of $$n$$ modulo $$m$$.

You can do this because unexpectedly (to me at least) $$v(n\bmod(2^{i}-2^{j}))\leq v(n),\,i>j$$.

I have only gotten performance increases currently for when $$m=2^j-2^{j-1}=2^{j-1}$$. Essentially looking at a window of bits.

It's also possible to multiply both sides of the Frobenius equation by a constant in the hopes that the bit counts on each side allow you to infer a greater lower bound:

$$\max_{i=1}^{z}v(x_{i})\geq\left\lceil \frac{v(nm)}{\sum_{i=1}^{z}v(a_{i}m)}\right\rceil$$

I only see performance increase with $$m=3$$ currently. Does this sort of thing come up in cryptography? Are their known techniques for say following the bits through multiplies etc? Obviously I would like to get some root property of the bits in the $$a_i$$ and $$n$$ to go more directly to the lower bounds for the bits in the $$x_i$$.