Fast computation of permanents over F₃ via F₂ arithmetic

We present a method of representing an element of F₃ⁿ as an element of Fₙ² × Fₙ² which in practice will be a pair of unsigned integers. We show how to do addition, subtraction and pointwise multiplication and division of such vectors quickly using primitive binary operations (and, or, xor). We use this machinery to develop a fast algorithm for computing the permanent of a matrix in F₃n× n. We present Julia code for a natural implementation of the permanent and show that our improved implementation gives, roughly, a factor of 80 speedup for problems of practical size. Using this improved code, we perform Monte Carlo simulations that suggest that the distribution of perm(A) tends to the uniform distribution as n → ∞.