The Exact Multiplicative Complexity of the Hamming Weight Function

Joan Boyar; rene peralta

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR05-049 | 1st April 2005 00:00

The Exact Multiplicative Complexity of the Hamming Weight Function

TR05-049 Authors: Joan Boyar, rene peralta
Publication: 26th April 2005 01:28
Downloads: 2956

Keywords:

circuit complexity, cryptographic proofs, Hamming weight, multiplicative complexity, symmetric functions

Abstract:

We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for GF2 addition and multiplication only. We show the number of multiplications necessary and sufficient to build such a circuit is n - |n| where |n| is the Hamming weight of the binary representation of n.

ISSN 1433-8092 | Imprint