We exhibit an explicit, deterministic algorithm for finding a canonical form for a positive definite matrix under unimodular integral transformations. We use characteristic sets of short vectors and partition-backtracking graph software. The algorithm runs in a number of arithmetic operations that is exponential in the dimension n, but it is practical and more efficient than canonical forms based on Minkowski reduction.

, , , ,
doi.org/10.2140/obs.2020.4.179
The Open Book Series
14th Algorithmic Number Theory Symposium
Cryptology

Dutour Sikirić, M, Haensch, A, Voight, J, & van Woerden, W.P.J. (2020). A canonical form for positive definite matrices. In Proceedings of the 14th Algorithmic Number Theory Symposium, ANTS-XIV (pp. 179–195). doi:10.2140/obs.2020.4.179