Computing the $p$-adic Canonical Quadratic Form in Polynomial Time

Abstract

An $n$-ary integral quadratic form is a formal expression $Q(x_1,..,x_n)={\sum }_{1\le i,j\le n}{a}_{ij}{x}_i{x}_j$ in $n$-variables $x_1,...,x_n$, where $a_{ij}=a_{ji}\in \mathbb{Z}$. We present a randomized polynomial time algorithm that given a quadratic form $Q(x_1,...,x_n)$, a prime $p$, and a positive integer $k$ outputs a $\mathtt{U}\in {\text{GL}}_n(\mathbb{Z}/p^k\mathbb{Z})$ such that $\mathtt{U}$ transforms $Q$ to its $p$-adic canonical form.

arXiv admin note: text overlap with arXiv:1404.0281

References in corpus (1)

• Sampling a Uniform Random Solution of a Quadratic Equation Modulo $p^k$

Cited by in corpus (1)

• Generating a Quadratic Forms from a Given Genus