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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.