Cryptology: Dictionary of Bit Vectors

[JoGu]

Cryptology

Dictionary of Bit Vectors

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

A bit vector (b₁, ..., b_n) has the following interpretations:

an element of the F₂-vectorspace F₂ⁿ,
a bitstring of length n,
a natural number between 0 and 2ⁿ-1 in binary representation
a subset of {1, ..., n},
a linear form on F₂ⁿ, expressed as sum of the coordinate projections T_i where the coefficient b_i = 1,
a monomial in n indeterminates T₁, ..., T_n.

[Of course there are other possible interpretations—every information has a binary encoding.]

The following table shows these interpretations for the bit vectors of length n = 4:

Number	Bitstring	(hexadecimal)	Subset	Linear form	Monomial
0	0000	0	Ø	0	1
1	0001	1	{4}	T₄	T₄
2	0010	2	{3}	T₃	T₃
3	0011	3	{3,4}	T₃+T₄	T₃T₄
4	0100	4	{2}	T₂	T₂
5	0101	5	{2,4}	T₂+T₄	T₂T₄
6	0110	6	{2,3}	T₂+T₃	T₂T₃
7	0111	7	{2,3,4}	T₂+T₃+T₄	T₂T₃T₄
8	1000	8	{1}	T₁	T₁
9	1001	9	{1,4}	T₁+T₄	T₁T₄
10	1010	A	{1,3}	T₁+T₃	T₁T₃
11	1011	B	{1,3,4}	T₁+T₃+T₄	T₁T₃T₄
12	1100	C	{1,2}	T₁+T₂	T₁T₂
13	1101	D	{1,2,4}	T₁+T₂+T₄	T₁T₂T₄
14	1110	E	{1,2,3}	T₁+T₂+T₃	T₁T₂T₃
15	1111	F	{1,2,3,4}	T₁+T₂+T₃+T₄	T₁T₂T₃T₄

Or, to express it by a picture for an example:

[Interpretations of a bitblock]

Author: Klaus Pommerening, 2005-Aug-03; last change: 2021-Feb-01.