Solving Binary Linear Equation Systems over the Rationals and Binaries

Benedikt Driessen, Chris­tof Paar

International Workshop on the Arithmetic of Finite Fields (Bochum) 2012


This paper presents intermediate results of our investigations into the potential of analog hardware for the purpose of solving linear equation (LES) systems which are of quadratic form and binary. Based on the assumption that we can efficiently solve binary LES over the rationals with sufficient precision, we present a generic method to map a rational solution to a solution which solves the equation system over F2. We show that, in order to perform this mapping, we only need to look at two bits of the binary expansion of each of the elements of the rational solution vector.

[Waifi 2012] [pdf] [bib]

Tags: Binaries, binary, Equation, Linear, Rationals, Solving, systems