Affine Fibers and a Fibonacci Bound for Boolean–Modular Inversion

Let L be any invertible binary-linear map on w-bit words. We give a disjoint affine decomposition of every fiber of L(a+D)+L(a)=S modulo 2^w. Each feasible XOR signature reduces both modular additions to exact linear mask constraints over GF(2). Two carry automata enumerate the input and output signatures, and the algorithm uses the smaller list. Each list has at most F_(w+1) entries, where F denotes the Fibonacci sequence; this bound is attained for signature enumeration. The resulting compact-output algorithm has a conservative O(w^3 F_(w+1)) bit-operation bound. Two target classes give a single affine cell with an explicit dimension. The manuscript includes proofs, a worked five-cell example, and an executable whole-fiber verifier.