Finding number of certain strings in the group of 2N-bit strings

Revision en2, by egor_bb, 2021-12-26 04:49:40

Hi! There is a practical problem that reduces to the following:

You are given some 2N-bit strings that generate a group with XOR operation (subgroup of all 2N-bit strings). The goal is to find the number of elements in the group satisfying the following property in any reasonable time:

  • Split the 2N-bit string into N pairs of adjacent bits, for example $$$01111011 > (01)(11)(10)(11)$$$
  • The number of $$$(11)$$$ pairs should be odd (in the example there are two such pairs, so we don’t count it)

The faster the better, but ideas on speeding up the brute force are also welcome. I’m stuck at the moment and don’t even understand how to Google it properly :(


  Rev. Lang. By When Δ Comment
en2 English egor_bb 2021-12-26 04:49:40 2
en1 English egor_bb 2021-12-26 04:49:12 727 Initial revision (published)