Paper 2026/1664 Original: eprint.iacr.org/2026/1664 ↗

Deterministic Partial Algorithms for Matrix-Space Conjugacy over Finite Fields

Abstract

Given two ordered families of square matrices over a finite field, we seek an ambient conjugation and an invertible mixing of the family that carry one input to the other. The matrices need not be linearly independent. We give deterministic partial algorithms in an explicit finite-field model: source-side recognition certifies completeness against every target, and every returned transporter is verified. For a matrix space with nondegenerate trace pairing, two successive orthogonal projections produce an intrinsic matrix pair. A characteristic-wise nonzero polynomial certificate gives source density at least $1-(6n^2-4)s/q-2/q^3$, where $n\geq 3$ is the matrix size, $2\leq m\leq n^2-2$ is the number of slices, and $s=\min\{m,n^2-m\}$. Thus the density tends to one whenever $n^2s=o(q)$. A complementary one-dimensional-hull construction, together with low-dimensional and endpoint solvers, gives a recognized source family of iid-uniform mass greater than $9/(1216q)$ for every prime power $q$ and all positive $n,m$. Both algorithms have bit complexity polynomial in $n,m,\log q$. An image-and-kernel lift recovers the declared coefficient action, including dependent presentations. We separate the exceptional odd-characteristic two-by-two case and the arithmetic limitations of higher-moment constructions from the universal partial guarantee.