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

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 poly$(n,k,\log p,\log t)$ randomized algorithm that given a quadratic form $Q(x_1,...,x_n)$, a prime $p$, a positive integer $k$ and an integer $t$, samples a uniform solution of $Q(x_1,...,x_n)\equiv t\mathrm{mod}{p}^k$.

Cited by in corpus (2)

• Computing the $p$-adic Canonical Quadratic Form in Polynomial Time
• Generating a Quadratic Forms from a Given Genus