How to reverse this bitwise AND-XOR encoding algorithm? I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode that uses bit arrays (1-indexed):
N is a power of 2 strictly greater than 1.

encode(A : Array of N bits) -> B : Array of N bits

// Split the input into two halves.
    Var A1 : Array of N/2 bits := A[1 .. N/2]
    Var A2 : Array of N/2 bits := A[N/2+1 .. N]

// Initialize the result with all bits to zero.
    For k from 1 to N
        B[k] := 0

// Do the work.
    For i from 1 to N/2
        For j from 1 to N/2
            B[i+j] := B[i+j] XOR (A1[i] AND A2[j])

    Return B

For illustration, here's a "live" C++ program: http://ideone.com/NBGGPS

For example I have unrolled it for N = 8, then B is like this (symbols: & for AND, ^ for XOR):

B[1] = 0
B[2] = (A1[1] & A2[1])
B[3] = (A1[1] & A2[2]) ^ (A1[2] & A2[1])
B[4] = (A1[1] & A2[3]) ^ (A1[2] & A2[2]) ^ (A1[3] & A2[1])
B[5] = (A1[1] & A2[4]) ^ (A1[2] & A2[3]) ^ (A1[3] & A2[2]) ^ (A1[4] & A2[1])
B[6] =                   (A1[2] & A2[4]) ^ (A1[3] & A2[3]) ^ (A1[4] & A2[2])
B[7] =                                     (A1[3] & A2[4]) ^ (A1[4] & A2[3])
B[8] =                                                       (A1[4] & A2[4])

That resembles a system of N equations with N variables (knowing that for bits a XOR b = (a &plus; b) mod 2 and a AND b = (a × b) mod 2 = a × b):
$$\begin{eqnarray}
b_1 & = & 0             &   &                &   &               &   &               &         \\
b_2 & = & x_1 \cdot x_5 &   &                &   &               &   &               &         \\
b_3 & = & x_1 \cdot x_6 & + & x_2 \cdot x_5  &   &               &   &               & \pmod 2 \\
b_4 & = & x_1 \cdot x_7 & + & x_2 \cdot x_6  & + & x_3 \cdot x_5 &   &               & \pmod 2 \\
b_5 & = & x_1 \cdot x_8 & + & x_2 \cdot x_7  & + & x_3 \cdot x_6 & + & x_4 \cdot x_5 & \pmod 2 \\
b_6 & = &               &   & x_2 \cdot x_8  & + & x_3 \cdot x_7 & + & x_4 \cdot x_6 & \pmod 2 \\
b_7 & = &               &   &                &   & x_3 \cdot x_8 & + & x_4 \cdot x_7 & \pmod 2 \\
b_8 & = &               &   &                &   &               &   & x_4 \cdot x_8 &         \\
\end{eqnarray}$$

Some (informal) thoughts:


*

*It is kind of "symmetric": you get the same result if you swap the two halves of A.

*I have seen examples that you can get the same result for several different inputs ("different" not only by symmetry), so it is "lossy".

*It looks like a "keyless XOR encryption" (well, not sure this one even makes sense...).



Now the challenge is to "reverse" it, i.e. to write some decoding algorithm such that decode( encode(A) ) = A.
But after bullet 2 above (and also 1) we know that the solution is not unique, so we must rather find one possible solution such that encode( decode_one( encode(A) ) ) = encode(A), or maybe we can find all possible solutions i.e. an algorithm such that decode_all( encode(A) ) = { X | encode(X) = encode(A) }.
(Of course "brute force" is not interesting.)
Now I'm just completely stuck on that... For example, if B[2] = 1 then I know that both A1[1] and A2[1] are 1, but if B[2] = 0 then I can only say that A1[1] and A2[1] are not both 1 (they could be both 0, or one 0 and the other 1). Then for B[3] the XOR comes in and multiplies the possibilities...
I tried to somehow "combine" several equations from the unrolling but it's not linear.

What would be the way to go?
(Also feel free to edit the post e.g. to add relevant tags.)
 A: Encryption:
What your equation system shows is that the encryption is equivalent to multiplying two polynomials of degree N/2 on GF(2) (algebra of two elements {1,0} where 1+1=0, that is to say + = XOR).
"Proof":
Let A1 be an array of the coefficients of A1: $A1[1]\times x^0+A1[2]\times x^1+A1[3]\times x^2+...$
Same goes for A2
Let B be the product polynomial of $B=A1\times A2$
Polynomial multiplication gives you:
$B=(A1[1]\times x^0+A1[2]\times x^1+A1[3]\times x^2+...)\times(A2[1]\times x^0+A2[2]\times x^1+A2[3]\times x^2+...)$
$B=(A1[1]\times A2[1]\times x^0+(A1[2]\times A2[1]+A2[2]\times A1[1])\times x^1+...)$
In general $B[i]=Sum(A1[n]\times A2[l],n+l==i+1)$   (%2 because of GF(2))
You wrote:
$B[5] = (A1[1] & A2[4]) ^ (A1[2] & A2[3]) ^ (A1[3] & A2[2]) ^ (A1[4] & A2[1])$
This is exactly the previous formula for i=4, you have $B[1]=0$ so there's a shift: your $B[5]$ is the coefficient in front of x^3.
Decryption:
If the encryption is polynomial multiplication of two polynomials of degree N/2, the decryption is polynomial factorisation into two parts of degree less than N/2. This can be done with the Berlekamp Algorithm or Cantor–Zassenhaus Algorithm
Note these algorithms will work because we are on a finite field GF(2) where the coefficients have finite possible values.
