How to perform bitwise XOR by rational function modulo $2^n$?

Unless I have a bug in my Haskell script below, your problem has no solution for $n>3$. For $n=4$ it finds the solution for the lowest 3 bits, but fails then for 96 pairs $(x, y)$.

As I commented earlier, it's enough to look at polynomials, so I restricted myself to these. For bitlength $n$, the $n$-th power of any even number is $0\bmod 2^n$, and the exponent of the multiplicative group $(\mathbb{Z}/\mathbb{Z}_{2^n})^\times$ is $2^{n-2}$, i.e., $x^{2^{n-2}} = 1\bmod 2^n$ for odd $x$. Hence for $n>3$ we have $x^e = x^{e+2^{n-2}} \bmod 2^n$ for $e\ge n$, and we can restrict our attention to monomials $X^l\cdot Y^k$ with $k, l < n+2^{n-2}$. Your question is equivalent to the existence of a solution $(a_{k,l})$ of

(*) $x\oplus y = \sum_{0\le k, l<n+2^{n-2}} a_{k,l}\cdot x^k\cdot y^l \bmod 2^n$ for all $0\le x, y<2^n$

When adding $\bmod 2^n$ the lower bits influence the higher bits via the carry, but the result $\bmod 2^k$ for $k<n$ depends only on the inputs $\bmod 2^k$ and not on the higher bits. Hence one can solve (*) bit for bit from the lowest bit to the highest bit, i.e., first $\bmod 2$, then $\bmod 2^2, \dots, \bmod 2^n$. In each step one has to solve a linear equation system over the field $\mathbb{F}_2$ with two elements, and use the solution to set up the linear equation system for the next step. For my program I preferred to split the coefficients of the terms $a_{k,l}\cdot x^k\cdot y^l$ in its bits, i.e., $a_{k,l} = \sum_{0\le i<n} a_{k,l,i}$, which you will find as triplets $(k,l,s)$ in my code.

import Data.Bits ((.&.), xor, bit, testBit, shiftL, countTrailingZeros) import Data.List (partition, sort) import Debug.Trace (traceShow) import System.Environment (getArgs) -- try to find solution for this many bits bitDepth = 4 -- the triple (k, l, s) corresponds to the monomial 2^s*X^k*Y^l -- evaluate at point (x, y) the monomial X^k*Y^l shifted s bits left eval :: Int -> Int -> (Int, Int, Int) -> Int eval x y (k, l, s) = shiftL (x^k*y^l) s -- list of triples correspond to the sum of its elements -- eval' sums up results of eval over a list of triples eval' :: Int -> Int -> [(Int, Int, Int)] -> Int eval' x y ps = sum [eval x y p | p <- filter (\(_, _, s) -> s>=0) ps] -- use all terms of maximal degree n with maximal shift m-1 terms n m = [[(k, d-k, s)] | d <- [1..n], k <- [0..d], s <- [0..m-1]] -- given the function f, zero the bit position b at the value (x, y) -- for f minus the approximation a given as list of triples using -- the list ts of lists of triples as possible summands -- returning -- the updated list ts' of lists of triples with bit b zero at (x, y) -- paired with the updated approximation a' of f that matches this bit -- (if no solution exists, a dummy with negative shift is inserted to -- indicate the failing positions) solveAt :: (Int -> Int -> Int) -> Int -> (Int, Int) -> ([[(Int, Int, Int)]], [(Int, Int, Int)]) -> ([[(Int, Int, Int)]], [(Int, Int, Int)]) solveAt f b (x, y) (ts, a) | testBit v b && null zs = dummy | testBit v b = (cs, compress $ a ++ head zs) | otherwise = (cs, a) where (ys, zs) = span (not.flip testBit b.eval' x y) ts cs | null zs = ys | otherwise = ys ++ map g (tail zs) g z | testBit (eval' x y z) b = cut.compress $ head zs ++ z | otherwise = z v = f x y - eval' x y a dummy = (cs, (x, y, -b-1):a) -- failure at (x, y) for bit b -- solveLayer calls solveAt at all possible points (x, y) for bit b solveLayer f s b = flip (foldr (solveAt f b)) xys where xys = [(x, y) | x <- [0..bit s-1], y <- [0..bit s-1]] -- auxiliary function summing up two terms 2^s*X^l*Y^k to 2^(s+1)*X^l*Y^k compress' :: [(Int, Int, Int)] -> [(Int, Int, Int)] compress' [] = [] compress' [a] = [a] compress' (a@(k, l, s):b:as) | a == b = compress $ (k, l, s+1):as | a /= b = a:compress' (b:as) compress :: [(Int, Int, Int)] -> [(Int, Int, Int)] compress [] = [] compress [a] = [a] compress as = compress' $ sort as -- auxiliary function for removing terms 2^s*X^l*y^k with s>=bitDepth cut = filter (\(k, l, s) -> s<bitDepth) -- auxiliary function to check result test f b ps = all (\(x, y) -> f x y == mod (eval' x y ps) (2^b)) xys where xys = [(x, y) | x <- [0..bit b-1], y <- [0..bit b-1]] -- usage: only parameter gives maximal degree of monomials to use main = do ns <- getArgs let n = read $ head ns let sl = solveLayer xor bitDepth let res = cut.compress.snd.sl 3.sl 2.sl 1 $ sl 0 (terms n bitDepth, []) print $ length $ filter (\(_, _, b) -> b<0) res print $ filter (\(_, _, b) -> b<0) res print $ length $ filter (\(_, _, b) -> b>=0) res print $ filter (\(_, _, b) -> b>=0) res print $ test xor 3 $ filter (\(_, _, b) -> b>=0) res print $ test xor 4 $ filter (\(_, _, b) -> b>=0) res {- -- for trying symmetric monomials only, replace upper functions by: eval x y (d, k, s) | d == 2*k = shiftL ((x*y)^k) s | otherwise = shiftL (x^k*y^(d-k) + x^(d-k)*y^k) s terms n m = [[(d, k, s)] | d <- [1..n], k <- [0..div d 2], s <- [0..m-1]] -} 

I cannot say this is impossible but I think it would be very difficult. There may be people here who know more about multivariate polynomial and rational representations, Grobner basis, etc.

Some reasons I can see are

1. The structure you are looking at has zero divisors (can have $ab\equiv 0\pmod{2^t}$ with both nonzero.
2. Thus polynomial representation is not unique
3. Looking at the structure of the XOR function you will need step functions on the halves to represent it, but such functions are quite difficult to represent as polynomials over the integers modulo $2^n,$ since they need to specified at every single point, leading to large degree polynomials, and such polynomials will cease to be one to one due to pigeonhole principle.

Here is the operation table for 2 bit XOR. You will notice that the first term in the additive representation is just the $2\times 2$ antidiagonal matrix matrix repeated and the $2\times 2$ all 1 matrix premultiplied by 2 and added in antidiagonal fashion. $$ \left[\begin{array}{cccc} 0 & 1 & 2 & 3\\ 1 & 0 & 3 & 2 \\ 2 & 3 & 0 & 1\\ 3 & 2& 1& 0 \end{array} \right]= \left[\begin{array}{cccc} 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1\\ 1 & 0& 1& 0 \end{array} \right]+ \left[\begin{array}{cccc} 0 & 0 & 2 & 2\\ 0 & 0 & 2 & 2 \\ 2 & 2 & 0 & 0\\ 2 & 2& 0& 0 \end{array} \right]$$ This repeats for the next operation table recursively, now antidiagonal all 1's multiplied by 4 and added.

I suppose this is a kind of module structure, but I'm not sure how useful that would be. One way to proceed might be to use a larger integer ring which gives the correct representation on integers modulo $2^t.$