text:
\section{Introduction}

Let $\Ring$ be a commutative ring with unity and $\Ring^\times$
be the set of units (i.e., invertible elements) of $\Ring$. A
quadratic form over the ring $\Ring$ in $n$-formal variables
$x_1,\cdots,x_n$ in an expression
$\sum_{1\leq i, j \leq n}a_{ij}x_ix_j$, where $a_{ij}=a_{ji}
\in \Ring$. A quadratic form can equivalently be represented by
a symmetric matrix $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n=(a_{ij})$ such that
$Q(x_1,\cdots,x_n)=(x_1,\cdots,x_n)'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}(x_1,\cdots,x_n)$. The
quadratic form is called integral if $\Ring=\mathbb{Z}$ and the
determinant of the quadratic form $Q$ is defined as $\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$.
In this paper, we concern ourselves with integral quadratic
forms, henceforth referred only as {\em quadratic forms}.

One of the classical problems in the study of quadratic
forms is their classification into equivalence classes.
Two quadratic forms $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1, \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$ are said to be equivalent
over a ring $\Ring$ if there exists a transformation
$\MU \in \gln(\Ring)$ such that $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1 = \MU'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2\MU$.
For example, $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1$ and $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$ are $q$-equivalent, for an
integer $q$ (denoted, $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1 \overset{q}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$), if there exists a
matrix $\MU \in \gln(\zRz{q})$ such that
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1 \equiv \MU'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2\MU \bmod q$. Intuitively,
$q$-equivalence means
that there exists an invertible linear change of variables over
$\zRz{q}$ that transforms one form to the other. Gauss \cite{Gauss86}
gives a complete classification of binary quadratic forms
(i.e., $n=2$).

Two quadratic forms are said to be in the
same genus if they are equivalent over the reals $\mathbb{R}$ and also
over $\zRz{q}$ for all positive integers $q$. In this paper, we
consider the following problem: given a description of a non-empty
genus, produce a quadratic form from that genus.
A discussion of the problem can
be found in Conway and Sloane \cite{CS99}, page 403. The
best algorithm for this problem is based on Minkowski
Reduced forms and takes $O(d^{n^2})$ time for genus in dimension
$n$ with determinant $d$.

The skeleton of our
algorithm is similar to the algorithm given by Hartung
\cite{Hartung08}. His thesis uses an equivalent but different
approach based on Cassels \cite{Cassels78}. Unfortunately, there
are several gaps in his construction. There are also mistakes when
dealing with prime~2. But, the most
severe problem with the algorithm is that its time
complexity is proportional to $n^n$ i.e., it is not
polynomial. A discussion can be found in Section \ref{sec:Hartung}.

We mention here, a connection of our problem to
lattices as studied in the Computer Science community.
A {\em full-rank} lattice $L$ in $\mathbb{R}^n$ is a discrete subgroup of
$\mathbb{R}^n$ which is the set of all integer linear combinations of
$n$-linearly independent vectors, say $\mathbf{b}_1,\ldots,\mathbf{b}_n$ i.e.,
$L=\{\sum_{i=1}^n z_i \mathbf{b}_i \mid z_1,\ldots,z_n \in \mathbb{Z}\}$.
The matrix $\MB=[\mathbf{b}_1,\ldots,\mathbf{b}_n]$ is called
the {\em basis} of the lattice and the matrix $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}=\MB'\MB$ is called
a {\em Gram} matrix of the lattice. A lattice is {\em integral} if its
Gram matrix has only integer entries. It is not difficult to see
that the Gram matrix of a lattice defines a positive definite
quadratic form.

Two lattices
are called {\em isomorphic} if one can be transformed into
another by an orthogonal linear transformation.
A fundamental question, called the Lattice
Isomorphism Problem (LIP), is to decide if two given
Gram matrices come from isomorphic lattices.
In other words, given two Gram matrices
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1$ and $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$ one has to decide if there exists a
unimodular matrix $\MU$ such that $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2=\MU'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1\MU$.
For Gram matrices in dimension $n$ and determinant $d$,
the problem can be solved using Minkowski Reduced Forms
(see Section 10, Chapter 10 \cite{CS99}) in time
$O(d^{n^2})$. Other exhaustive search algorithms are known,
see \cite{Dietmann03,Siegel72}. Recently, Regev and
Haviv \cite{HR13}
gave an algorithm with time complexity which is
$n^{O(n)}$ times the size of the input.

The shortest vector problem (SVP) is the problem of finding the
shortest non-zero vector in a given lattice.
The current best known hardness for SVP is given
by Regev-Haviv \cite{HR07} and is based on tensoring lattice bases
in the hope of amplifying the length of the shortest vector.
This approach fails in general. For large enough dimension $n$, there are
self dual lattices with shortest vector $\Omega(\sqrt{n})$. The
usual tensoring among these lattices fails to amplify the length
of the shortest vector (Lemma~2.4, \cite{HR07}). It is not known
how one can construct self-dual lattice with shortest vector
length $\Omega(\sqrt{n})$ but it can be shown that such lattices
exist in large dimensions. The proof of existence (see page~48,
\cite{MH73}) uses the
Smith-Minkowski-Siegel mass formula; which computes
the average number vectors of a certain length in a genus.
One way to generate a self-dual lattice with shortest vector
$\Omega(\sqrt{n})$ is to sample a lattice according to a certain
distribution from a specific genus (see Milnor-Husemoller
\cite{MH73}). Our result falls short in the following way. Given
this specific genus, we can construct one lattice but we do not
know how to sample according to the distribution specified in
\cite{MH73}. In this respect, our work can be seen as an important
first step towards construction of self-dual lattices with shortest
vector $\Omega(\sqrt{n})$.

\paragraph*{Our Contributions.}

Let $d$ be the determinant of a genus in dimension $n$.
We present a $\poly(n,\log d)$ Las Vegas algorithm
that outputs a quadratic form in the genus with constant probability.
Our construction technique is inspired by the proof of
Smith-Minkowski-Siegel mass formula given by Siegel
\cite{Siegel35} and uses similar notations as Conway-Sloane
\cite{CS99}.

A significant feature of our work is the simplification achieved by
not using $p$-adic numbers, a staple in the analysis of
integral quadratic forms \cite{CS99,Kitaoka99,Kneser02,Siegel35}.

\section{Preliminaries}

Integers and ring elements are denoted by lowercase letters,
vectors by bold lowercase letters and matrices by typewriter
uppercase letters. The $i$'th component of a vector $\mathbf{v}$ is
denoted by $v_i$. We use the notation $(v_1,\cdots,v_n)$ for
a column vector and the transpose of matrix $\mathtt{A}} \newcommand{\MB}{\mathtt{B}$ is denoted by
$\mathtt{A}} \newcommand{\MB}{\mathtt{B}'$. The matrix
$\mathtt{A}} \newcommand{\MB}{\mathtt{B}^n$ will denote a $n\times n$ square matrix.
The scalar product of two vectors will be denoted
$\mathbf{v}'\mathbf{w}$ and equals $\sum_i v_iw_i$. The standard Euclidean norm of the
vector $\mathbf{v}$ is denoted by $||\mathbf{v}||$ and equals $\sqrt{\mathbf{v}'\mathbf{v}}$.

If $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1^n, \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2^m$ are matrices, then the {\em direct product}
of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1$ and $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$ is denoted by $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1\oplus\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$ and is
defined as $\diag(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1,\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2)=\begin{pmatrix}
\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1&0\\0&\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2
\end{pmatrix}$.
Given two matrices $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1$ and $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$ with the same number
of rows, $[\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1,\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2]$ is the matrix which is obtained
by concatenating the two matrices columnwise.
A matrix is called unimodular
if it is an integer $n\times n$ matrix with determinant $\pm 1$.
If $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ is a $n\times n$ integer matrix and $q$ is a positive integer
then $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \bmod{q}$ is defined as the matrix with all entries of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$
reduced modulo $q$.

Let $\Ring$ be a commutative ring with unity and $\Ring^\times$ be the
set of units (i.e., invertible elements) of $\Ring$.
If $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \in \Ring^{n\times n}$ is a square matrix, the
{\em adjugate} of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ is defined as the transpose of
the cofactor matrix and is denoted by $\adj(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$. The matrix $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$
is invertible if and only if $\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$ is a unit of $\Ring$.
In this case, $\adj(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})=\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^{-1}$. The set of invertible
$n\times n$ matrices over $\Ring$ is denoted by $\gln(\Ring)$. The
subset of matrices with determinant $1$ will be denoted by
$\sln(\Ring)$.

\begin{fact}\label{fact:gln}
A matrix $\MU$ is in $\gln(\Ring)$ iff $\det(\MU) \in \Ring^\times$.
\end{fact}

The set of odd primes is denoted by $\mathbb{P}$.
We define $\mathbb{Q}/(-1)\mathbb{Q}=\zRz{(-1)}:=\mathbb{R}$.
For every prime $p$ and positive integer $k$,
we define the ring $\zRz{p^k}=\{0,\cdots,p^k-1\}$, where product
and addition is defined modulo $p^k$.

Let $p$ be a prime, and $a, b$ be integers. Then,
$\ord_p(a)$ is the largest integer exponent of $p$ such that $p^{\ord_p(a)}$
divides $a$. We let $\ord_p(0) = \infty$. The $p$-coprime part of $a$ is then
$\cop_p(a)=\frac{a}{p^{\ord_p(a)}}$. Note that $\cop_p(a)$ is,
by definition, a unit of $\zRz{p}$.
For $\frac{a}{b}$, a rational number, we define
$\ord_p(\frac{a}{b})=\ord_p(a)-\ord_p(b)$. The $p$-coprime part of $\frac{a}{b}$
is denoted as
$\cop_p(\frac{a}{a})$ and equals $\frac{a/p^{\ord_p(a)}}{b/p^{\ord_p(b)}}$.
For a positive integer $q$,
one writes $a\equiv b \bmod{q}$, if $q$
divides $a-b$. By $x:=a \bmod{q}$, we mean that
$x$ is assigned the unique value $b \in \{0,\cdots,q-1\}$ such that
$b \equiv a \bmod{q}$.
An integer $t$ is
called a {\em quadratic residue} modulo $q$ if $\gcd(t,q)=1$ and
$x^2\equiv t \bmod{q}$ has a solution.

\begin{definition}\label{def:Legendre}
Let $p$ be an odd prime, and $t$ be a positive integer with
$\gcd(t,p)=1$.
Then, the Legendre-symbol of $t$ with
respect to $p$ is defined as follows.
\begin{displaymath}
\legendre{t}{p} = t^{(p-1)/2} \bmod p = \left\{ \begin{array}{ll}
1 & \textrm{if $t$ is a quadratic residue modulo $p$}\\
-1 & \textrm{otherwise.}
\end{array}\right.
\end{displaymath}
\end{definition}

For the prime~2, there is an extension of Legendre symbol called the
Kronecker symbol. It is defined for odd integers $t$ and
$\legendre{t}{2}$ equals $1$ if $t\equiv \pm 1 \bmod 8$, and $-1$
if $t \equiv \pm 3 \bmod 8$.

The Law of Quadratic Reciprocity, conjectured by Euler and Legendre
and first proved by Gauss, says that if
$p_1, p_2$ are distinct primes, and $p$ is an odd prime, then
\begin{align}\label{QuadraticReciprocity}
\legendre{p_1}{p_2} = \left\{
\begin{array}{ll}
- \legendre{p_2}{p_1} & \text{if $p_1\equiv p_2 \equiv 3 \pmod 4$,}\\
\legendre{p_2}{p_1} & \text{otherwise.}
\end{array}\right. \qquad
\legendre{p\vphantom{2}}{2\vphantom{p}} = \legendre{2}{p}
\end{align}

The $p$-sign of $t$, denoted $\sgn_p(t)$, is defined as
$\legendre{\cop_p(t)}{p}$
for odd primes $p$ and $\cop_2(t) \bmod 8$ otherwise. We
also define $\sgn_p(0)=0$, for all primes $p$.
Thus,
\[
\sgn_p(0) = 0 \qquad
\sgn_p(t>0) \in \left\{
	\begin{array}{ll}
	\{+1,-1\} & \text{if $p$ is odd}\\
	\{1,3,5,7\} & \text{otherwise}
	\end{array}\right.
\]

The following lemma is well known.

\begin{lemma}\label{lem:QR}
Let $p$ be an odd prime. Then, there
are $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$
quadratic non-residues modulo $p$. Also, every quadratic residue
in $\zRz{p}$ can be written as a sum of two quadratic non-residues
and every quadratic non-residue can be written as a sum of two quadratic
residues.
\end{lemma}

An integer $t$ is a square modulo $q$
if there exists an integer $x$ such that $x^2\equiv t \pmod{q}$.
The integer $x$ is called the {\em square root} of $t$
modulo $q$. If no such $x$ exists, then $t$ is a non-square modulo $q$.

\begin{definition}\label{def:NonSquare}
Let $p$ be a prime and $\frac{x}{y}$ be a rational number. Then, $\frac{x}{y}$
can be uniquely written as $\frac{x}{y}=p^{\alpha}\frac{a}{b}$,
where $a,b$ are  units of $\zRz{p}$. We say that $\frac{x}{y}$ is a
$p$-antisquare if $\alpha$ is odd and $\sgn_p(a) \neq \sgn_p(b)$.
\end{definition}

The following lemma is folklore and gives the necessary and sufficient
conditions for an integer $t$ to be a square modulo $p^k$. For
completeness, a proof is provided in Appendix \ref{sec:Proofs}.

\begin{lemma}\label{lem:Square}
Let $p$ be a prime, $k$ be a positive integer and
$t \in \zRz{p^k}$ be a non-zero integer. Then, $t$ is a
square modulo $p^k$ if and only if $\ord_p(t)$ is even and
$\sgn_p(t)=1$.
\end{lemma}

\begin{definition}\label{def:Prim}
Let $p^k$ be a prime power. A vector $\mathbf{v} \in (\zRz{p^k})^n$ is called
primitive if there exists a component $v_i$, $i \in [n]$, of $\mathbf{v}$ such
that $\gcd(v_i,p)=1$. Otherwise, the vector $\mathbf{v}$ is
non-primitive.
\end{definition}

Our definition of primitiveness of a vector is different but equivalent
to the
usual one in the literature. A
vector $\mathbf{v} \in (\zRz{q})^n$ is called primitive over $\zRz{q}$ for a
composite integer $q$ if it is primitive modulo $p^{\ord_p(q)}$ for
all primes that divide $q$.

\paragraph{Randomized Algorithms.}
Our randomized algorithms are
Las Vegas algorithms. They either fail
and output nothing, or produce a correct answer. The
probability of failure is bounded by a constant. Thus, for any
$\delta>0$, it is possible to repeat the algorithm
$O(\log \frac{1}{\delta})$ times and succeed with probability at least
$1-\delta$. Henceforth, these algorithms will be called
{\em randomized algorithms}.

Our algorithms perform two kinds of operations. Ring operations e.g.,
multiplication, additions, inversions over $\zRz{p^k}$ and operations
over integers $\mathbb{Z}$ e.g., multiplications, additions, divisions etc
and operations over integers $\mathbb{Z}$.
The runtime for all these operations is treated as constant i.e., $O(1)$
and the time complexity of the algorithms is measured in terms of
ring operations. Note that the complexity cannot be assumed to be
$O(1)$ if the numbers are doubly exponential in $n$. Thus, we make sure
than the numbers generated during the algorithm are bounded by
$2^{\poly(n,d)}$.
Sometimes, we also need to sample a
uniform ring element from $\zRz{p^k}$. We adapt the convention that sampling
a uniform ring elements also takes $O(1)$ ring operations.

For example, the Legendre symbol of an integer $a$ can be computed
by fast exponentiation in $O(\log p)$ ring operations over $\zRz{p}$
while $\ord_p(t)$
for $t \in \zRz{p^k}$ can be computed by fast exponentiation in $O(\log k)$ ring
operations over $\zRz{p^k}$.

Let $\omega$ be the constant, such that multiplying two $n\times n$
matrices over $\zRz{p^k}$ takes
$O(n^{\omega})$ ring operations.

\paragraph{Dirichlet's Theorem.}

Let $a,q$ be positive integers such that $\gcd(a,q)=1$.
Dirichlet's theorem states
that there are infinitely many primes of the form $a+zq$, where
$z$ is a non-negative integer. The following theorem gives a
quantitative version of Dirichlet's theorem using Generalized
Riemann Hypothesis (GRH). A proof of the theorem
can be found in any analytic number theory book, for
example \cite{Kowalski04}.

\begin{theorem}\label{thm:ERH}
Let $a, q$ be integers such that $\gcd(a,q)=1$ and $S$ be the set
$\{a+zq\mid z \in \mathbb{Z}, a+zq \leq q^3\}$. Then assuming GRH, there exists a
constant $c$ such that $S$ has $c\frac{|S|}{\log|S|}$ primes.
\end{theorem}

Another implication of GRH is that the
smallest quadratic non-residue modulo $p$, for odd prime $p$; is
a number less than $3(\ln p)^2/2$, see \cite{Ankeny52,Wedeniwski01}.
Thus, assuming GRH, a quadratic residue modulo $p$ can be found
deterministically in time $O(\log^3p)$ ring operations over $\zRz{p}$
by trying all integers $\leq 3(\ln p)^2/2$.

\paragraph{Quadratic Form.}
An $n$-ary quadratic form over a ring $\Ring$
is a symmetric matrix $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \in \Ring^{n\times n}$, interpreted as the following
polynomial in $n$ formal variables $x_1,\cdots, x_n$ of uniform degree~2.
\[
\sum_{1\leq i,j \leq n}\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_{ij}x_ix_j =
\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_{11}x_1^2 + \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_{12}x_1x_2 + \cdots = \Vx'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}\Vx
\]
The quadratic form is called {\em integral} if it is defined over the ring
$\mathbb{Z}$. It is called positive definite if for all non-zero column vectors
$\Vx$, $\Vx'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}\Vx > 0$. This work deals with integral quadratic forms,
henceforth called simply {\em quadratic forms}.
The {\em determinant} of the quadratic
form is defined as $\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$.
A quadratic form is called {\em diagonal} if $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ is a diagonal matrix.

Given a set of formal variables
$\Vx=\begin{pmatrix}x_1 & \cdots & x_n\end{pmatrix}'$ one can make a linear
change of variables to $\mathbf{y}=\begin{pmatrix}y_1 & \cdots & y_n\end{pmatrix}'$
using a matrix $\MU \in \Ring^{n\times n}$ by setting $\mathbf{y}=\MU\Vx$.
If additionally,
$\MU$ is invertible over $\Ring$ i.e., $\MU \in \gln(\Ring)$, then this
change of
variables is reversible over the ring. We now define the equivalence of
quadratic forms over the ring $\Ring$ (compare with Lattice Isomorphism).

\begin{definition}\label{def:equiv}
Let $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1^n, \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2^n$ be quadratic forms over a ring $\Ring$. They are called
$\Ring$-{\em equivalent} if there exists a $\MU \in \gln(\Ring)$ such that
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2=\MU'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1\MU$.
\end{definition}

If $\Ring=\zRz{q}$, for some positive integer $q$, then two integral
quadratic forms $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1^n$ and $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2^n$ will be called $q$-equivalent (denoted,
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1\overset{q}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$)
if there exists a matrix $\MU \in \gln(\zRz{q})$ such that
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2\equiv\MU'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1\MU\pmod q$.
For a prime $p$, they
are $p^*$-equivalent (denoted, $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1\overset{p^*}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$) if  they
are $p^k$-equivalent for every positive integer $k$. Additionally,
$(-1)^*$-equivalence as well as $(-1)$-equivalence mean
equivalence over the reals $\mathbb{R}$.

Let $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ be a $n$-ary integral quadratic form, and $q,t $ be positive
integers. If the equation $\Vx'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}\Vx \equiv t \pmod{q}$ has a solution
then we say that $t$ has a $q$-representation in $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ (or $t$ has
a representation in
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ over $\zRz{q}$). Solutions
$\Vx \in (\zRz{q})^n$ to the equation are called $q$-{\em representations} of
$t$ in $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$. We classify the representations into two
categories: {\em primitive} and {\em non-primitive} (see Definition
\ref{def:Prim}). The following lemma shows that a primitive
representation can be extended to a invertible transformation.

\begin{lemma}\label{lem:ExtendPrimitive}
Let $p$ be a prime, $k$ be a positive integer and
$\Vx \in (\zRz{p^k})^n$ be a primitive vector.
Then, an $\mathtt{A}} \newcommand{\MB}{\mathtt{B}$ can be found in $O(n^2)$ ring operation
such that $[\Vx,\mathtt{A}} \newcommand{\MB}{\mathtt{B}] \in \sln(\zRz{p^k})$.
\end{lemma}
\begin{proof}
The column vector $\Vx=(x_1,\cdots,x_n)$ is primitive, hence there
exists a $x_i$, $i\in [n]$ such that $x_i$ is invertible over $\zRz{p^k}$.
It is easier to write the matrix $\MU$, which equal $[\Vx,\mathtt{A}} \newcommand{\MB}{\mathtt{B}]$ where
the row $i$ and $1$ or $[\Vx,\mathtt{A}} \newcommand{\MB}{\mathtt{B}]$ are swapped.
\[
\MU = \begin{pmatrix}x_i & 0 \\
\Vx_{-i} & x_i^{-1}\bmod{p^k} \oplus \MI^{n-2}
\end{pmatrix}\qquad \Vx_{-i}=(x_1,\cdots,x_{i-1},x_{i+1},\cdots,x_n)
\]
The matrix $\MU$ has determinant~1 modulo $p^k$ and hence is invertible
over $\zRz{p^k}$. The lemma now follows from the fact that the swapped matrix
is invertible iff the original matrix is invertible.
\end{proof}

For the following result, see Theorem~2, \cite{Jones50}.

\begin{theorem}\label{thm:diagonal}
An integral quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ is equivalent to a quadratic
form
$q_1 \oplus \cdots \oplus q_a \oplus q_{a+1} \oplus \cdots \oplus q_n$
over the field of rationals $\mathbb{Q}$,
where $a \in [n]$, $q_1, \cdots, q_a$ are positive rational numbers and
$q_{a+1}, \cdots, q_n$ are negative rational numbers.
\end{theorem}

The {\em signature} (also, $(-1)$-signature) of the form
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ (denoted $\sig(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$, also  $\sig_{(-1)}(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$) is defined
as the number $2a-n$, where $a$ is the integer in
Theorem \ref{thm:diagonal}.

Each rational number $q_i$ in Theorem
\ref{thm:diagonal} can be written uniquely as
$p^{\alpha_i}a_i$, where $\alpha_i = \ord_p(q_i)$ and $a_i = \cop_p(q_i)$.
Let $m$ be the number of $p$-antisquares among $q_1,\cdots,q_n$.
Then, we define the $p$-signature of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ as follows.
\begin{align}\label{def:PSignature}
\sig_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})=\left\{
\begin{array}{ll}
p^{\alpha_1}+ p^{\alpha_2} + \cdots + p^{\alpha_n} + 4m  \pmod{8}  & p\neq 2 \\
a_1 + a_2 + \cdots + + a_n + 4m \pmod{8} & p=2
\end{array}\right.
\end{align}
The $2$-signature is also known as the {\em oddity} and is denoted by
$\odty(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$.
Even though there are different ways to diagonalize a quadratic form
over $\mathbb{Q}$, the signatures are an invariant for the quadratic form.

For each $p \in \{-1,2\} \cup \mathbb{P}$, we define the $p$-excess of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$
as follows.
\begin{align}\label{def:PExcess}
\excess_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) = \left\{
	\begin{array}{ll}
	\sig_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) - n & p \neq 2 \\
	 n - \sig_2(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) & p = 2
	\end{array}\right.
\end{align}

\begin{theorem}\label{thm:oddity}(\cite[page~76]{Cassels78}, \cite[Theorem~29]{Jones50})
Let $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ be an integral quadratic form. Then,
\begin{align}\label{SumFormula}
\begin{array}{ll}
\sum_{p \in \{-1,2\}\cup \mathbb{P}} \excess_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) &\equiv 0 \pmod 8 \text{ or equivalently,}\\
\sig(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) + \sum_{p \in \mathbb{P}} \excess_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) &\equiv \odty(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) \pmod 8\;.
\end{array}
\end{align}
\end{theorem}

The Equation \ref{SumFormula} is also referred to as the {\em
oddity formula} in the literature.

\paragraph{Diagonalizing a Quadratic Form.}

For the ring $\zRz{p^k}$ such that $p$ is odd, there
always exists an equivalent quadratic form which is also diagonal
(see \cite{CS99}, Theorem 2, page 369).
Additionally, one can explicitly find the invertible change of
variables that turns it into a diagonal quadratic form.
The situation is tricky over the ring $\zRz{2^k}$. Here, it might not
be possible to eliminate all mixed terms, i.e., terms of the form
$2a_{ij}x_ix_j$ with $i\neq j$. For example, consider
the quadratic form $2xy$ i.e.,
$\begin{pmatrix}0 & 1 \\ 1 & 0 \end{pmatrix}$ over $\zRz{2^k}$.
An invertible linear change of variables over $\zRz{2^k}$ is
of the following form.
\begin{gather*}
\begin{array}{l}x \to a_1x_1 + a_2x_2\\
y \to b_1x_1+b_2x_2\end{array} \qquad
\begin{pmatrix}a_1 & a_2 \\ b_1 & b_2\end{pmatrix} \text{ invertible over
$\zRz{2^k}$}
\end{gather*}
The mixed term after this transformation is $2(a_1b_2+a_2b_1)$.
As $a_1b_2+a_2b_1 \bmod 2$ is the same as the determinant
of the change of variables above i.e., $a_1b_2-a_2b_1$
modulo $2$; it is not possible for a transformation in
$\gl_2(\zRz{2^k})$ to eliminate the mixed term.
Instead, one can show that over $\zRz{2^k}$ it is possible to get an
equivalent form where the mixed terms are disjoint i.e., both
$x_ix_j$ and $x_ix_k$ do not appear, where $i,j,k$ are
pairwise distinct.
One captures this form by the following definition.

\begin{definition}\label{def:BlockDiagonal}
A matrix $\MD^n$ over integers is in a block diagonal form if it is a
direct sum of type I and type II forms; where type I form is an integer
while type II is a matrix of the form
$\begin{pmatrix}2^{\ell+1}a & 2^{\ell} b \\ 2^{\ell}b & 2^{\ell+1}c\end{pmatrix}$
with $b$ odd.
\end{definition}

The following theorem is folklore and is also implicit in the proof of
Theorem~2 on page~369 in \cite{CS99}. For completeness, we provide a
proof in Appendix \ref{sec:BlockDiagonal}.

\begin{theorem}\label{thm:BlockDiagonal}
Let $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ be an integral quadratic form, $p$ be a prime,
and $k$ be a positive integer.
Then, there is an algorithm that performs $O(n^{1+\omega}\log k)$ ring operations
and produces a matrix $\MU \in \sln(\zRz{p^k})$ such that $\MU'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}\MU\pmod{p^k}$, is a
diagonal matrix for odd primes $p$ and a block diagonal matrix
(in the sense of Definition~\ref{def:BlockDiagonal}) for $p=2$.
\end{theorem}

\paragraph{Canonical Forms.}

For a quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ and prime $p$, the set
$\{\MS^n \mid \MS \overset{p^*}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}\}$ is the set of
$p^*$-equivalent forms of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ (also called $p^*$-equivalence class of
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$).  It is possible to define something called a
``canonical'' quadratic form for the $p^*$-equivalence class of a given
quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$. In
particular, we are interested in
a function $\can_p$ such that for all integral quadratic forms
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$, $\can_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) \in \{\MS \mid \MS \overset{p^*}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}\}$; with the
property that if $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1 \overset{p^*}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$ then
$\can_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1) = \can_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2)$.
We also consider a related problem of coming up with a
canonicalization procedure. In particular, we want a polynomial
time algorithm that given $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}, p$ and a positive integer $k$,
finds $\MU \in \gln(\zRz{p^k})$ such that
$\MU'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}\MU \equiv \can_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})\bmod{p^k}$.

It is not difficult to show the existence of a canonical form.
For example, we can go over the $p^*$-equivalence class of
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ and output the form which is lexicographically the smallest
one. But, this form gives us no meaningful information about
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ or the $p^*$-equivalence class of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$.

For odd prime $p$,
the $p$-canonical form is implicit in Conway-Sloane
\cite{CS99} and is also described explicitly by Hartung
\cite{Hartung08, Cassels78}. The canonicalization algorithm in this case
is not complicated and can be claimed to be implicit in
Cassels \cite{Cassels78}.

The definition of canonical form for the case of prime~2 is
quite involved and needs careful analysis\footnote{
Cassels (page~117, Section~4, \cite{Cassels78}),
referring to the canonical forms for $p=2$
observes that ``only a masochist is invited to read the rest''.}
\cite{Jones44, CS99, Watson60}.
Jones \cite{Jones44} presents the most complete description
of the $2$-canonical form. His method is to come up with a small
$2$-canonical forms and then showing that every quadratic form is
$2^*$-equivalent to one of these. Unfortunately, a few of his
transformations are existential i.e., he shows that a transformations
with certain properties exists without explicitly finding them.

The following theorems appear in \cite{DH14Can}.

\begin{theorem}\label{thm:ALG:CanP}
Let $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ be an integral quadratic form, $p$ be a prime and
$k\geq \ord_2(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}))+k_p$. Then, there is an algorithm (Las Vegas
with constant probability of success for odd primes and deterministic for
the prime~2)
that given $(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n, p, k)$ performs
$O(n^{1+\omega}\log k+nk^3+n\log p+\log^3p)$ ring operations over $\zRz{p^k}$
and outputs $\MU \in \gln(\zRz{p^k})$
such that $\MU'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}\MU \equiv \can_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) \bmod{p^k}$.
\end{theorem}

\begin{theorem}\label{thm:PStarEq}
Let $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ be an integral quadratic form, $p$
be a prime and $k = \ord_p(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}))+k_p$. If $\MD^n$ is a block
diagonal form which is equivalent
to $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ over $\zRz{p^k}$, then $\MD \overset{p^*}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}$.
\end{theorem}

\paragraph{Primitive Representations.}
The following theorem gives an algorithmic handle on the
question of deciding if an integer $t$ has a primitive
$p^*$-representation in $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$. The theorem is implicit
in Siegel \cite{Siegel35} (a proof is provided in
Appendix \ref{sec:Proofs} for completeness).

\begin{theorem}\label{thm:Siegel13}
Let $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ be an integral quadratic form, $t$ be an integer,
$p$ be a prime and $k=\max\{\ord_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}),\ord_p(t)\}+k_p$. Then,
if $t$ has a primitive $p^k$-representation in $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ then
$t$ has a primitive $p^*$-representation in $\tilde{\mathtt{Q}} \newcommand{\MS}{\mathtt{S}}$ for all
$\tilde{\mathtt{Q}} \newcommand{\MS}{\mathtt{S}} \overset{p^*}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}$.
\end{theorem}

Next, we give several results from \cite{DH14}.
This paper deals with the following problem. Given a quadratic
form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ in $n$-variables, a prime $p$, and integers $k,t$
find a solution of $\Vx'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}\Vx\equiv t \bmod{p^k}$, if it exists.
Note that it is easy (i.e., polynomial time tester exists) to test
if $t$ has a $p^k$-representation in $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$.

\begin{theorem}\label{thm:PolyRep}
Let $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ be an integral quadratic form, $p$ be a prime,
$k$ be a positive integer, $t$ be an element of $\zRz{p^k}$.
Then, there is a
polynomial time algorithm (Las Vegas for odd primes and
deterministic for the prime~2)
that performs
$O(n^{1+\omega}\log k+nk^3+n\log p)$ ring operations over
$\zRz{p^k}$ and outputs a primitive
 $p^k$-representation of $t$ by $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$,
if such a representation exists. The time complexity can be improved
for the following special cases.
\begin{align*}
\begin{array}{ll}
\text{Type I, $p$ odd} & ~~O(\log k+\log p)\\
\text{Type I, $p=2$} & ~~O(k)\\
\text{Type II} & ~~O(k\log k)
\end{array}
\end{align*}
\end{theorem}

Next, we give necessary and sufficient conditions for a Type II
block to represent an integer $t$. A proof of this result can
also be found in \cite{DH14}.

\begin{lemma}\label{lem:RepresentTTypeII}
Let $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}=\begin{pmatrix}2a & b \\ b & 2c \end{pmatrix}$, $b$ odd
be a type II block, and $t, k$ be positive integers. Then, $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ represents
$t$ primitively over $\zRz{2^k}$ if $\ord_2(t)=1$.
\end{lemma}

\paragraph{Additional Notation.}
For convenience, we introduce the following notations, where
$q$ is a positive integer.
\begin{align}\label{not:kp}
k_p = \left\{\begin{array}{ll} 3 & \text{if $p=2$, and}\\
1 & \text{$p$ odd prime.}
\end{array}\right.
&\qquad
\overline{q}= q\prod_{p|2q}p^{k_p} \\
\mathbb{P}_q &= \{p \mid \ord_p(2q)>0\} \nonumber\\
\SGNI &= \{1,3,5,7\} \nonumber\\
\mathtt{T}^{+} = \begin{pmatrix}2&1\\1&4\end{pmatrix}
&\qquad
\mathtt{T}^{-} = \begin{pmatrix}2&1\\1&2\end{pmatrix}\nonumber
\end{align}

\section{Technical Overview}

In this section, we give an overview of our algorithm.
Note that this algorithm does not run in polynomial
time. The final version of the algorithm, which is correct and runs
in polynomial time will be presented in Section \ref{sec:QFGen}.

Before describing the algorithm, we need to describe the input
to the algorithm.
The question of succinct specification of a genus has several
competing answers \cite{Watson76,Kitaoka99,CS99,OMeara73}.
In this work, we use the specification by Conway-Sloane, called
the {\em symbol}; with the property that two
quadratic forms are in the same genus iff they have the same symbol.
An intuitive overview of the symbol follows (see Section \ref{sec:Symbol}
for the formal version).

It can be shown that two quadratic forms $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1^n$
and $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2^n$ are in the same genus iff : (i) $\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1)=\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2)$,
(ii) $\sig(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1)=\sig(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2)$
and (iii) $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1\overset{p^*}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$, for every prime $p$ that divides
$2\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1)$. The set of primes
$\mathbb{P}_{\Sym}=\{p\mid \ord_p(2\det(\Sym)) > 0\}$ is called the set of
{\em relevant primes} for the genus $\Sym$.
The question now reduces to finding the necessary and sufficient
condition for $p^*$-equivalence. It can be shown that two
quadratic forms $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1^n$ and $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2^n$ are $p^*$-equivalent iff
(a) $\ord_p(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1))=\ord_p(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2))$, and
(b) $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1 \overset{p^k}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$, for
$k=\ord_p(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1))+k_p$. These two conditions can be written
in an equivalent way, using what is called the $p$-symbol of a
quadratic form.  The key property is that two quadratic forms are
$p^*$-equivalent iff they have the same $p$-symbol. For now, we
can think of $\can_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$ as the $p$-symbol of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$. By definition
of $p$-canonical forms, it follows that $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1 \overset{p^*}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2$ iff
$\can_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1)=\can_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2)$.

\paragraph{Symbol.} One can now give an informal description of
the symbol. Intuitively, think of $\SYM_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$ as the tuple
$(p,\can_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}))$. Then, by the definition of canonical forms, two
quadratic form are $p^*$-equivalent iff they have the same $p$-symbol.
 The symbol of a
quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ is the list of tuples
$(p,\can_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}))$, one for each prime that divides $2\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$
along with its signature
i.e.,
\begin{gather}\label{EQ:SYM}
\SYM(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) = \{(-1, \sig(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}))\}
\bigcup_{p| 2\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})} \{ (p,\can_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}))\}
\end{gather}
Note that the determinant of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ is missing from the symbol. This is
because it is possible to find the determinant from the symbol $\SYM(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$.
This is done by calculating $\ord_p(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}))$ for each prime $p$.
The relevant primes of $\SYM(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$ can be read from the first component
in of the tuples in $\SYM(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$. And, for a relevant prime $p$ it
can be shown that $\ord_p(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}))=\ord_p(\det(\can_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})))$.

The notation $\Sym^n$ will denote both
a genus and the symbol of the
genus, depending on the context. The notation $\Sym_p$ will denote the
$p$-symbol of the genus $\Sym$.
The set of {\em relevant primes} for the symbol $\Sym$ is denoted by
$\mathbb{P}_{\Sym}=\{p \mid \ord_p(2\det(\Sym)) > 0\}$.
If $\SYM_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$ is the $p$-symbol of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ then
$\scalep(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$ denotes the set of $p$-scales of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$.
The size of the symbol of a genus $\Sym^n$ of determinant $d$
is $O(n|\mathbb{P}_{\Sym}|\log d)$.

\paragraph*{Local Form.} Given a symbol $\Sym^n$ and a positive
integer $q$, it is possible to construct a quadratic form $\MS^n$
such that $\MS \overset{q}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}$, for every $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \in \Sym$; in
$\poly(n,\log\det(\Sym), \log q)$ time. Such a form is said to be locally
equivalent to the genus $\Sym$ over $\zRz{q}$ and is denoted by
$\MS \overset{q}{\sim} \Sym$. The local form satisfies the following important
property. For every prime $p$ that divides $q$,
$\ord_p(\det(\MS))=\ord_p(\det(\Sym))$. Note that $\MS$ does not need to
have determinant $\det(\Sym)$ and may not be equivalent to $\Sym$
over $\mathbb{R}$. In particular, $\MS \not\in \Sym$.

\paragraph{Primitive Representation.}
If $t$ has a primitive $p^*$-representation in $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ then,
by Theorem \ref{thm:Siegel13}, $t$ has a
primitive $p^*$-representation in every
quadratic form in the genus $\gen(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$. Hence, the primitive
representativeness of an integer $t$ by a quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$
only depends on the symbol $\SYM(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$.

\begin{definition}\label{def:PrimRepInGenus}
We say that an integer $t$ has a primitive representation in a genus
$\Sym$ if $t$ has a primitive $p^*$-representation in $\Sym$ for all
$p \in \{-1,2\} \cup \mathbb{P}$.
\end{definition}

\paragraph*{Simple Version of the Algorithm.}
Let $\Sym^n$ be a symbol of non-empty genus. In this section,
we give the simple version of the algorithm.
The run time of the algorithm is not polynomial; mainly because the
exponential blowup in the determinant after each recursive step.
In Section \ref{sec:QFGen}, we show that by carefully selecting
the embedding $\Vx$ of $t$ and by
simplifying the input before each recursive call, it is
possible to avoid the blowup and show a polynomial bound on the
runtime.

\vspace*{10pt}
\noindent
\textsc{GenSimple} ({\em input:} $\Sym^n$)
{\em output:} $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n \in \Sym$
\begin{enumerate}[1.]
\item If $n=1$ then $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}=\det(\Sym)$.
\item Let $t$ be an integer such that $t$ has a primitive representation
in $\Sym$.
\item Let $q=\overline{t^{n-1}\det(\Sym)}$. Find $\MS$ such that
$\MS\overset{q}{\sim} \Sym$.
\item Find a primitive $q$-representation $\Vx$ such that $\Vx'\MS\Vx\equiv t\bmod{q}$.
\item Extend $\Vx$ by $\mathtt{A}} \newcommand{\MB}{\mathtt{B}$ so that $[\Vx,\mathtt{A}} \newcommand{\MB}{\mathtt{B}]\in \gln(\zRz{q})$.
\item Compute the following quantities.
\begin{align}\label{ALGO:dH}
\begin{array}{ll}
\Vd:=\Vx'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B} \bmod q & \mathtt{H}} \newcommand{\MI}{\mathtt{I} := (t\mathtt{A}} \newcommand{\MB}{\mathtt{B}'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B} - \Vd'\Vd) \bmod q\\
\end{array}
\end{align}
\item Define the symbol $\tilde{\Sym}^{n-1}$ as follows.
\begin{align}\label{def:tSym}
\tilde{\Sym}_p = \left\{ \begin{array}{ll}
\sig(t)\left(\sig(\Sym)-\sig(t)\right) & \text{if }p=-1\\
\SYM_p(\mathtt{H}} \newcommand{\MI}{\mathtt{I}) & \text{if $p$ divides $q$}\\
\SYM_p(\MI^{n-2} \oplus t^{n-2}\det(\Sym)) & \text{otherwise}
\end{array}\right.
\end{align}
\item Let $\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}} =$ \textsc{GenSimple}$(\tilde{\Sym})$.
\item Find $\tilde{\MU} \in \gl_{n-1}(\zRz{q})$ such that $\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}\equiv \tilde{\MU}'\mathtt{H}} \newcommand{\MI}{\mathtt{I}\tilde{\MU} \bmod q$.
\item Output $
\mathtt{Q}} \newcommand{\MS}{\mathtt{S} = \begin{pmatrix}t & \Vd\tilde{\MU} \\
(\Vd\tilde{\MU})' & \frac{\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}+\tilde{\MU}'\Vd'\Vd\tilde{\MU}}{t}\end{pmatrix}
$, where the division in the lower right is (usual) rational division.
\end{enumerate}

\subsection{Intuitive Description of the Algorithm}
For simplicity, we assume that $\sig_{(-1)}(\Sym)=n$ i.e., the genus
$\Sym$ is the genus of positive definite quadratic forms or
Gram matrix of lattices.

In order to find a Gram matrix $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ in the genus $\Sym$, we
start by finding a value $t$ such that $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ has the following form.
\begin{align}\label{EQ:MQForm}
\mathtt{Q}} \newcommand{\MS}{\mathtt{S} = \begin{pmatrix}t & \mathbf{w} \\ \mathbf{w}' & \tilde{\mathtt{Q}} \newcommand{\MS}{\mathtt{S}}\end{pmatrix}
\end{align}
It turns out that it suffices to find an integer $t$ which has a
primitive representation in the genus $\Sym$. The next step
is best explained by thinking in terms of lattices.

The Gram matrix $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ equals $\MB'\MB$, where
$\MB=[\mathbf{b}_1,\ldots,\mathbf{b}_n]$ is a basis of a lattice with Gram matrix
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$. Because $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ has the form given in Equation \ref{EQ:MQForm},
$\mathbf{b}_1'\mathbf{b}_1 = t$. Consider now the (possibly non-integral) lattice
one obtains by projecting $[\mathbf{b}_1,\ldots,\mathbf{b}_n]$ onto the subspace
orthogonal to $\mathbf{b}_1$.
It is possible to show that the Gram matrix of this lattice in
$(n-1)$-dimensions is given by $\tilde{\mathtt{Q}} \newcommand{\MS}{\mathtt{S}}-\frac{\mathbf{w}'\mathbf{w}}{t}$.

The matrix $\tilde{\mathtt{Q}} \newcommand{\MS}{\mathtt{S}}$, and the matrix $\mathbf{w}'\mathbf{w}$ are integral. Thus,
$t\tilde{\mathtt{Q}} \newcommand{\MS}{\mathtt{S}}-\mathbf{w}'\mathbf{w}$ is a Gram matrix of an integral lattice.
To find $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$, we therefore (a) find the symbol of the lattice
$t\tilde{\mathtt{Q}} \newcommand{\MS}{\mathtt{S}} - \mathbf{w}'\mathbf{w}$ and recursively find a corresponding lattice,
and (b) find $\mathbf{w}$.
To solve (a), the algorithm above constructs a locally equivalent quadratic
form $\MS$, then finds a representation $\Vx$ of $t$ into $\MS$, and transforms
$\MS$ with a transformation $[\Vx,\mathtt{A}} \newcommand{\MB}{\mathtt{B}] \in \gln(\zRz{q})$
which maps $t$ into the top left
\begin{align}
[\Vx,\mathtt{A}} \newcommand{\MB}{\mathtt{B}]' \MS [\Vx,\mathtt{A}} \newcommand{\MB}{\mathtt{B}] = \begin{pmatrix}
t & \Vd \\ \Vd' & \mathtt{A}} \newcommand{\MB}{\mathtt{B}'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B}
\end{pmatrix}\bmod q
\end{align}
To solve (b), it is possible to show that one can recover $\mathbf{w}$
from the vector $\Vd$.

Finally, one can show that because of the way we chose $q$
in the algorithm, the expression
$\frac{\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}+\tilde{\MU}'\Vd'\Vd\tilde{\MU}}{t}$ in the construction of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$
is actually integral.

\subsection{Comparisons to Hartung's Algorithm.}\label{sec:Hartung}

Our construction in Section \ref{sec:QFGen} is
similar to the algorithm given by Hartung \cite{Hartung08}.
This algorithm, as we will show, is not polynomial but $O(n^n)$.
There are other severe problems with Hartung's work
(i) several lemmas are incorrect because of insufficient care
while handling prime~2, and (ii) the construction of $t$, in case
of dimension~2,
is short but unfortunately incorrect.
This construction takes us several pages
(page~\pageref{dim2}-\pageref{dim2end}).
A detailed discussion of the comparison follows.

The first non-trivial step is to construct an integer $t$
which is primitively representatable in the genus $\Sym$.
Hartung constructs a $t$ such that $t=\wp s$, where $s$
divides $\det(\Sym)$ and $\wp$ is an prime which does not
divide $\det(\Sym)$. This construction seems correct when
$n\geq 3$ but incorrect for $n=2$. One of the reasons is
the treatment of the prime~2; which is not thorough. The
prime~2 has been known to create problems, if not handled
correctly \cite{Pall65, Minkowski10, Watson76}.

For example, Lemma 3.3.1 \cite{Hartung08} is incorrect
for $p=2$ because it is not possible to divide by~2 over
the ring $\zRz{2^k}$ at the end of the proof. This leads to an
easy counter example for Lemma 3.3.2, which claims that
a quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^{n\geq 3}$ with
$\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) \in (\zRz{p})^\times$ represents every integer $t$
primitively over $\zRz{p^k}$ for all positive integers $k$. A
counter example is $(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}=x^2+y^2+z^2, p=2, k=3, t=7)$. By
exhaustive search, it can be verified that $x^2+y^2+z^2$
does not represent $7$ modulo $8$. This mistake becomes
more severe in the construction of $t$ for $\Sym^{n=2}$.
The construction in this case is
highly non-trivial and needs a separate treatment
(page~\pageref{dim2}-\pageref{dim2end}).

The construction of $t$ for $\Sym^{n\geq 3}$ seems to be
correct \cite{Hartung08}.
Our construction, though, gives smaller $t$. Hartung
needs a prime $\wp$ which does not divide the determinant,
each time he needs to find a primitively representable integer $t$.
In contrast, we need
such a prime only once. Note that the construction of such a prime
$\wp$ takes polynomial time if ERH holds.

The most serious issue is that the algorithm by Hartung is not polynomial
time. He argues that each step in the algorithm is polynomial
and because each recursive step reduces the dimension by~1, overall
the algorithm is polynomial. This is not true because
after finding
$t$ and reducing to one less dimension to a symbol
$\tilde{\Sym}^{n-1}$,
$\det(\tilde{\Sym})=t^{n-2}\det(\Sym)$ (see Claim \ref{CALG:dtSym}).
The upper found on $t$ is $\det(\Sym)$ and so
$\det(\tilde{\Sym})$ can be as large as $\det(\Sym)^{n-1}$;
leading to a blowup $\sim \det(\Sym)^{n^n}$ if used $n$ times
recursively. As it is, the time complexity of Hartung's
algorithm is proportional to $O(n^n)$.
In contrast, our construction represents $t$ in a specific way and uses the
property of this representation to show that the determinant
blows up by $2^{n^2}$ at most; resulting in a
polynomial time algorithm (see Section \ref{sec:QFGenPoly}).

\section{Formalizing the Input}

This section describes the input to the algorithm which boils
down to the question of a succinct representation of the genus.

\subsection{Symbol of a Quadratic Form}\label{sec:Symbol}

There are several equivalent ways of giving a description of
the $p^*$-equivalence \cite{CS99, Kitaoka99, OMeara73, Cassels78}.
In this work, we go with a modified version of the Conway-Sloane description,
called the $p$-{\em symbol} of a quadratic form. Our modification
gets rid of the need to use the $p$-adic numbers.
Note that $p$-adic numbers are a
staple in this area and we are not aware of any work which does not
use them \cite{Kitaoka99, OMeara73, Siegel35}.

The $(-1)$-symbol of a quadratic form is equal to the
signature of the quadratic form.

\subsubsection{$p$-symbol, $p$ odd prime}\label{sec:PSym}

Let $k=\ord_p(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}))+1$ and $\MD$ be the diagonal quadratic form
which is $p^k$-equivalent to $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ (see Theorem \ref{thm:BlockDiagonal}).
Then, $\MD$ can be written as follows.
\begin{align}\label{def:jordanp}
\MD=\MD_0^{n_0} \oplus p\MD_1^{n_1} \ldots \oplus p^i \MD_i^{n_i} \oplus \ldots
\qquad i \leq \ord_p(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}))\;,
\end{align}
where $\MD_0,\ldots,\MD_{k-1}$ are diagonal quadratic forms,
$\sum_i n_i = n$ and $p$ does not divide
$\det(\MD_0)\ldots\det(\MD_{k-1})$. Let $\scalep(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$ is the set of
$p$-orders $i$ with non-zero $n_i$.
Then, the $p$-symbol of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ is defined as the
set of {\em scales} $i$ occurring in Equation \ref{def:jordanp} with non-zero
$n_i$, {\em dimensions} $n_{i}=\dim(\MD_i)$ and {\em signs}
$\epsilon_i=\legendre{\det(\MD_i)}{p}$.
\begin{equation}\label{eq:PSymbol}
\SYM_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})= \left\{(p, i,\legendre{\det(\MD_i)}{p},n_i) \mid
i \in \scalep(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})\right\}
\end{equation}

The following fundamental result follows from Theorem~9, page~379
\cite{CS99} and Theorem \ref{thm:PStarEq}.

\begin{theorem}\label{thm:PSymbol}
For $p \in \{-1\} \cup \mathbb{P}$, two quadratic forms
are $p^*$-equivalent iff they have the same $p$-symbol.
\end{theorem}

\subsubsection{$2$-symbol}\label{sec:2Sym}

Let $k=\ord_2(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}))+3$ and $\MD$ be the block diagonal form
which is $2^k$-equivalent to $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ (Theorem \ref{thm:BlockDiagonal}).
Then, $\MD$ can be written as follows.
\begin{align}\label{def:jordant}
\MD=\MD_0^{n_0} \oplus 2\MD_1^{n_1} \ldots \oplus 2^i \MD_i^{n_i}
\oplus \ldots \qquad i \leq \ord_2(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}))\;,
\end{align}
where $\det(\MD_0), \ldots, \det(\MD_i), \ldots$ are odd, $\sum_i n_i=n$
and each $\MD_i$ is in block diagonal form according to Definition
\ref{def:BlockDiagonal}.
The $2$-symbol of $2^i\MD_i$ are the following quantities.
\begin{equation}\label{def:2invariants}
\left(\begin{array}{lll}
i   & \text{{\em scale} of $\MD_i$} & \\
n_i= \dim(\MD_i) & \text{{\em dimension} of $\MD_i$} &\\
\epsilon_i = \legendre{\det(\MD_i)}{2} & \text{{\em sign} of $\MD_i$} & \\
\type_i=\text{I  or  II} & \text{{\em type} of $\MD_i$} & \text{I, iff
there is an odd entry on} \\ && \text{~the main diagonal of the }\\
&&\text{~matrix $\MD_i$}\\
\odty_i\in\{0,\ldots,7\} & \text{{\em oddity} of $\MD_i$} &
\text{it $\type_i=$I, then it
is equal to} \\ && \text{~the trace of $\MD_i$ read modulo $8$,} \\
&& \text{~and is $0$ otherwise.}
\end{array}\right)
\end{equation}
Let the set of scales $i$, with non-zero $n_i$, be denoted
$\scalet(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})$.
Then, the $2$-symbol of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ is written as follows.
\begin{equation}\label{eq:2sym}
\SYM_2(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})= \left\{(2,i,\epsilon_i, n_i, \type_i, \odty_i)
\mid i \in \scalet(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})\right\}
\end{equation}

In contrast to the $p \in \{-1\} \cup \mathbb{P}$ case,
two $2^*$-equivalent quadratic forms may produce two different
$2$-symbols. These symbols are then said to be $2$-equivalent.

\bigskip

Consider the following useful generalization of the function $p$-order.

\begin{definition}\label{def:porder}
Let $p \in \{2\}\cup \mathbb{P}$ be a prime, and $\Sym$ be a symbol with
$\Upsilon_p = \{(p,i,n_i,\epsilon_i, *, *)\}$, where $*$ is
empty in case $p$ is odd. Then, $\ord_p(\Sym)$ is defined as
$\argmax_i \{i \in \mathbb{I}_p(\Sym)\}$.
\end{definition}

\subsection{Reduced Symbol}

The set $\cup_{p \in \{-1,2\} \cup \mathbb{P}} \Upsilon_p$, where $\Upsilon_p$ is a
$p$-symbol, is a complete description of a genus and can be used as
an input to the algorithm. Unfortunately,
this description is too long because there are infinitely many primes. The
following lemma helps us in giving a shorter description.

\begin{lemma}\label{lem:RelevantPrimes}
Let $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ be a lattice with determinant $d$
and $p$ be an odd prime that does not divide $d$. Then,
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \overset{p^*}{\sim} d\oplus\MI^{n-1}$.
\end{lemma}
\begin{proof}
Let $p$ be an odd prime that does not divide $d$ and
$\MD=d_1\oplus \cdots \oplus d_n$ be the diagonal matrix which is
equivalent to $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ over $\zRz{p}$. Then, $p$ does not divide
$d_1\cdots d_n$ and
\[
\SYM_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) = \left\{ \left(p, 0, n, \legendre{\det(\MD)}{p}\right)\right\}
\]
By the definition of the $p$-symbol, $\MD \overset{p^*}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}$. It follows that there is a
$\MU \in \gln(\zRz{p})$ such that $\MD\equiv \MU'\mathtt{Q}} \newcommand{\MS}{\mathtt{S}\MU \bmod p$.
But then, $\det(\MD)\equiv\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})\det(\MU)^2 \bmod{p}$ and
\[
\legendre{\cop_p(\det(\MD))}{p} = \legendre{\cop_p(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})\det(\MU)^2)}{p}
=\legendre{\cop_p(d)}{p}.
\]
This implies that $d\oplus\MI^{n-1}$ has the same $p$-symbol as
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$, completing the proof (Theorem \ref{thm:PSymbol}).
\end{proof}

Our input to the algorithm is the symbol of a genus, defined as
follows.

\begin{definition}\label{def:Symbol}
Let $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ be an integral quadratic form from a given genus.
Then, the symbol the genus is defined as the set
\[
\bigcup_{p \in \{-1\} \cup
\{p \mid \ord_p(2\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})) > 0\}} \SYM_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})
\]
\end{definition}

From Theorem \ref{thm:PSymbol}, it follows that two quadratic forms are
in the same genus if they are $2^*$-equivalent and have the same
$p$-symbol for each $p \in \{-1\}\cup \mathbb{P}$.

The following theorem is a direct implication of
\cite[Theorem~9, ][page~379]{CS99}, \cite[Theorem~10, ][page~381]{CS99},
and the definition of the symbol.

\begin{theorem}\label{thm:Symbol}
Let $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1^n$ and $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2^n$ be two integral quadratic forms.
Then, the following statements are equivalent.
\vspace{-10pt}
\begin{align*}
\begin{array}{l}
\text{(a)~}\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1 \in \gen(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2), ~~~~\qquad
\text{(b)~} \det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1)=\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2)(=d),
\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1 \overset{\overline{d}}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2, \text{ and }
\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1 \overset{\mathbb{R}}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2\\
~~~~\text{(c)~}\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1 \overset{p^*}{\sim} \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2, \forall~p \in
\{-1\}\cup\{p\mid \ord_p(2\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_1\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_2))> 0 \}.\\
\end{array}
\end{align*}
\end{theorem}

Note that Theorem \ref{thm:Symbol} implies that every quadratic
form in a particular genus has the same determinant (for a proof see
page~139, Lemma 4.1, \cite{Cassels78}). The determinant of a genus
can be computed from its symbol.

We simplify the input description further by introducing the notion
of reduced symbol.

\begin{definition}\label{def:ReducedGenus}
A symbol $\Sym$ is {\em reduced} if for every relevant prime
$p \in \mathbb{P}_{\Sym}$ the $p$-scale~0 appears in $\scalep(\Sym)$.
\end{definition}

If $i_p = \min\{i \in \scalep(\Sym)\}$ then $\Sym$ is
$p^{i_p}$-equivalent to a matrix which is identically~0. Thus, if
$\MD$ is a quadratic form with $\MD \overset{p^*}{\sim} \Sym$ then every entry of
$\MD$ is divisible by $p^{i_p}$. Given a genus $\Sym$, we define
the following quantity.
\begin{align}\label{def:gcd}
\gcd(\Sym) = \underset{p \in \mathbb{P}_{\Sym}}{\prod} p^{i_p} \text{ where, }
i_p = \min\{i \in \scalep(\Sym)\}
\end{align}
The reduced symbol corresponding to the symbol $\Sym$ can now be defined
as follows.
\begin{align}\label{def:gcdSymbol}
\red(\Sym) = \left\{\SYM_p\left(\frac{\MD}{p^{\min\{i \in \scalep(\Sym)\}}}\right)\mid p \in \mathbb{P}_{\Sym}, \MD \overset{p^*}{\sim} \Upsilon_p\right\} \cup \{\SYM_{(-1)}(\Sym)\}
\end{align}

To find a quadratic form from a genus $\Sym$, it suffices to
find a quadratic form in genus $\red(\Sym)$, the proof of which
is as follows.

\begin{lemma}\label{lem:ReducedGenus}
Let $\Sym$ be a genus, and for each prime $p \in \mathbb{P}_{\Sym}$,
$i_p$ be the integer $\min\{i \in \scalep(\Sym)\}$.
Then, $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \in \red(\Sym)$ iff
$\gcd(\Sym)\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \in \Sym$.
\end{lemma}
\begin{proof}
Let $p \in \mathbb{P}_{\Sym}$ be a prime. If $\MS$ is a quadratic form such that
$\SYM(\MS)=\Sym$ then every entry of $\MS$ is divisible by $p^{i_p}$.
We define a quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ as follows.
\[
\mathtt{Q}} \newcommand{\MS}{\mathtt{S}=\frac{\MS}{\prod_{p\in\mathbb{P}_{\Sym}}p^{i_p}}
\]
By definition of $\red(\Sym)$, $\SYM_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})=\SYM_p(\red(\Sym))$
for all $p \in \{-1\} \cup \mathbb{P}_{\Sym}$. Thus, $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \in \red(\Sym)$.

Conversely, if $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \in \red(\Sym)$ then $p^{i_p}\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ has
the same $p$-symbol as $\Upsilon_p$. Thus,
$\left(\prod_{p\in\mathbb{P}_{\Sym}}p^{i_p}\right)\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ has symbol $\Sym$.
\end{proof}

\subsection{Valid Symbol}

We now define the following
three conditions on the symbol $\Sym$.

\begin{description}
\item[Determinant Condition.] For every prime $p \in \{2\} \cup \mathbb{P}$
such that
$\Upsilon_p=\left\{(p,i,\epsilon_i,n_i, *, *) \mid i \in \scalep(\Sym)\right\}$,
where $*$ is empty for odd primes;
\begin{equation}\label{Cond:det}
\legendre{\cop_p(\det(\Sym))}{p} = \prod_{i\in \scalep(\Sym)} \epsilon_i
\end{equation}

\item[Oddity Condition.] The symbol $\Sym$ satisfies the oddity
equation i.e.,
\begin{equation}\label{Cond:Sum}
\sig(\Sym) + \sum_{p \in \mathbb{P}} \excess_p(\Sym) \equiv
\odty(\Sym) \bmod 8
\end{equation}

\item[Jordan Condition.] Let $p$ be an odd prime and
$\Upsilon_p=\left\{(p,i,\epsilon_i,n_i) \mid i \in \scalep(\Sym)\right\}$,
then for each Jordan constituent $(p^i,\epsilon_i,n_i)$, we must have
\begin{equation}\label{Cond:Odd}
\text{if $n_i=0$ or $p=-1$ then $\epsilon=+$}
\end{equation}
For $p=2$, let $\SYM_2(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})= \left\{(2,i,\epsilon_i, n_i, \type_i, s_i)
\mid i \in \scalet(\Sym)\right\}$, then $\Sym$ satisfies the following
conditions.
\begin{equation}\label{Cond:2}
\begin{array}{l}
\text{for $n_i=0$, $\type_i=$II and $\epsilon_i=+$}\\
\text{for $n_i=1$,} \left\{
	\begin{array}{l}
	\epsilon_i=+ \implies s_i \equiv \pm 1 \bmod 8\\
	\epsilon_i=- \implies s_i \equiv \pm 3 \bmod 8\\
	\end{array}\right. \\
\text{for $n_i=2$,$\type_i=$I} \left\{
	\begin{array}{l}
	\epsilon_i=+ \implies s_i \equiv 0 \text{ or }\pm 2 \bmod 8\\
	\epsilon_i=- \implies s_i \equiv 4 \text{ or }\pm 2 \bmod 8\\
	\end{array}\right. \\
\end{array}
\end{equation}
\end{description}

The set of conditions are taken
from \cite[page~382-383]{CS99}. A symbol $\Sym$ which satisfies these
three conditions will be called {\em valid}.

\section{$q$-equivalent forms, $q$ composite}

Given a valid symbol $\Sym^n$, it is useful to construct a quadratic
form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ which is $q$-equivalent to $\Sym$ for a given positive
integer $q$ (see Step~3 of \textsc{GenSimple}).

The following is a helper lemma which shows how to construct a
quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ such that $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \overset{p^*}{\sim} \Sym$.

\begin{lemma}\label{lem:LocalQF}
There exists a randomized algorithm that takes a symbol $\Sym^n$
of determinant $d$, and a prime $p$ as input; performs
$O(n+\log^3p)$ ring operations over $\mathbb{Z}/p^{\ord_p(d)+k_p}\mathbb{Z}$; and outputs a
block diagonal quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ such that
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \overset{p^*}{\sim} \Sym$.
\end{lemma}
\begin{proof}
There are three different constructions: for the prime $2$, for relevant
odd prime and for the odd prime that does not divide $\det(\Sym)$.
\begin{enumerate}[(1.)]
\item The first and simplest construction deals with odd primes $p$
that do not divide $\det(\Sym)$. By Lemma \ref{lem:RelevantPrimes},
$\Upsilon_p\overset{p^*}{\sim} \det(\Sym)\oplus \MI^{n-1}$.
Hence, we set $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}=\MI^{n-1}\oplus\det(\Sym)$.

\item The second type of primes are odd primes that divide $\det(\Sym)$.
Let $\Upsilon_p=\{(p,i,\epsilon_i,n_i)\mid i \in \scalep(\Sym)\}$.
We use rejection sampling to find a quadratic non-residue modulo $p$,
say $\tau_p$. Note that generating a random non-zero element from
$\zRz{p}$ yields a quadratic non-residue with probability $1/2$.
The matrix $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$, in this case, is generated as follows.
\begin{align}\label{EQ:PDividesDetSym}
\mathtt{Q}} \newcommand{\MS}{\mathtt{S} = \underset{i \in \scalep(\Sym)}{\oplus}p^i\MD_i \qquad
\MD_i = \left\{\begin{array}{ll}
\MI^{n_i} & \text{if $\epsilon_i=1$} \\
\MI^{n_i-1}\oplus \tau_p & \text{otherwise}
\end{array}\right.
\end{align}
\item The only remaining case is of the prime~2.
Let $\Upsilon_2=
\{(2,i,\epsilon_i,n_i, \type_i, \odty_i)\mid i \in \scalet(\Sym)\}$.
Then, the
quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ is defined as
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}=\oplus_{i\in\scalet(\Sym)}2^i\MD_i^{n_i}$, where $\MD_i$
is defined as follows.
\begin{align}\label{EQ:MQ2}
\MD_i^{n_i} &= \left\{\begin{array}{ll}
\underbrace{\mathtt{T}^{+}\oplus\cdots\oplus\mathtt{T}^{+}}_{n_i/2-1}\oplus\mathtt{T}^{-}
& \text{if $\epsilon_i=-1, \odty_i=\text{II}$}\\
\underbrace{\mathtt{T}^{+}\oplus\cdots\oplus\mathtt{T}^{+}}_{n_i/2}
& \text{if $\epsilon_i=1, \odty_i=\text{II}$}\\
\MI^{n_i-3}\oplus\MD^{n=3} & \text{$\odty_i\in\{0,\cdots,7\}, n_i>3$}
\end{array}\right.
\end{align}
If $n_i=1$ then $\MD_i$
has to be equal to $\odty_i$. For $n_i=2$, we exhaustively
list all possible Type I forms in Table \ref{tab:dim2}. We observe
that two situations are not possible: $\epsilon=+, \odty=4$
and $\epsilon=-, \odty=0$. For $n_i=3$, we list forms
for all possible choices of $\epsilon$ and $\odty$.

\begin{table}
\caption{Exhaustive List of Type I forms for $n=2$}
\centering
\begin{tabular}{| l | l | l |}
\hline
Form  & $\epsilon$ & $\odty$ \\
\hline
$1\oplus 7, 3\oplus 5$ & $+$ & $0$\\
$1\oplus 1, 5\oplus 5$ &  $+$ & $2$\\
$3\oplus 3, 7\oplus 7$ &  $+$ & $6$\\
\cline{1-3}
$3\oplus 7$ 			&  $-$ & $2$\\
$1\oplus 3, 5\oplus 7$ & $-$ & $4$\\
$1\oplus 5$ 			& $-$ & $6$\\
\hline
\end{tabular}
\label{tab:dim2}
\end{table}

The $\MD$ in Equation \ref{EQ:MQ2} is defined as follows. Suppose
we are looking for a type I form in dimension $n_i>3$ with
$\odty_i \in \{0,\cdots,7\}$ and Legendre-Jacobi symbol $\epsilon_i$.
In this case, we choose $\MD$ as
the form in Table \ref{tab:dim3} with $\odty=\odty_i-(n_i-3) \bmod 8$
and $\epsilon=\epsilon_i$.

\begin{table}
\caption{List of Type I forms for $n=3$}
\centering
\begin{tabular}{| l | l | l |}
\hline
$\epsilon$ & $\odty$ & Form\\
\hline
$+$ & $1$ & $1\oplus1\oplus7$\\
& $3$ & $1\oplus1\oplus1$\\
& $5$ & $7\oplus7\oplus7$\\
& $7$ & $1\oplus7\oplus7$\\
\cline{1-3}
$-$ & $1$ &$3\oplus3\oplus3$\\
& $3$ & $3\oplus3\oplus5$\\
& $5$ & $1\oplus1\oplus3$\\
& $7$ & $1\oplus1\oplus5$\\
\hline
\end{tabular}
\label{tab:dim3}
\end{table}

By construction $\SYM_2(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})=\Upsilon_2$.
\end{enumerate}

The algorithm needs to generate a quadratic non-residue modulo
$p$ and hence performs $O(n+\log^3p)$ ring operations.
\end{proof}

\begin{theorem}\label{thm:LocalQF}
Let $\Sym^n$ be a symbol and $q$ be a composite integer. Then,
there is a randomized $\poly(n,\log q)$ algorithm that takes
$(\Sym,q)$, along with a factorization of $q$ as input; and
produces a quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ such that $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \overset{q}{\sim} \Sym$.
\end{theorem}
\begin{proof}
For each $p\in \mathbb{P}_{\Sym}$, we use Lemma \ref{lem:LocalQF} to generate
$\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_p$ such that $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}_p \overset{p^*}{\sim} \Sym$. We now solve the following
system of congruences using the Chinese Remainder Theorem.
\[
\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \equiv \mathtt{Q}} \newcommand{\MS}{\mathtt{S}_p \pmod{p^{\ord_p(q)}}\qquad p \in \mathbb{P}_q
\]
By construction, $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \overset{q}{\sim} \Sym$. The algorithm runs in time
$\poly(n, \log q)$
\end{proof}

\section{Existence of a Quadratic Form with a given Symbol}\label{sec:QFGen}

In this section, we answer the following question.
Given a symbol $\Sym^n$, how does one verify that the genus
corresponding to $\Sym$
is non-empty i.e., there exists a quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n$ such that
$\SYM(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})=\Sym$.

\begin{theorem}\label{thm:QFGen}
Let $\Sym^n$ be a valid symbol (i.e., satisfies the determinant,
oddity and the Jordan conditions); then
there exists an integral quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ such that $\SYM(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})=\Sym$.
\end{theorem}

This is a well known theorem \cite[Theorem~11, ][page~383]{CS99}.
A proof can also be found in \cite{OMeara73}. Our work, not only
shows the existence, but also generates a form in polynomial time.
In this section, we show that the algorithm \textsc{GenSimple},
if successful, generates a quadratic form from the correct genus.

\begin{proof}(Theorem \ref{thm:QFGen})
Let $\Sym^n$ be a valid input symbol. Run the \textsc{GenSimple}
algorithm on $\Sym$. We show that {\em if} the algorithm outputs a
quadratic form then it must be from the genus $\Sym$.

We prove several claims regarding
the matrices constructed during the algorithm \textsc{GenSimple}.

\begin{claim}\label{CALG:dtSym}
The determinant of the genus $\tilde{\Sym}$ is $t^{n-2}\det(\Sym)$. Also,
$t^{n-2}\det(\Sym)$ divides $\det(\mathtt{H}} \newcommand{\MI}{\mathtt{I})$.
\end{claim}
\begin{proof}
Recall that $\MS$ is a
quadratic form which is equivalent to $\Sym$ over $\zRz{q}$.
Let $\Vd$ be the row vector and $\mathtt{H}} \newcommand{\MI}{\mathtt{I}$ be the matrix defined in Equation
\ref{ALGO:dH}. Note that all entries of these matrices i.e., $\Vd, \mathtt{H}} \newcommand{\MI}{\mathtt{I}$
are integers. Define the matrix
$\mathtt{M}} \newcommand{\MN}{\mathtt{N}=\begin{pmatrix}t & \Vd \\ \Vd' & (\mathtt{H}} \newcommand{\MI}{\mathtt{I}+\Vd'\Vd)/t\end{pmatrix}$.
By definition, $\mathtt{H}} \newcommand{\MI}{\mathtt{I}+\Vd'\Vd \equiv t\mathtt{A}} \newcommand{\MB}{\mathtt{B}'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B} \bmod q$. The integer
$t$ divides $q$. But then, each entry in the matrix $\mathtt{H}} \newcommand{\MI}{\mathtt{I}+\Vd'\Vd$
is divisible by $t$ i.e., $(\mathtt{H}} \newcommand{\MI}{\mathtt{I}+\Vd'\Vd)/t$ is a matrix over integers.
Thus, $\mathtt{M}} \newcommand{\MN}{\mathtt{N}$ is a matrix over integers and the following equality
implies that $\det(\mathtt{M}} \newcommand{\MN}{\mathtt{N})=\det(\mathtt{H}} \newcommand{\MI}{\mathtt{I})/t^{n-2}$.
\begin{align}\label{ALG:M}
\mathtt{M}} \newcommand{\MN}{\mathtt{N}=\begin{pmatrix}t & \Vd \\ \Vd' & (\mathtt{H}} \newcommand{\MI}{\mathtt{I}+\Vd'\Vd)/t\end{pmatrix}=
\begin{pmatrix}1 & \Vd/t \\ 0 & \MI\end{pmatrix}'
\begin{pmatrix}t & 0 \\ 0 & \mathtt{H}} \newcommand{\MI}{\mathtt{I}/t\end{pmatrix}
\begin{pmatrix}1 & \Vd/t \\ 0 & \MI\end{pmatrix}
\end{align}
From Equation \ref{ALGO:dH}, it follows that
$(\mathtt{H}} \newcommand{\MI}{\mathtt{I}+\Vd'\Vd)/t \equiv \mathtt{A}} \newcommand{\MB}{\mathtt{B}'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B} \bmod{q/t}$. By definition,
$\mathtt{M}} \newcommand{\MN}{\mathtt{N} \equiv (\Vx~\mathtt{A}} \newcommand{\MB}{\mathtt{B})'\MS(\Vx~\mathtt{A}} \newcommand{\MB}{\mathtt{B}) \bmod{q/t}$. Hence,
\begin{align}\label{EQALG:dS}
\det((\Vx~\mathtt{A}} \newcommand{\MB}{\mathtt{B})'\MS(\Vx~\mathtt{A}} \newcommand{\MB}{\mathtt{B})) \equiv  \det(\mathtt{M}} \newcommand{\MN}{\mathtt{N}) \bmod{q/t}
= \frac{\det(\mathtt{H}} \newcommand{\MI}{\mathtt{I})}{t^{n-2}} \bmod{q/t}\nonumber\\
t^{n-2}\det(\MS)\det(\Vx~\mathtt{A}} \newcommand{\MB}{\mathtt{B})^2 \equiv \det(\mathtt{H}} \newcommand{\MI}{\mathtt{I}) \bmod{qt^{n-3}}\;
\end{align}
Let $p$ be a prime divisor of $q$. Recall $(\Vx~\mathtt{A}} \newcommand{\MB}{\mathtt{B}) \in \gln(\zRz{q})$.
But then, $p$ does not divide $\det(\Vx~\mathtt{A}} \newcommand{\MB}{\mathtt{B})$. From the fact that
$\MS$ is equivalent to $\Sym$ over $\zRz{q}$, it follows that
$\ord_p(\det(\MS))=\ord_p(\det(\Sym))$. By definition of $q$,
it follows that $\ord_p(q)>\ord_p(\det(\Sym) t^{n-1})$. But then,
\begin{align}\label{EQALG:MOD}
\ord_p(t^{n-2}&\det(\MS)\det(\Vx~\mathtt{A}} \newcommand{\MB}{\mathtt{B})^2)=\ord_p(t^{n-2})+\ord_p(\det(\MS))\nonumber\\
&=\ord_p(t^{n-2})+\ord_p(\det(\Sym)) < \ord_p(q)
\end{align}
From Equation \ref{EQALG:dS} and Equation \ref{EQALG:MOD}, we
conclude that for all primes $p$ that divide $q$,
$\ord_p(\det(\mathtt{H}} \newcommand{\MI}{\mathtt{I}))=\ord_p(t^{n-2}\det(\MS))=\ord_p(t^{n-2}\det(\Sym))$.

It also follows from the definition of
the symbol that $\ord_p(\det(\tilde{\Sym}))=\ord_p(\det(\mathtt{H}} \newcommand{\MI}{\mathtt{I}))$ for
all relevant primes of symbol $\tilde{\Sym}$. But we showed that
$\ord_p(\det(\mathtt{H}} \newcommand{\MI}{\mathtt{I}))=\ord_p(t^{n-2}\det(\Sym))$ for every relevant
prime $p$ of $\tilde{\Sym}$.
Thus, $\det(\tilde{\Sym})=t^{n-2}\det(\Sym)$.
\end{proof}

We now show that $\tilde{\Sym}$ defined in Equation \ref{def:tSym}
is a valid symbol.

\begin{theorem}\label{thm:Existence}\label{thm:tSymExists}
Let $\Sym^{n>1}$ be a valid symbol,
$t$ be a primitively representable integer in $\Sym$,
$q=\overline{t^{n-1}\det(\Sym)}$,
$\MS^n$ be an integral quadratic form with $\MS \overset{q}{\sim} \Sym$,
$\Vx \in (\zRz{q})^n$ be a primitive vector with $\Vx'\MS\Vx\equiv t \bmod{q}$,
$\mathtt{A}} \newcommand{\MB}{\mathtt{B}$ be such that $[\Vx, \mathtt{A}} \newcommand{\MB}{\mathtt{B}] \in \gln(\zRz{q})$, $\Vd:=\Vx'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B} \bmod q$,
$\mathtt{H}} \newcommand{\MI}{\mathtt{I}^{n-1}:=(t\mathtt{A}} \newcommand{\MB}{\mathtt{B}'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B} - \Vd'\Vd) \bmod q$ and
$\tilde{\Sym}$ be as defined in Equation \ref{def:tSym}; then $\tilde{\Sym}$
is a valid symbol.
\end{theorem}

\begin{proof}
We divide the proof in three items, one for each condition.
\begin{enumerate}[(i).]
\item (Oddity Condition)
Consider the
matrix $\mathtt{M}} \newcommand{\MN}{\mathtt{N}$ over integers (note that $t$ divides both $q$ and
$\mathtt{H}} \newcommand{\MI}{\mathtt{I}+\Vd'\Vd$ and so $(\mathtt{H}} \newcommand{\MI}{\mathtt{I}+\Vd'\Vd)/t$ is integral).
\[
\mathtt{M}} \newcommand{\MN}{\mathtt{N}=\begin{pmatrix}t & \Vd \\ \Vd' & (\mathtt{H}} \newcommand{\MI}{\mathtt{I}+\Vd'\Vd)/t\end{pmatrix}=
\begin{pmatrix}1 & \Vd/t \\ 0 & \MI\end{pmatrix}'
\begin{pmatrix}t & 0 \\ 0 & \mathtt{H}} \newcommand{\MI}{\mathtt{I}/t\end{pmatrix}
\begin{pmatrix}1 & \Vd/t \\ 0 & \MI\end{pmatrix}
\]
The matrix $\mathtt{V}} \newcommand{\MW}{\mathtt{W}=\begin{pmatrix}1 & \Vd/t \\ 0 & \MI\end{pmatrix}$ is over
rationals and has determinant~1. Thus, $\mathtt{M}} \newcommand{\MN}{\mathtt{N}$ is equivalent
to $\diag(t, \mathtt{H}} \newcommand{\MI}{\mathtt{I}/t)$ over rationals. By construction,
$\mathtt{M}} \newcommand{\MN}{\mathtt{N} \overset{q}{\sim} \MS \overset{q}{\sim} \Sym$. From \cite[Theorem~3, ][page~372]{CS99},
it follows that for all prime $p$ that divides $q$,
\begin{align}\label{tSymExists:PExcess}
\excess_p(\Sym)=\excess_p(\mathtt{M}} \newcommand{\MN}{\mathtt{N})=\excess_p(t \oplus \mathtt{H}} \newcommand{\MI}{\mathtt{I}/t)
= \excess_p(t)+\excess_p(\mathtt{H}} \newcommand{\MI}{\mathtt{I}/t)
\end{align}
By the hypothesis of the theorem, the oddity condition holds for the
symbol $\Sym$. And so,
\begin{align*}
0 &\equiv \sum_{p\in \mathbb{P}_q \cup\{-1\}} \excess_p(\Sym)
  \equiv \sig(\Sym)-n+\sum_{p|q}\left( \excess_p(t)+\excess_p(\mathtt{H}} \newcommand{\MI}{\mathtt{I}/t)\right) \\
  &\equiv \sig(\Sym)-(n-1)-\sig(t)+(\sig(t)-1)+\sum_{p|q} \left(\excess_p(t)+\excess_p(\mathtt{H}} \newcommand{\MI}{\mathtt{I}/t) \right)\\
  &\equiv \sig(t)(1+\sig(\tilde{\Sym}))-(n-1)-\sig(t)+\sum_{p|q} \excess_p(\mathtt{H}} \newcommand{\MI}{\mathtt{I}/t)\\
  &\equiv \sig(t)\sig(\tilde{\Sym})-(n-1)+\sum_{p|q} \excess_p(t\mathtt{H}} \newcommand{\MI}{\mathtt{I}) \\
  &\equiv \sig(t)\sig(\tilde{\Sym})-(n-1)+\sum_{p|q} \excess_p(t\tilde{\Sym}) \pmod{8}
\end{align*}
From \cite[Theorem~5, ][page~372]{CS99}, it follows that there exists a (rational)
quadratic form $\mathtt{X}} \newcommand{\MY}{\mathtt{Y}$ which is equivalent to $\tilde{\Sym}$ over rationals.
This also implies that $\tilde{\Sym}$ satisfies the oddity condition (Theorem
\ref{thm:oddity}).

\item (Determinant Condition)
By definition, $\mathtt{H}} \newcommand{\MI}{\mathtt{I} \overset{q}{\sim} \tilde{\Sym}$. By item (i), $\mathtt{X}} \newcommand{\MY}{\mathtt{Y}$ is equivalent to $\tilde{\Sym}$
over rationals. Thus, $\frac{\det(\mathtt{H}} \newcommand{\MI}{\mathtt{I})}{\det(\tilde{\Sym})}$ is a rational square
modulo $q$ \cite[Theorem~3, ][page~372]{CS99}). From Claim \ref{CALG:dtSym},
there exists an integer $x$ such that
\begin{align}\label{tSymExists:Square}
\det(\mathtt{H}} \newcommand{\MI}{\mathtt{I}) \equiv t^{n-2}\det(\Sym) x^2 \pmod{q}
\end{align}
But then, for all primes $p$ that divide $q$,
\begin{equation*}
\prod_{i\in \mathbb{I}_p(\tilde{\Sym})} \epsilon_i =
\legendre{\cop_p\left(\det(\mathtt{H}} \newcommand{\MI}{\mathtt{I})\right)}{p} =
\legendre{\cop_p\left(\det(\tilde{\Sym})x^2\right)}{p}=
\legendre{\cop_p\left(\det(\tilde{\Sym})\right)}{p}
\end{equation*}
This equality show that the determinant condition holds for all primes
$p$ that divide $q$. For all other primes, the determinant condition
holds by construction.

\item (Jordan Condition) The Jordan constituents of the $\mathtt{H}} \newcommand{\MI}{\mathtt{I}$ are
 the same as the Jordan constituents of $\tilde{\Sym}$ for all relevant
 primes of $\det(\tilde{\Sym})$. This is because for all relevent primes $p$ of
 $\tilde{\Sym}$, $\tilde{\Sym}_p=\SYM_p(\mathtt{H}} \newcommand{\MI}{\mathtt{I})$. The quadratic form $\mathtt{H}} \newcommand{\MI}{\mathtt{I}$ is integral and so
 its Jordan constituents exist, proving that the Jordan Condition
 is satisfied for $\tilde{\Sym}$.
\end{enumerate}
\end{proof}

\begin{claim}\label{CALG:QisIntegral}
The matrix $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ is an integral quadratic form with determinant
$\det(\Sym)$ and signature $\sig(\Sym)$.
\end{claim}
\begin{proof}
The matrix $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ is symmetric by construction. By Claim \ref{CALG:dtSym},
the determinant of $\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}$ equals $t^{n-2}\det(\Sym)$. Thus, the following
equality implies that the determinant of $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ equals $\det(\Sym)$.
\begin{align}\label{EQ:dSym}
\mathtt{Q}} \newcommand{\MS}{\mathtt{S} =
\begin{pmatrix}t & \Vd\tilde{\MU} \\ \tilde{\MU}'\Vd' &
\frac{\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}+\tilde{\MU}'\Vd'\Vd\tilde{\MU}}{t}\end{pmatrix}=
\begin{pmatrix}1 & \frac{\Vd\tilde{\MU}}{t} \\ 0 & \MI\end{pmatrix}'
\begin{pmatrix}t & 0 \\ 0 & \frac{\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}}{t}\end{pmatrix}
\begin{pmatrix}1 & \frac{\Vd\tilde{\MU}}{t} \\ 0 & \MI\end{pmatrix}
\end{align}
Let $\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}$ be the integral quadratic form with symbol $\tilde{\Sym}$,
$\mathtt{H}} \newcommand{\MI}{\mathtt{I}:=t\mathtt{A}} \newcommand{\MB}{\mathtt{B}'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B}-\Vd'\Vd \bmod{q}$, and
$\tilde{\MU}$ be such that $\tilde{\MU}'\mathtt{H}} \newcommand{\MI}{\mathtt{I}\tilde{\MU}\equiv\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}} \bmod{q}$. Then,
\begin{align}\label{CEQ:Lambda}
\begin{pmatrix}1 & 0 \\ 0 & \tilde{\MU}\end{pmatrix}'
(\Vx~\mathtt{A}} \newcommand{\MB}{\mathtt{B})'\MS(\Vx~\mathtt{A}} \newcommand{\MB}{\mathtt{B})
\begin{pmatrix}1 & 0 \\ 0 & \tilde{\MU}\end{pmatrix} \bmod q
&=\begin{pmatrix}t & \Vd\tilde{\MU} \\ (\Vd\tilde{\MU})' & \tilde{\MU}'\mathtt{A}} \newcommand{\MB}{\mathtt{B}'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B}\tilde{\MU}\end{pmatrix}
\bmod q \\
t\tilde{\MU}'\mathtt{A}} \newcommand{\MB}{\mathtt{B}'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B}\tilde{\MU} - \tilde{\MU}'\Vd'\Vd\tilde{\MU} \equiv  \tilde{\MU}'\mathtt{H}} \newcommand{\MI}{\mathtt{I}\tilde{\MU}
&\equiv \tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}} \bmod{q}\label{EQ:Integer}
\end{align}
The integer $t$ divides $q$. By Equation
\ref{EQ:Integer}, $\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}+\tilde{\MU}'\Vd'\Vd\tilde{\MU}\equiv 0 \bmod{t}$. But then,
$t$ divides every entry of the matrix
$\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}+\tilde{\MU}'\Vd'\Vd\tilde{\MU}$ and so $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ is an integral matrix.

Finally, by Equation \ref{EQ:dSym}, $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \overset{\mathbb{R}}{\sim} t\oplus\frac{\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}}{t}$. Hence,
\[
\sig(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}) = \sig(t) + \sig(\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}})\sig(t) = \sig(t)+\sig(\tilde{\Sym})\sig(t)
\overset{(\ref{def:tSym})}{=}\sig(\Sym)
\]
\end{proof}

The proof of Theorem \ref{thm:QFGen} now proceeds as follows.
\begin{enumerate}[(i).]
\addtolength{\itemsep}{-5pt}
\item If the symbol $\Sym$ is valid, then there exists an integer $t$,
which has a primitive representation in $\Sym$ (see Theorem \ref{thm:ExistenceOfRep}).

\item
If $\Sym^n$ satisfies the determinant, oddity and the Jordan
conditions i.e., Equations (\ref{Cond:det})-(\ref{Cond:2}); then
so does $\tilde{\Sym}$. (Theorem \ref{thm:tSymExists})

\item The symbol $\tilde{\Sym}$ is well defined and has a short description.
In particular, by Claim \ref{CALG:dtSym},
$\det(\tilde{\Sym})=t^{n-2}\det(\Sym)$ and $\tilde{\Sym}$ can equivalently be written
as follows.
\begin{align}\label{def:tSym2}
\tilde{\Sym}=\left(\cup_{p \in \mathbb{P}_q}\SYM_p(\mathtt{H}} \newcommand{\MI}{\mathtt{I})\right) \cup
\{\sig(t)(\sig(\Sym)-\sig(t))\}
\end{align}

\item The output matrix $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ has determinant $\det(\Sym)$. It also
has the same signature as $\sig(\Sym)$. Thus, $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \overset{\mathbb{R}}{\sim} \Sym$.

\item
If $n=1$ then $\det(\Sym)$ is the unique matrix with determinant
equal to the determinant of the symbol $\Sym$. This follows from
the Determinant Condition.

\item
If $n>1$ then, it remains to show that for every relevant
prime of $\Sym$, $\SYM_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})=\Upsilon_p$.
Consider the following sequence of congruences.
\begin{align*}
t\mathtt{Q}} \newcommand{\MS}{\mathtt{S} &=
\begin{pmatrix}t^2 & t\Vd\tilde{\MU} \\ t(\Vd\tilde{\MU})'
& \tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}+\tilde{\MU}'\Vd'\Vd\tilde{\MU}\end{pmatrix}\\
&\equiv
\begin{pmatrix}t^2 & t\Vd\tilde{\MU} \\ t(\Vd\tilde{\MU})'
& \tilde{\MU}'\mathtt{H}} \newcommand{\MI}{\mathtt{I}\tilde{\MU}+\tilde{\MU}'\Vd'\Vd\tilde{\MU}\end{pmatrix} \bmod q\\
&\equiv
\begin{pmatrix}1 & 0 \\ 0 & \tilde{\MU}\end{pmatrix}'
\begin{pmatrix}t^2 & t\Vd \\ t\Vd'
& \mathtt{H}} \newcommand{\MI}{\mathtt{I}+\Vd'\Vd\end{pmatrix}
\begin{pmatrix}1 & 0 \\ 0 & \tilde{\MU}\end{pmatrix} \bmod q\\
&\overset{(\ref{ALGO:dH})}{\equiv}
\begin{pmatrix}1 & 0 \\ 0 & \tilde{\MU}\end{pmatrix}'
\begin{pmatrix}t^2 & t\Vd \\ t\Vd'
& t\mathtt{A}} \newcommand{\MB}{\mathtt{B}'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B}\end{pmatrix}
\begin{pmatrix}1 & 0 \\ 0 & \tilde{\MU}\end{pmatrix} \bmod q\\
&\overset{(\ref{ALGO:dH})}{\equiv}
\begin{pmatrix}1 & 0 \\ 0 & \tilde{\MU}\end{pmatrix}'
\begin{pmatrix}t\Vx'\MS\Vx & t\Vx'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B} \\ t\mathtt{A}} \newcommand{\MB}{\mathtt{B}'\MS\Vx
& t\mathtt{A}} \newcommand{\MB}{\mathtt{B}'\MS\mathtt{A}} \newcommand{\MB}{\mathtt{B}\end{pmatrix}
\begin{pmatrix}1 & 0 \\ 0 & \tilde{\MU}\end{pmatrix} \bmod q\\
&\equiv
\begin{pmatrix}1 & 0 \\ 0 & \tilde{\MU}\end{pmatrix}'
\begin{pmatrix}\Vx & \mathtt{A}} \newcommand{\MB}{\mathtt{B}\end{pmatrix}'t\MS
\begin{pmatrix}\Vx & \mathtt{A}} \newcommand{\MB}{\mathtt{B}\end{pmatrix}
\begin{pmatrix}1 & 0 \\ 0 & \tilde{\MU}\end{pmatrix} \bmod q\\
\mathtt{Q}} \newcommand{\MS}{\mathtt{S} &\equiv
\begin{pmatrix}1 & 0 \\ 0 & \tilde{\MU}\end{pmatrix}'
\begin{pmatrix}\Vx & \mathtt{A}} \newcommand{\MB}{\mathtt{B}\end{pmatrix}'\MS
\begin{pmatrix}\Vx & \mathtt{A}} \newcommand{\MB}{\mathtt{B}\end{pmatrix}
\begin{pmatrix}1 & 0 \\ 0 & \tilde{\MU}\end{pmatrix} \bmod {q/t}\\
\end{align*}
Recall, $\tilde{\MU} \in \gl_{n-1}(\zRz{q})$ and $(\Vx~\mathtt{A}} \newcommand{\MB}{\mathtt{B}) \in \gln(\zRz{q})$.
This implies that $\MU=[\Vx,\mathtt{A}} \newcommand{\MB}{\mathtt{B}](1\oplus\tilde{\MU}) \in \gln(\zRz{q})$. But then,
$\MU\in \gln(\mathbb{Z}/\frac{q}{t}\mathbb{Z})$ and $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \overset{q/t}{\sim} \MS$.
Note that for every prime $p$ that divides $2\det(\Sym)$ the following
holds because $\ord_p(q/t) > \ord_p(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})) + k_p$.
\[
\ord_p(\det(\Sym)) = \ord_p(\det(\mathtt{Q}} \newcommand{\MS}{\mathtt{S})) = \ord_p(\det(\MS))
\]
Thus, by definition of $p^*$-equivalence one concludes that
for every $p$ that divides $2\det(\Sym)$, $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \overset{p^*}{\sim} \MS$;
completing the proof of Theorem \ref{thm:QFGen}.
\end{enumerate}
\end{proof}

\section{Primitive Representation in a Genus}

An important step in the algorithm \textsc{GenSimple}
is to find an integer $t$ which has a
primitive representation in the genus $\Sym$.

Recall
Definition \ref{def:PrimRepInGenus}. The following lemma shows
that if $n\geq 2$ then $t$ has a primitive $p^*$-representation
in $\Sym$ for all primes $p$ such that $p$ does not divide
$2\det(\Sym)$. A proof of this lemma can already be found in Siegel
\cite{Siegel35}, although in a different setting.

\begin{lemma}\label{lem:Siegel12}
Let $\Sym^{n\geq 2}$ be a valid genus, $t$ be an integer and
$p$ be an odd prime which does not divide $t\det(\Sym)$.
Then, $t$ has a primitive $p^*$-representation in $\Sym$.
\end{lemma}
\begin{proof}
Let $p$ be an odd prime which does not divide $t\det(\Sym)$. Then,
by Lemma \ref{lem:RelevantPrimes},
$\Sym \overset{p^*}{\sim} \diag(\det(\Sym),1,\cdots,1)$. It suffices to show that
$t$ has a primitive representation in $\diag(\det(\Sym),1)$ over
$\zRz{p}$ (Theorem \ref{thm:Siegel13}).

By assumption, $\det(\Sym)$ and $1$ are invertible modulo $p$.
If $\legendre{t}{p}$ is the same as the Legendre symbol of $\det(\Sym)$ or $1$
(say, $\det(\Sym)$) then $x^2\equiv t\det(\Sym)^{-1} \pmod{p}$ has a
non-trivial solution.
Otherwise, $\det(\Sym)$ and $1$ have the same Legendre symbol, different
from $t$. But then the result follows from Lemma \ref{lem:QR}.
\end{proof}

\begin{theorem}\label{thm:ExistenceOfRep}
Let $\Sym^{n\geq 2}$ be a valid genus and $\mathtt{Q}} \newcommand{\MS}{\mathtt{S} \in \Sym$. A positive
integer $t$ has a primitive representation in
$\Sym$ if $t$ has a primitive $p^{K_p}$-representation in $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}$ for all
$p$ that divides $2t\det(\Sym)$, where
$K_p= \max\{\ord_p(\mathtt{Q}} \newcommand{\MS}{\mathtt{S}),\ord_p(t)\}+k_p$.
\end{theorem}
\begin{proof}
Follows from Theorem \ref{thm:Siegel13}, Lemma \ref{lem:Siegel12} and
the definition of primitive representations in a genus.
\end{proof}

This simplifies our problem in the algorithmic sense. To find an
integer $t$ which has a
primitive representation in the genus $\Sym^{n\geq 2}$, we only need
to check all primes $p$ that divide $2t\det(\Sym)$ and only over
the ring $\mathbb{Z}/p^{K_p}\mathbb{Z}$ for $K_p=\max\{\ord_p(\Sym),\ord_p(t)\}+k_p$.

For $n>3$, it is comparatively
easy to find a $t$; in fact, it is possible to find a $t$ which divides
$\det(\Sym)$. But for dimensions $n=3$ and $n=2$, the proof
deteriorates to case analyses, especially for dimension~2.
The proofs are constructive in the sense that it is
also possible to find a representation $\Vx$ such that
$\Vx'\MS\Vx\equiv t\bmod{q}$ in time $\poly(n ,\log \det(\Sym))$.

In this section, we prove the following theorem.

\begin{theorem}\label{thm:FindT}
Let $\Sym^{n\geq 2}$ be a valid reduced genus. Then, there
exists a randomized algorithm that takes $\Sym$ as input; runs in time
$\poly(|\mathbb{P}_{\Sym}|, \log \det(\Sym))$ and outputs
an integer $t$ which has a primitive representation in the genus $\Sym$.
\end{theorem}

Note that the run time of the algorithm does not depend on $n$. This
is because for $n=4$, we can already find a nice $t$ which divides
$\det(\Sym)$ and we ignore the later dimensions. When we want to find
an $\Vx$ such that $\Vx'\MS\Vx\equiv t \bmod{q}$ then we use the same
trick and only represents $t$ using at most $4\times 4$ sub-form of
$\MS$ (see Section \ref{sec:QFGen}).

But before starting the construction of $t$, we prove two lemmas
which are going to be useful.

\begin{lemma}\label{lem:RepMod2Dim4}
Let $t$ be an odd integer, and
$2^{i_1}\tau_1 \oplus \cdots \oplus 2^{i_4}\tau_4$ be an
integral quadratic form with $\tau_1, \cdots, \tau_4$ odd and
$i_1\leq \cdots \leq i_4$. Then, $2^{i_4}t$ has a $2^*$-primitive
representation in $\MD$. Additionally, for every positive integer $k$
there exists a primitive $2^k$-representation $(x_1,\cdots,x_4)$ such
that $\ord_2(x_4)=0$ and $\ord_2(2^{i_j}\tau_jx_i^2)\geq i_4$,
for all $j \in [4]$.
\end{lemma}
\begin{proof}
Let $k=i_4+3$, then  it suffices to show that the following has a
primitive solution (see Theorem \ref{thm:Siegel13}).
\begin{align}\label{RepMod2Dim4:EQ1}
2^{i_1}\tau_1 x_1^2 + \cdots + 2^{i_4}\tau_4x_4^2 \equiv 2^{i_4}t \pmod{2^{i_4+4}}
\end{align}
We find a primitive solution where $x_4$ is odd. For $j \in [3]$, we set
$x_j = 2^{\lceil \frac{i_4-i_j}{2} \rceil}y_j$ and divide the entire
Equation \ref{RepMod2Dim4:EQ1} by $2^{i_4}$. The equation then
reduces to the following.
\begin{align}\label{RepMod2Dim4:EQ2}
\sum_{j \in [3]} 2^{(i_4-i_j) \bmod 2}\tau_j y_j^2 + \tau_4x_4^2 \equiv t \pmod{16}
\end{align}
An exhaustive search shows that for each possible choice of odd
$t$ in $\mathbb{Z}/16\mathbb{Z}$,
$\tau_1,\cdots, \tau_4 \in \{1,3,5,7\}$ and $i_4-i_j \pmod 2$, the Equation
\ref{RepMod2Dim4:EQ2} always has a solution, where  $x_4$ is odd.
\end{proof}

\begin{lemma}\label{lem:RepModPDim2}
Let $p$ be an odd prime,
$\MD=\tau_1 \oplus p^{i}\tau_2$,
where $\tau_1, \tau_2\in (\zRz{p})^\times$, $i$ even
and $t \in (\zRz{p})^\times$ such that
$\legendre{t}{p}\neq \legendre{\tau_1}{p}$. Then,
$p^it$ has a $p^*$-primitive representation in $\MD$.
\end{lemma}
\begin{proof}
If $\legendre{t}{p}=\legendre{\tau_2}{p}$, then
$p^{i}t$ has the same symbol as $p^{i}\tau_1$ and then
$p^{i}t$ has a primitive $p^*$-representation
in $p^i\tau_2$. Otherwise, from the statement of the lemma,
$\legendre{t}{p}\neq \legendre{\tau_1}{p}=\legendre{\tau_2}{p}$.

In this case, $t$ can always be written as
$t \equiv \tau_1y_1^2+\tau_2y_2^2 \pmod{p}$, where both $y_1$ and $y_2$ are
units of $\zRz{p}$. But then,
\begin{align*}
p^{i}t &\equiv p^{i}\tau_1y_1^2 + p^{i}\tau_2y_2^2 \pmod{p^{i+1}} \\
		&\equiv \tau_1(p^{i/2}y_1)^2 + p^{i}\tau_2y_2^2 \pmod{p^{i+1}}.
\end{align*}
It follows that $p^it$ has a primitive representation by
$\tau_1\oplus p^i\tau_2$ over $\mathbb{Z}/p^{i+1}\mathbb{Z}$. By Theorem
\ref{thm:Siegel13}, $p^{i}t$ has a $p^*$-primitive representation in $\MD$.
\end{proof}

\subsection{Representation: $n>3$}

As mentioned earlier, we construct an integer
$t$ such that $t$ divides $\det(\Sym)$ and $t$ has a primitive
representation in the input genus $\Sym$. It turns out that
when $n>3$ we do not need to use the fact that the input symbol
$\Sym$ is reduced.

\begin{lemma}\label{lem:TInDim4}
Let $\Sym^{n>3}$ be a genus. Then, there exists an integer
$t$ such that $t$ divides $\det(\Sym)$ and $t$ has a primitive
representation in the genus $\Sym$.
\end{lemma}
\begin{proof}
Let us suppose that $p$ is an odd prime that divides $\det(\Sym)$. In this
case, we construct a diagonal form using Lemma \ref{lem:LocalQF} as follows.
\begin{align}\label{TInDim4:Local}
\Upsilon_p \overset{p^*}{\sim} p^{i_1}\tau_1 \oplus p^{i_2}\tau_2 \oplus \cdots
~~~~~~ \tau_1,\tau_2, \cdots \in (\zRz{p})^{\times}, i_1\leq i_2 \leq \cdots
\end{align}
An integer can be equivalently written as
$\prod_{p\in\{-1,2\}\cup \mathbb{P}} p^{e_p}$, where $e_p$ is the $p$-order
of the integer. The construction
of the integer $t$ is as follows.
\begin{enumerate}[(i).]
\item For every odd prime that does not divide $\det(\Sym)$,
$e_p$ is identically~0. Also, if $\sig(\Sym)>-n$, then we set $e_{-1}=0$.
Otherwise, $e_{-1}=1$.

\item For every odd prime $p$ that divide $\det(\Sym)$ our first step
is to compute the value of $e_p \bmod 2$. Consider a prime $p$ that
divides $\det(\Sym)$. Consider the quadratic form constructed in Equation
\ref{TInDim4:Local} for the prime $p$. Then,
\begin{align}\label{TInDim4:Parity}
e_p \bmod 2 := \maj(i_1 \bmod 2, i_2\bmod 2, i_3 \bmod 2)
\end{align}

\item Next we compute $e_2$. If $\Sym_2$ has a type II
block of $2$-order $\ell$, then we set $\ord_2(t)=\ell+1$.
Otherwise, $\Sym_2$ has only Type I blocks.
Thus, $\Sym$ is $2$-equivalent to
a diagonal matrix $2^{j_1}{\tilde{\tau}}_1 \oplus \cdots$, where ${\tilde{\tau}}_1,\cdots$
are odd and $j_1\leq j_2\leq \cdots$. The value of
$j_1, \cdots, j_4$ can be read off the symbol $\Upsilon_2$ as
the four smallest possible $2$-orders in $\Sym_2$. We set
$e_2=j_4$.

\item Once the parity of all $p \in \{-1,2\}\cup \mathbb{P}$ is known (see item
(i)-(iii)), we define an integer $r$ as follows.
\begin{align}\label{TInDim4:r}
r = \prod_{p \in \{-1,2\} \cup \mathbb{P}} p^{e_p \bmod 2}
\end{align}

\item
Finally, we compute $e_p$ for all odd primes $p$ which divide
$\det(\Sym)$. Consider the diagonal form constructed in Equation
\ref{TInDim4:Local} for the prime $p$. Out of $(i_1,i_2), (i_2,i_3),$
and $(i_1,i_3)$;
let $(i_a,i_b), a < b \in \{1,2,3\}$ be the pair with the same parity.
Then,
\begin{align}\label{TInDim4:ep}
e_p = \left\{
	\begin{array}{ll}
	i_a & \text{if } \legendre{\cop_p(r)}{p} = \legendre{\tau_a}{p},\\
	i_b & \text{otherwise}
	\end{array}
	\right.
\end{align}
\item We now have $e_p$ for every $p \in \{-1,2\} \cup \mathbb{P}$. We define
our integer $t$ as follows.
\begin{align}\label{TInDim4:t}
t = \prod_{p \in \{-1,2\}\cup \mathbb{P}} p^{e_p}
\end{align}
\end{enumerate}

The next step is to show that $t$ has a primitive representation in the genus
$\Sym$, or equivalently, $t$ has a $p^*$-primitive
representation in $\Sym$ for all $p \in \{-1,2\} \cup \mathbb{P}$.
\begin{enumerate}[(i).]
\item ($p=-1$) By construction, $t$ is negative iff $\sig(\Sym)=-n$. In this
case $\Sym$ is a genus of negative definite matrices and hence must represent
every negative integer over $\mathbb{R}$. Otherwise, $t$ is a positive integer and
$\Sym$ is a genus of non-negative definite matrices i.e.,
$\Sym \overset{\mathbb{R}}{\sim} 1\oplus\cdots$. Hence, $\Sym$ must represent all positive integers
over $\mathbb{R}$. In either case, the constructed $t$ has a primitive representation
in $\Sym$ over $\mathbb{R}$.

\item ($p$ odd, $p$ does not divide $\det(\Sym)$) In this case, $p$ does
not divide $t$. Hence, $t$ has a $p^*$-primitive representation in $\Sym$
(Lemma \ref{lem:Siegel12}).

\item ($p=2$) If $\Upsilon_2$ has a Type II block then $\ord_2(t)=\ell+1$, where
$\ell$ is the $2$-order of one of the Type II blocks. Then, the Type II
block represents every integer of $2$-order $\ell+1$ (by Lemma
\ref{lem:RepresentTTypeII}). The existence of a
$2^*$-primitive representation now follows from
Lemma \ref{lem:Siegel12}. Otherwise, there are only Type I blocks in $\Upsilon_2$
and the existence of a $2^*$-primitive representation follows from
Lemma \ref{lem:RepMod2Dim4} and Theorem \ref{thm:Siegel13}.

\item ($p$ odd, $p$ divides $\det(\Sym)$) By construction, $e_p$ has the
same parity as $i_a$ and $i_b$, see item (v) of the construction of $t$
and Equation \ref{TInDim4:ep}. Thus, $\ord_p(t) \equiv \ord_p(r) \pmod 2$, or
\[
\legendre{\cop_p(t)}{p} = \legendre{\cop_p(r)}{p}
\]
By Equation \ref{TInDim4:ep}, $e_p=i_a$ if
$\legendre{\cop_p(t)}{p}=\legendre{\tau_a}{p}$ and $e_p=i_b$, otherwise.
If $\legendre{\cop_p(t)}{p}=\legendre{\tau_a}{p}$ then $t$ can be $p^*$-primitively
represented by the diagonal entry $p^{i_a}\tau_a$ in Equation
\ref{TInDim4:Local}. Otherwise, $t$ can be $p^*$-primitively represented
by $p^{i_a}\tau_a \oplus p^{i_b}\tau_b$ (see Lemma \ref{lem:RepModPDim2}).
In either case, $t$ has a
$p^*$-primitive representation in $\Upsilon_p$.
\end{enumerate}
\end{proof}

\subsection{Representation: $n=3$}

In this case, we construct an integer
$t$ with the following properties. If the input
genus $\Upsilon_2$ has a Type II block then the constructed
$t$ divides $\det(\Sym)$. Otherwise, $t$ is of the form
$\wp {\tilde{t}}$, where ${\tilde{t}}$ divides $\det(\Sym)$ and $\wp$
is an odd prime that does not divide $\det(\Sym)$.

\begin{lemma}\label{lem:TInDim3}
Let $\Sym^{n=3}$ be a genus. Then, there exists an integer
$\wp {\tilde{t}}$ such that ${\tilde{t}}$ divides $\det(\Sym)$,
$\wp\in\mathbb{P}\setminus\mathbb{P}_{\Sym}$ and $\wp {\tilde{t}}$
has a primitive representation in the genus $\Sym$.
\end{lemma}
\begin{proof}
Let us suppose that $p$ is an odd prime that divides $\det(\Sym)$. In this
case, we construct a diagonal form using Lemma \ref{lem:LocalQF} as follows.
\begin{align}\label{TInDim3:Local}
\Upsilon_p \overset{p^*}{\sim} p^{i_1}\tau_1 \oplus p^{i_2}\tau_2 \oplus p^{i_3}\tau_3
~~~ \tau_1,\tau_2, \tau_3 \in (\zRz{p})^{\times}, i_1\leq i_2 \leq i_3
\end{align}
An integer can be equivalently written as
$\prod_{p\in\{-1,2\}\cup \mathbb{P}} p^{e_p}$, where $e_p$ is the $p$-order
of the integer. The construction
of the integer $t$ is as follows.
\begin{enumerate}[(i).]
\item if $\sig(\Sym)>-3$, then we set $e_{-1}=0$.  Otherwise, $e_{-1}=1$.

\item For every odd prime $p$ that divides $\det(\Sym)$, our first step
is to compute the value of $e_p \bmod 2$.
Consider the quadratic form constructed in Equation
\ref{TInDim4:Local} for the prime $p$. Then,
\begin{align}\label{TInDim3:Parity}
e_p \bmod 2 := \maj\{i_1 \bmod 2, i_2\bmod 2, i_3 \bmod 2\}
\end{align}

\item If $\Sym_2$ has a type II
block of $2$-order $\ell$, then we set $\ord_2(t)=\ell+1$. Also, for
all odd primes $p \not\in \mathbb{P}_{\Sym}$, we set $e_p=0$.

\item
Otherwise, $\Sym_2$ has only Type I blocks. Thus,
\begin{align}\label{TInDim3:Local2}
\Sym \overset{2^*}{\sim} 2^{j_1}{\tilde{\tau}}_1 \oplus 2^{j_2}{\tilde{\tau}}_2 \oplus 2^{j_3}{\tilde{\tau}}_3, ~~
{\tilde{\tau}}_1,{\tilde{\tau}}_2,{\tilde{\tau}}_3 \in \SGN^{\times}, i_1\leq i_2 \leq i_3
\end{align}
The value of $j_1$ can be read off the symbol $\Upsilon_2$ as
the smallest possible $2$-orders in $\Sym_2$. We set
$e_2=j_1$. We also pick an odd prime $\wp$ not in $\mathbb{P}_{\Sym}$
satisfying the following equation.
\begin{align}\label{TInDim3:wp}
\left(\prod_{p\in\{-1\}\cup (\mathbb{P}_{\Sym}\setminus\{2\})}
p^{e_p \bmod 2}\right)\wp \equiv {\tilde{\tau}}_1 \pmod 8
\end{align}
Such a prime can be found by rejection sampling. A random odd prime
satisfies the Equation \ref{TInDim3:wp} with probability
$1/4$. We set $e_{\wp}=1$. Also, for all primes $p$ that do not
divide $2\wp\det(\Sym)$, we set $e_p=0$.

\item Once the parity of all $p \in \{-1,2\}\cup \mathbb{P}$ is known
(see item (i)-(iv) of the construction), we define an integer $r$ as follows.
\begin{align}\label{TInDim3:r}
r = \prod_{p \in \mathbb{P}\cup \{-1,2\}} p^{e_p \bmod 2}
\end{align}

\item
Finally, we compute $e_p$ for all odd primes $p$ which divide
$\det(\Sym)$. Consider the diagonal form constructed in Equation
\ref{TInDim4:Local} for the prime $p$. Out of $(i_1,i_2), (i_2,i_3),$
and $(i_1,i_3)$;
let $(i_a,i_b), a < b \in \{1,2,3\}$ be the pair which has the same parity.
Then,
\begin{align}\label{TInDim3:ep}
e_p = \left\{
	\begin{array}{ll}
	i_a & \text{if } \legendre{\cop_p(r)}{p} = \legendre{\tau_a}{p},\\
	i_b & \text{otherwise}
	\end{array}
	\right.
\end{align}
\item We now have $e_p$ for every $p \in \{-1,2\} \cup \mathbb{P}$. We define
our integer $t$ as follows.
\begin{align}\label{TInDim3:t}
t = \prod_{p \in \{-1,2\}\cup \mathbb{P}} p^{e_p}
\end{align}
\end{enumerate}

The next step is to show that $t$ has a primitive representation in the genus
$\Sym$. Equivalently, it suffices to show that $t$ has a $p^*$-primitive
representation in $\Sym$ for all $p \in \{-1,2\} \cup \mathbb{P}$. Note that
if $\Upsilon_2$ has a Type II block then the construction of $t$ in this case
is the same as the construction of $t$ in the case of
Lemma \ref{lem:TInDim4}. The correctness of the construction also follows
from the same proof. In the rest, we assume that $\Upsilon_2$ has no Type II
block.
\begin{enumerate}[(i).]
\item ($p=-1$) By construction, $t$ is negative iff $\sig(\Sym)=-3$. In this
case $\Sym$ is a genus of negative definite matrices and hence must represent
every negative integer over $\mathbb{R}$. Otherwise, $t$ is a positive integer and
$\Sym$ is a genus of non-negative definite matrices i.e.,
$\Sym \overset{\mathbb{R}}{\sim} 1\oplus\cdots$. Hence, $\Sym$ must represent all positive integers
over $\mathbb{R}$. In either case, the constructed $t$ has a primitive representation
in $\Sym$ over $\mathbb{R}$.

\item ($p$ odd, $p$ does not divide $\wp\det(\Sym)$) In this case, $p$ does
not divide $t$. Hence, $t$ has a $p^*$-primitive representation in $\Sym$
(Lemma \ref{lem:Siegel12}).

\item ($p=2$) By assumption, there are only Type I blocks in $\Upsilon_2$.
By construction of $t$, $\tsym_{2^k}(2^{j_1}{\tilde{\tau}}_1) = \tsym_{2^k}(t)$. But then,
$t$ has a $2^*$-primitive representation in $2^{j_1}{\tilde{\tau}}_1$
(Lemma \ref{lem:Square}).

\item ($p$ odd, $p$ divides $\det(\Sym)$) By construction, $e_p$ has the
same parity as $i_a$ and $i_b$, see item (vi) of the construction of $t$
and Equation \ref{TInDim3:ep}. Thus, $\ord_p(t) \equiv \ord_p(r) \pmod 2$, or
\[
\legendre{\cop_p(t)}{p} = \legendre{\cop_p(r)}{p}
\]
By Equation \ref{TInDim3:ep}, $e_p=i_a$ if
$\legendre{\cop_p(t)}{p}=\legendre{\tau_a}{p}$ and $e_p=i_b$, otherwise.
If $\legendre{\cop_p(t)}{p}=\legendre{\tau_a}{p}$ then $t$ can be $p^*$-primitively
represented by the diagonal entry $p^{i_a}\tau_a$ (see Equation
\ref{TInDim3:Local}). Otherwise, $t$ can be $p^*$-primitively represented
by $p^{i_a}\tau_a \oplus p^{i_b}\tau_b$ (see Lemma \ref{lem:RepModPDim2}).
In either case, $t$ has a
$p^*$-primitive representation in $\Upsilon_p$.

\item ($p=\wp$) Finally, we show that $t$ has a $\wp^*$-primitive
representation in $\Sym$.
The prime $\wp$ does not divide $\det(\Sym)$ and hence by Lemma
\ref{lem:RelevantPrimes}, $\Sym \eqx{\wp^*}\det(\Sym)\oplus1\oplus1$.
Consider the following equation.
\begin{align}\label{TInDim3:wp2}
\det(\Sym) x_1^2 + x_2^2+x_3^2 \equiv t \pmod{\wp^2}\;.
\end{align}
By Lemma \ref{lem:QR}, $x_2^2+x_3^3$ represents
$t - \det(\Sym)$ over $\mathbb{Z}/\wp\mathbb{Z}$. Also,
$\det(\Sym) x_1^2$ represents $\det(\Sym)$
primitively over $\mathbb{Z}/\wp^2\mathbb{Z}$. Thus, Equation
\ref{TInDim3:wp2} has a primitive solution. By Theorem \ref{thm:Siegel13},
$t$ has a $\wp^*$-primitive representation in $\Sym$.
\end{enumerate}
\end{proof}

\subsection{Representation: $n=2$, basics}\label{dim2}

Finding an integer representation in dimension~2 is the most difficult.
As with dimension~3, we may need a prime $\wp$ but it needs to satisfy
more stringent conditions. In this case, we strongly use the fact that
the input symbol $\Sym$ is reduced and valid.

Recall the definition of a reduced genus. In dimension~2
a reduced genus $\Sym$ has the following form.
\begin{align}\label{def:red2}
\Sym \left\{\begin{array}{ll}
\overset{p^*}{\sim} a_p \oplus p^{i_p}b_p & \text{where }a_p, b_p \in (\zRz{p})^\times,
p \text{ odd},\\
\overset{2^*}{\sim} \mathtt{X}} \newcommand{\MY}{\mathtt{Y} \in \{a_2 \oplus 2^i b_2, \mathtt{T}^{+}, \mathtt{T}^{+}\} &
\text{where }a_2,b_2 \in \SGN^\times
\end{array}\right.
\end{align}

Note that $\Sym$ is a symbol in dimension~2 and hence
$\sig(\Sym) \in \{2,0,-2\}$. Define the quantities $\epsilon, \rho, $
and the function $\xi:\mathbb{Z}\to\{0,1\}$, as follows.
\begin{align}\label{def:dim2}
\begin{array}{lll}
\epsilon&=&\frac{\det(\Sym)}{|\det(\Sym)|} \\
\rho &=& \left\{\begin{array}{ll}
1 & \text{if }\sig(\Sym)\in\{0,2\}\\
-1 & \text{otherwise.}
\end{array}\right.\\
\xi(x) &=&\left\{\begin{array}{ll}
1 & \text{if }{x \choose 2}=\frac{x(x-1)}{2} \text{ is odd, and}\\
0 & \text{otherwise.}
\end{array}\right.
\end{array}
\end{align}

Then, the signature and the oddity of $\Sym$ can be computed
as follows.
\begin{align}\label{dim2:sigodty}
\begin{array}{lll}
\sig(\Sym) &=& \rho(1+\epsilon) \\
\odty(\Sym) &=& \left\{\begin{array}{ll}
0 & \text{if }\Upsilon_2 \overset{2^*}{\sim} \mathtt{T}^{+} \text{ or }\Upsilon_2 \overset{2^*}{\sim} \mathtt{T}^{-}\\
a_2 + b_2 \bmod 8 & \text{if }\legendre{b_2}{2}=1, \text{ or  $i_2$ even}\\
a_2+b_2+4 \bmod 8 & \text{otherwise}
\end{array}\right.
\end{array}
\end{align}

For convenience, we define the set $S$ as the set of
odd primes $p$ for which $i_p$ is odd i.e.,
$S=\{p \in \mathbb{P}_{\Sym} \cap \mathbb{P} \mid i_p \text{ odd}\}$.
Next, for each $d \in \{1,3,5,7\}$ and $b \in \{-,+\}$ we define
sets,
\begin{align}\label{def:Sdb}
S_{db} &= \Big\{p \in S \mid p \equiv d \bmod 8,
\legendre{a_p}{p} = b \Big\}
\end{align}

If we eliminate
a subscript, it means a union of the sets with all possible values
of the subscript. For example, $S_3=S_{3+}\cup S_{3-}$. The calligraphic
versions, as usual, will denote the size of the corresponding sets. For
example, $\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}-}$ is $|S_{3-}|+|S_{5-}|$.

\begin{lemma}\label{lem:dim2pexcess}
Let $\Sym^{n=2}$ be a valid reduced genus,
$\epsilon=\frac{\det(\Sym)}{|\det(\Sym)|}$, and $m$ be the total number of
antisquares in $\Sym$. Then,
\begin{align*}
\left(\sum_{p \in \mathbb{P}\cap\mathbb{P}_{\Sym}} \excess_p(\Sym)\right)
\equiv 2\mathcal{S}}\newcommand{\fT}{\mathcal{T}_3+4\mathcal{S}}\newcommand{\fT}{\mathcal{T}_5+6\mathcal{S}}\newcommand{\fT}{\mathcal{T}_7+2(1-(-1)^m) \pmod 8
\end{align*}
where,
\[
(-1)^m =
	\left\{\begin{array}{ll}
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\xi(\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}})}\epsilon^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
	& \text{if }\ord_2(\det(\Sym)) \text{ is even}\\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\xi(\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}})+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}}\epsilon^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
	& \text{otherwise.}\\
	\end{array}\right.
\]
\end{lemma}
\begin{proof}
Let $p$ be an odd prime from $\mathbb{P}_{\Sym}$. To compute the $p$-excess,
we need to compute the number of $p$-antisquares in $\Upsilon_p$.
By construction, $\Sym\overset{p^*}{\sim} a_p \oplus p^{i_p}b_p$ has a $p$-antisquare
iff $i_p$ is odd and $\legendre{b_p}{p}=-1$. But then,
$\det(\Sym) \overset{p^*}{\sim} \det(a_p\oplus p^{i_p}b_p)=a_pb_pp^{i_p}$ and so
$\legendre{b_p}{p}=\legendre{a_p\cop_p(\det(\Sym))}{p}$. If $m$ is the total
number of antisquares in $\Sym$ then,
\begin{align*}
(-1)^m &= \prod_{p \in S} \legendre{b_p}{p}
	= \prod_{p \in S} \legendre{a_p\cop_p(\det(\Sym))}{p}
	= \prod_{p \in S} \legendre{\cop_p(\det(\Sym))}{p}
	\prod_{p \in S} \legendre{a_p}{p} \\
	&= \left\{\begin{array}{ll}
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}\prod_{p \in S}\legendre{\epsilon}{p}
	\prod_{p_i \neq p_j \in S} \legendre{p_i}{p_j}\legendre{p_j}{p_i}
	& \text{if }\ord_2(\det(\Sym)) \text{ is even}\\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}\prod_{p \in S}\legendre{2\epsilon}{p}
	\prod_{p_i \neq p_j \in S} \legendre{p_i}{p_j}\legendre{p_j}{p_i}
	& \text{otherwise.}
	\end{array}\right.
\end{align*}
Note that $\legendre{-1}{p}=-1$ iff $p \equiv 3 \bmod 4$ i.e.,
$\prod_{p \in S}\legendre{\epsilon}{p}=\epsilon^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}$. Also,
$\legendre{2}{p}=-1$ iff $p\bmod 8 \in \{3,5\}$ i.e.,
$\prod_{p\in S}\legendre{2}{p}=(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}}$. By Quadratic
Reciprocity,
$\prod_{p_i \neq p_j} \legendre{p_i}{p_j}\legendre{p_j}{p_i}
=(-1)^{\xi(\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}})}$. Putting it together, we have,
\[
(-1)^m =
	\left\{\begin{array}{ll}
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\xi(\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}})}\epsilon^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
	& \text{if }\ord_2(\det(\Sym)) \text{ is even}\\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\xi(\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}})+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}}\epsilon^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
	& \text{otherwise.}\\
	\end{array}\right.
\]

By definition, if $m$ is the total number of $p$-antisquares in $\Sym$
with $p$ odd then,
\begin{align*}
\sum_{p\in \mathbb{P}\cap\mathbb{P}_{\Sym}} \excess_p(\Sym) &= \sum_{p \in S} \excess_p(\Sym)
= 4m+\sum_{p \in S} (p-1)  \bmod 8 \\
&= 2\mathcal{S}}\newcommand{\fT}{\mathcal{T}_3 + 4\mathcal{S}}\newcommand{\fT}{\mathcal{T}_5 + 6\mathcal{S}}\newcommand{\fT}{\mathcal{T}_7 + 4m \pmod 8
\end{align*}

The expression $4m \bmod 8$ evaluates to~4 iff $m$ is odd. Equivalently,
$4m \bmod 8$ evaluates to~4 iff $(-1)^m$ evaluates to
$-1$; completing the proof.
\end{proof}

\begin{lemma}\label{lem:RepresentWP}
Let $\Sym^{n=2}$ be a reduced genus,
$r$ be an integer and $\wp$ be an
odd prime that does not divide $r\det(\Sym)$. Then, $r\wp$ has a
$\wp^*$-primitive representation in $\Sym$ iff
$\legendre{-\det(\Sym)}{\wp}=1$. If $\ord_2(\det(\Sym))$ is even, then
\[
\legendre{-\det(\Sym)}{\wp} = \left\{\begin{array}{ll}
\underset{p\in S}{\prod} \legendre{\wp}{p} & \text{if }\wp\equiv1\bmod4\\
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}+1}\epsilon\underset{p\in S}{\prod} \legendre{\wp}{p} & \text{otherwise.}
\end{array}\right.
\]
and if $\ord_2(\det(\Sym))$ is odd then,
\[
\legendre{-\det(\Sym)}{\wp} = \left\{\begin{array}{ll}
\underset{p\in \{2\} \cup S}{\prod} \legendre{\wp}{p}
& \text{if }\wp\equiv1\bmod4\\
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}+1}\epsilon
\underset{p\in \{2\}\cup S}{\prod} \legendre{\wp}{p} & \text{otherwise.}
\end{array}\right.
\]
\end{lemma}
\begin{proof}
By Lemma \ref{lem:RelevantPrimes},
$\Sym \overset{\wp*}{\sim} \diag(\det(\Sym), 1)$.  By Theorem
\ref{thm:Siegel13}, $r\wp$ has a $\wp^*$-primitive representation
in $\Sym$ iff the following equation has a primitive solution;
\[
\wp r \equiv \det(\Sym) x^2 + y^2 \pmod{\wp^2}\;.
\]
Both $x$ and $y$ must be units of $\mathbb{Z}/\wp\mathbb{Z}$. But then,
\[
\legendre{-\det(\Sym)}{\wp}=\legendre{\wp r - \det(\Sym) x^2}{\wp}
=\legendre{y^2}{\wp}=1.
\]

Convsersely, if $\legendre{-\det(\Sym)}{\wp}=1$ then, by Lemma
\ref{lem:Square}, the following equation
has a solution.
\[
x^2 \equiv -\det(\Sym) + \wp r \pmod{\wp^2}
\]
Thus, $x^2+\det(\Sym) \equiv \wp r \pmod{\wp^2}$ or $\wp r$ has a
$\wp^*$-primitive representation in $1\oplus \det(\Sym)$.

Next, we write $\legendre{-\det(\Sym)}{\wp}$ in terms of $\epsilon, \rho, $
and $\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{db}$ using the Law of Quadratic Reciprocity (Equation
\ref{QuadraticReciprocity}). If $\ord_2(\det(\Sym))$ is even then,
\begin{align*}
\legendre{-\det(\Sym)}{\wp}
	&=\legendre{-\epsilon}{\wp}\prod_{p \in S} \legendre{p}{\wp} \\
	&=\legendre{-\epsilon}{\wp} \prod_{p \in S_{\{1,5\}}} \legendre{\wp}{p}
	\prod_{p \in S_{\{3,7\}}} \legendre{p}{\wp}\\
	&= \left\{\begin{array}{ll}
	\underset{p \in S}{\prod} \legendre{\wp}{p}
	& \text{$\wp \equiv 1 \bmod 4$,} \\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\legendre{-\epsilon}{\wp}
	\underset{p \in S}{\prod}\legendre{\wp}{p}
	& \text{otherwise.}\\
	\end{array}\right.
\end{align*}
On the other hand, if $\ord_2(\det(\Sym))$ is odd then
\begin{align*}
\legendre{-\det(\Sym)}{\wp}
	&=\legendre{-2\epsilon}{\wp}\prod_{p \in S} \legendre{p}{\wp} \\
	&= \left\{\begin{array}{ll}
	\legendre{\wp}{2}\underset{p \in S}{\prod} \legendre{\wp}{p}
	& \text{$\wp \equiv 1 \bmod 4$,} \\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\legendre{\wp}{2}\legendre{-\epsilon}{\wp}
	\underset{p \in S}{\prod}\legendre{\wp}{p}
	& \text{otherwise.}\\
	\end{array}\right.
\end{align*}
\end{proof}

\subsection{Representation: $n=2$, Type II}

In this section, we construct an integer $t$ such that $t$ has
a primitive representation in $\Sym$, where $\Upsilon_2 \overset{2^*}{\sim} \mathtt{T}^{+}$ or
$\Upsilon_2 \overset{2^*}{\sim} \mathtt{T}^{-}$. Note that, in this situation,~2 does not divide
$\det(\Sym)$.

\begin{lemma}\label{TypeIIdim2:FindT}
Let $\Sym^{n=2}$ be a valid reduced genus with $\Upsilon_2 \overset{2^*}{\sim} \mathtt{T}^{-}$ or
$\Upsilon_2 \overset{2^*}{\sim} \mathtt{T}^{+}$. Then, there exists an integer of the form
$2\wp r^2$ with primitive representation
in $\Sym$, where $\wp$ is an odd prime that does not divide $\det(\Sym)$
and $r^2$ is an integer that divides $\det(\Sym)$.
\end{lemma}
\begin{proof}
Recall the definition of $\epsilon, \rho \in \{-1,1\}$ as in Equation
\ref{def:dim2}. Let us define the following set of congruences.
\begin{align}\label{TypeIIdim2:wp}
\begin{array}{ll}
\wp & \equiv 2\rho a_p  \pmod p ~\text{ for all} ~ p \in S\\
\wp &\equiv \left\{\begin{array}{ll}
1 \pmod 4 & \text{if }\rho=+, \mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even, or} \\
& \text{if }\rho=-, \mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even.} \\
3\pmod 4 &\text{if }\rho=+,\epsilon=+,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}\text{ odd, or} \\
& \text{if }\rho=+,\epsilon=-,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even, or}\\
& \text{if }\rho=-,\epsilon=-,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even, or}\\
& \text{if }\rho=-,\epsilon=+,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ odd.}
\end{array}\right.
\end{array}
\end{align}

Note that the set of possibilities under which we can write a
modulo~4 congruence is not exhaustive. It is, as we show later,
exhaustive for every valid symbol $\Sym$.

It is possible to solve the congruence in such a way that
$\wp$ is a prime (Dirichlet's Theorem).
Consider an integer $r$ defined as follows.
\begin{align}\label{TypeIIdim2:r}
r = \prod_{p \in \mathbb{P}_{\Sym}} p^{e_p/2} \qquad
e_p = \left\{\begin{array}{ll}
0 & \text{if }p \in \{2\}\cup S \\
0 & \text{if }p \in \mathbb{P}_{\Sym} \setminus (\{2\}\cup S),
\legendre{a_p}{p}=\legendre{2\rho\wp}{p} \\
i_p & \text{if }p \in \mathbb{P}_{\Sym} \setminus (\{2\}\cup S),
\legendre{a_p}{p}\neq \legendre{2\rho\wp}{p}
\end{array}\right.
\end{align}

Note that, if $p$ is an odd prime not in $S$ then $i_p$ is even. Thus,
$r$ is an integer. Define $t=2\rho \wp r^2$. We next show that $t$
has a primitive representation in the genus $\Sym$.
For this, it
suffices to show that $t$ has a primitive $p^*$-representation in $\Sym$
for all $p \in \{p \mid \ord_p(2t\det(\Sym))>0\}\cup\{-1\}$
(see Lemma \ref{lem:Siegel12}).
\begin{enumerate}[(i).]
\item ($p=-1$) By Equation \ref{def:dim2}, $\rho=-1$ iff
$\sig(\Sym)=-2$. In this case, $\Sym$ is negative definite and
represents all negative integers. Otherwise, $\Sym \overset{\mathbb{R}}{\sim} 1\oplus x$ and
$\rho=1$. But then, $t$ is a positive integer and hence can be
represented by $\Sym$ over $\mathbb{R}$. In either case, $t$ has a
representation in $\Sym$ over $\mathbb{R}$.

\item ($p=2$) By construction,~2 does not divide $\wp r^2$ and so
$\ord_p(t)=1$. By assumption, $\Upsilon_2 \overset{2^*}{\sim} \mathtt{T}^{+}$ or $\Upsilon_2 \overset{2^*}{\sim} \mathtt{T}^{-}$.
In either case, by Lemma \ref{lem:RepresentTTypeII} and
Theorem \ref{thm:Siegel13}, $t$ has a
$2^*$-primitive representation in $\Upsilon_2$.

\item ($p \in S$) By definition of $r$, $\ord_p(r)=0$ for all primes
$p \in S$. By construction in Equation \ref{TypeIIdim2:wp},
$\legendre{t}{p}=\legendre{2\rho\wp}{p}=\legendre{a_p}{p}$, where
$\Sym \overset{p^*}{\sim} a_p \oplus p^{i_p}b_p$. But then, by Lemma
\ref{lem:Square}, $a_p$ (and hence, $\Sym$)
represents $t$, $p^*$-primitively.

\item ($p$ odd, $p\in \mathbb{P}_{\Sym} \setminus S$) If $\Sym \overset{p^*}{\sim}
a_p \oplus p^{i_p}b_p$ then, $i_p$ is even. If
$\legendre{a_p}{p}=\legendre{2\rho\wp}{p}$ then, $p$ does
not divide $2\rho\wp r^2$ and $\legendre{a_p}{p}=\legendre{t}{p}$.
Thus, $t$ has a $p^*$-primitive representation in $\Sym$ (Lemma
\ref{lem:Square} and Theorem \ref{thm:Siegel13}).
Otherwise, $\legendre{a_p}{p} \neq \legendre{2\rho\wp}{p}$. But then,
$\ord_p(t)=\ord_p(r^2)=i_p$, and
by Lemma \ref{lem:RepModPDim2} and Theorem \ref{thm:Siegel13}, $t$
has a $p^*$-primitive representation in $a_p \oplus p^{i_p}b_p$.

\item ($p=\wp$) Finally, it remains to show that $t$ has a
$\wp^*$-primitive representation in $\Sym$. By Lemma
\ref{lem:RepresentWP}, one needs to show that
$\legendre{-\det(\Sym)}{\wp}=1$. Recall the Quadratic Reciprocity
Laws in Equation \ref{QuadraticReciprocity}. Also, note that
$\legendre{-1}{p}=1$ iff $p \equiv 1 \bmod 4$. The computation
of $\legendre{-\det(\Sym)}{\wp}$ can be done using Lemma
\ref{lem:RepresentWP}, as follows.
\begin{align*}
\prod_{p\in S}\legendre{\wp}{p} &= \prod_{p \in S} \legendre{2\rho a_p}{p}
	= (-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\prod_{p \in S} \legendre{2}{p} \\
	&=(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\prod_{p \in S} \legendre{p}{2}
	= (-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\\
\legendre{-\det(\Sym)}{\wp}
	&= \left\{\begin{array}{ll}
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
	& \text{$\wp \equiv 1 \bmod 4$,} \\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+1}\epsilon\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
	& \text{otherwise.}\\
	\end{array}\right. \\
	&= \left\{\begin{array}{ll}
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}}
	& \rho=+, \wp \equiv 1 \bmod 4 \\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}}
	& \rho=-, \wp \equiv 1 \bmod 4\\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}+1} & \rho=+, \epsilon=+, \wp\equiv 3\bmod 4\\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}} & \rho=+, \epsilon=-, \wp\equiv 3\bmod 4\\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}} & \rho=-, \epsilon=-, \wp\equiv 3\bmod 4\\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}+1} & \rho=-, \epsilon=+, \wp\equiv 3\bmod 4\\
	\end{array}\right. \\
\end{align*}
It turns out that $\wp \bmod 4$ was defined to satisfy exactly
this equation (see Equation \ref{TypeIIdim2:wp}).
\end{enumerate}

This completes the proof of the claim that $t$ has a primitive
representation in the genus $\Sym$.

Finally, we show that the set of possibilities under the modulo~4
congruence in Equation \ref{TypeIIdim2:wp} is exhaustive, if the
input symbol $\Sym$ is valid.
The proof of this statement is computer assisted and the code
can be found in Appendix \ref{sec:Code}.

We design the test program as follows. For all possible choices of
$\epsilon, \rho \in \{1,-1\}$, and $\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{db} \in \{0,1,2,3\}$, we
compute $\sig(\Sym), \odty(\Sym)$ by Equation \ref{dim2:sigodty}.
We also compute $\sum_{p \in \mathbb{P}}\excess_p(\Sym)$ by Lemma
\ref{lem:dim2pexcess}. Then, we check the oddity condition i.e,
\[
\sig(\Sym)+\sum_{p \in \mathbb{P}}\excess_p(\Sym)\equiv\odty(\Sym) \pmod 8
\]
If the oddity condition is satisfied then we check if at least one
of these conditions hold.
\begin{align}\label{TypeIIdim2:good}
\begin{array}{ll}
(\rho=+, \mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even}) &
(\rho=-, \mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even}) \\
(\rho=+,\epsilon=+,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}\text{ odd}) &
(\rho=+,\epsilon=-,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even})\\
(\rho=-,\epsilon=-,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even}) &
(\rho=-,\epsilon=+,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ odd})
\end{array}
\end{align}
In each of these cases, a $\wp$ and hence $t$ exists by Equation
\ref{TypeIIdim2:wp}. The test program never finds itself in
a situation when none of the conditions in Equation \ref{TypeIIdim2:good}
are true. This completes the proof of existence of a primitively
representable $t$.

\end{proof}

\subsection{Representation: $n=2$, Type I, Even}

This section deals with the case when $\Upsilon_2 \overset{2^*}{\sim} a_2 \oplus 2^{i_2} b_2$,
where $i_2$ is even, and $a_2, b_2 \in \{1,3,5,7\}$.

\begin{lemma}\label{lem:TypeIEven}
Let $\Sym^{n=2}$ be valid reduced genus with
$\Upsilon_2\overset{2^*}{\sim} a_2\oplus 2^{i_2}b_2$, where $i_2$ is even and
$a_2, b_2 \in \SGN^\times$. Then,
there exists an integer of the form $\wp r^2$ with primitive representation
in $\Sym$, where $\wp$ is an odd prime that does not divide $\det(\Sym)$
and $r^2$ is an integer that divides $\det(\Sym)$.
\end{lemma}
\begin{proof}
Recall the definition of $\epsilon, \rho \in \{-1,1\}$ as in Equation
\ref{def:dim2}. Let us define the following set of congruences.
\begin{align}\label{TypeIEven:wp}
\begin{array}{ll}
\wp &\equiv \rho a_p \pmod{p} ~~ \text{for all }p \in S\\
\wp &\equiv \left\{\begin{array}{ll}
x \pmod 8 & \text{if }\rho=+, \mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even and }
x \in X \cap \{1,5\}\text{ or} \\
& \text{if }\rho=-, \mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even and }
x \in X \cap \{1,5\}\text{ or} \\
y\pmod 8 &\text{if }\rho=+,\epsilon=+,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}\text{ odd and }
y \in X \cap \{3,7\}\text{ or}\\
& \text{if }\rho=+,\epsilon=-,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even and }
y \in X \cap \{3,7\}\text{ or}\\
& \text{if }\rho=-,\epsilon=-,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even and }
y \in X \cap \{3,7\}\text{ or}\\
& \text{if }\rho=-,\epsilon=+,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ odd and }
y \in X \cap \{3,7\}
\end{array}\right.\\
&\text{where, }X = \{\rho a_2 \bmod 8, \rho b_2 \bmod 8\}
\end{array}
\end{align}
A few word on notation. The modulo~8 congruences should be read as
follows. Consider the first congruence ``$\rho \equiv x \bmod 8$,
if $\rho=+, \mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}$ even and $x \in X\cap\{1,5\}$''. If $X\cap\{1,5\}$
is empty then this statement is false. Otherwise, we pick any
element $x$ from the intersection. Also, $x \equiv 1 \bmod 4$
and $y \equiv 3 \bmod 4$.

Note that the set of possibilities under which we can write a
modulo~8 congruence is not exhaustive. It is, as we show later,
exhaustive for every valid symbol $\Sym$.

It is possible to solve the congruence in such a way that
$\wp$ is a prime (Dirichlet's Theorem).
Consider an integer $r$ defined as follows.
\begin{align}\label{TypeIEven:r}
r = \prod_{p \in \mathbb{P}_{\Sym}} p^{e_p/2} \qquad
e_p = \left\{\begin{array}{ll}
0 & \text{if }(p \in S) \text{ or }(p=2, \wp \equiv a_2 \bmod 8)\\
i_2 & \text{if }p=2, \wp \equiv b_2 \bmod 8\\
0 & \text{if }p \in \mathbb{P}_{\Sym} \setminus (\{2\}\cup S),
\legendre{a_p}{p}=\legendre{\rho\wp}{p} \\
i_p & \text{if }p \in \mathbb{P}_{\Sym} \setminus (\{2\}\cup S),
\legendre{a_p}{p}\neq \legendre{\rho\wp}{p}
\end{array}\right.
\end{align}
The exponent $e_p$ is always even and hence $r$ is an integer.
Define $t=\rho \wp r^2$. We next show that $t$
has a primitive representation in the genus $\Sym$. For this, it
suffices to show that $t$ has a primitive $p^*$-representation in $\Sym$
for all $p \in \{p \mid \ord_p(2t\det(\Sym))>0\}\cup\{-1\}$
(see Lemma \ref{lem:Siegel12}).

\begin{enumerate}[(i).]
\item ($p=-1$) By Equation \ref{def:dim2}, $\rho=-1$ iff
$\sig(\Sym)=-2$. In this case, $\Sym$ is negative definite and
represents all negative integers. Otherwise, $\Sym \overset{\mathbb{R}}{\sim} 1\oplus x$ and
$\rho=1$. But then, $t$ is a positive integer and hence can be
represented by $\Sym$ over $\mathbb{R}$. In either case, $t$ has a
representation in $\Sym$ over $\mathbb{R}$.

\item ($p \in S$) By definition of $r$, $\ord_p(r)=0$ for all primes
$p \in S$. By construction in Equation \ref{TypeIEven:wp},
$\legendre{t}{p}=\legendre{\rho\wp}{p}=\legendre{a_p}{p}$, where
$\Sym \overset{p^*}{\sim} a_p \oplus p^{i_p}b_p$. But then, by Lemma
\ref{lem:Square}, $a_p$ (and hence, $\Sym$)
represents $t$, $p^*$-primitively.

\item ($p$ odd, $p\in \mathbb{P}_{\Sym} \setminus S$) If $\Sym \overset{p^*}{\sim}
a_p \oplus p^{i_p}b_p$ then, $i_p$ is even. If
$\legendre{a_p}{p}=\legendre{\rho\wp}{p}$ then, $p$ does
not divide $\rho\wp r^2$ and $\legendre{a_p}{p}=\legendre{t}{p}$.
Thus, $t$ has a $p^*$-primitive representation in $\Sym$ (Lemma
\ref{lem:Square} and Theorem \ref{thm:Siegel13}).
Otherwise, $\legendre{a_p}{p} \neq \legendre{\rho\wp}{p}$. But then,
$\ord_p(t)=\ord_p(r^2)=i_p$, and
by Lemma \ref{lem:RepModPDim2} and Theorem \ref{thm:Siegel13}, $t$
has a $p^*$-primitive representation in $a_p \oplus p^{i_p}b_p$.

\item ($p=\wp$) Next, we show that $t$ has a
$\wp^*$-primitive representation in $\Sym$. By Lemma
\ref{lem:RepresentWP}, one needs to show that
$\legendre{-\det(\Sym)}{\wp}=1$. Recall the Quadratic Reciprocity
Laws in Equation \ref{QuadraticReciprocity}. Also, note that
$\legendre{-1}{p}=1$ iff $p \equiv 1 \bmod 4$. The computation
of $\legendre{-\det(\Sym)}{\wp}$ can be done using Lemma
\ref{lem:RepresentWP}, as follows.
\begin{align*}
\prod_{p\in S}\legendre{\wp}{p} &= \prod_{p \in S} \legendre{\rho a_p}{p}
	= (-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\\
\legendre{-\det(\Sym)}{\wp}
	&= \left\{\begin{array}{ll}
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
	& \text{$\wp \equiv 1 \bmod 4$,} \\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+1}\epsilon\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
	& \text{otherwise.}\\
	\end{array}\right. \\
	&= \left\{\begin{array}{ll}
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}
	& \rho=+, \wp \equiv 1 \bmod 4 \\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
	& \rho=-, \wp \equiv 1 \bmod 4\\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}+1} & \rho=+, \epsilon=+, \wp\equiv 3\bmod 4\\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}} & \rho=+, \epsilon=-, \wp\equiv 3\bmod 4\\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}} & \rho=-, \epsilon=-, \wp\equiv 3\bmod 4\\
	(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+1} & \rho=-, \epsilon=+, \wp\equiv 3\bmod 4\\
	\end{array}\right. \\
\end{align*}
It turns out that $\wp \bmod 4$ was defined to satisfy exactly
this equation (see Equation \ref{TypeIIdim2:wp}).

\item ($p=2$) In this case, $\Upsilon_2 \overset{2^*}{\sim} a_2\oplus2^{i_2}b_2$, where
$a_2, b_2 \in \{1,3,5,7\}$.
From Equation \ref{TypeIEven:wp}, either $a_2 \overset{2^*}{\sim} t$ or
$2^{i_2}b_2\overset{2^*}{\sim} t$. In either case, $t$ has a $2^*$-primitive
representation in $\Sym$.
\end{enumerate}

This completes the proof of the claim that $t$ has a primitive
representation in the genus $\Sym$.

Finally, we show that the set of possibilities under the modulo~8
congruence in Equation \ref{TypeIEven:wp} is exhaustive, if the
input symbol $\Sym$ is valid.
The proof of this statement is computer assisted and the code
can be found in Appendix \ref{sec:Code}.

We design the test program as follows. For all possible choices of
$\epsilon, \rho \in \{1,-1\}$, $a_2,b_2 \in \{1,3,5,7\}$
and $\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{db} \in \{0,1,2,3\}$, we
compute $\sig(\Sym), \odty(\Sym)$ by Equation \ref{dim2:sigodty}.
We also compute $\sum_{p \in \mathbb{P}}\excess_p(\Sym)$ by Lemma
\ref{lem:dim2pexcess}. Then, we check the oddity condition i.e,
\[
\sig(\Sym)+\sum_{p \in \mathbb{P}}\excess_p(\Sym)\equiv\odty(\Sym) \pmod 8
\]
We next check the following determinant condition for $\Upsilon_2$.
\[
\legendre{a_2b_2}{2} = (-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}}
\]
If either of these conditions is not satisfied then the symbol $\Sym$
is not valid. For the others, we check if at least one of these
condition holds.
\begin{align}\label{TypeIEven:good}
\begin{array}{l}
(\rho=+, \mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}\text{ even}, |X\cap\{1,5\}|>0) \\
(\rho=-, \mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}\text{ even}, |X\cap\{1,5\}|>0) \\
(\rho=+,\epsilon=+,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}\text{ odd}, |X\cap\{3,7\}|>0) \\
(\rho=+,\epsilon=-,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even}, |X\cap\{3,7\}|>0)\\
(\rho=-,\epsilon=-,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ even}, |X\cap\{3,7\}|>0) \\
(\rho=-,\epsilon=+,\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-} \text{ odd}, |X\cap\{3,7\}|>0)
\end{array}
\end{align}
In each of these cases, a $\wp$ and hence $t$ exists by Equation
\ref{TypeIEven:wp}. The test program never finds itself in
a situation when none of the conditions in Equation \ref{TypeIEven:good}
are true. This completes the proof of existence of a primitively
representable $t$.

\end{proof}

\subsection{Representation: $n=2$, Type I, Odd}

This section deals with the case when $\Upsilon_2 \overset{2^*}{\sim} a_2 \oplus 2^{i_2} b_2$,
where $i_2$ is odd and $a_2,b_2 \in \{1,3,5,7\}$.

\begin{lemma}\label{lem:TypeIOdd}
Let $\Sym^{n=2}$ be a valid reduced genus with $\Upsilon_2 \overset{2^*}{\sim}
a_2\oplus 2^{i_2}b_2$, where $i_2$ is odd and $a_2,b_2 \in \SGN^\times$.
Then, there exists an integer of the form $\wp r^2$ or $2^{i_2}\wp r^2$ with
primitive representation in $\Sym$, where $\wp$ is an odd prime that
does not divide $\det(\Sym)$ and $r^2$ is an integer that divides
$\det(\Sym)$.
\end{lemma}
\begin{proof}
By assumption $i_2$ is odd and hence an odd power of~2 divides
$\det(\Sym)$.

Consider the following set of congruences, along with the construction
of the candidate primitively representable integer $t$.
\begin{align}\label{TypeIOdd:wp}
\begin{array}{l}
\textbf{if } \Big(\rho a_2 \equiv 1 \bmod 4 \textbf{ and }
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\legendre{a_2}{2}=1\Big) \textbf{ or } \\
\Big(\rho a_2 \equiv 3 \bmod 4 \textbf{ and }
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}+1}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
\epsilon\legendre{a_2}{2}=1\Big) \textbf{ then}\\
\begin{array}{ll}
~~\wp &\equiv \rho a_p \bmod p  ~~\text{ for all }p\in S\\
~~\wp &\equiv \rho a_2 \bmod 8 \\
~~e_p &= \left\{\begin{array}{ll}
0 & \text{if }p \in \{2\}\cup S \\
0 & \text{if }p \in \mathbb{P}_{\Sym} \setminus (\{2\}\cup S),
\legendre{a_p}{p}=\legendre{\rho\wp}{p} \\
i_p & \text{if }p \in \mathbb{P}_{\Sym} \setminus (\{2\}\cup S),
\legendre{a_p}{p}\neq \legendre{\rho\wp}{p}
\end{array}\right.\\
~~t &= \rho \wp \left(\underset{p \in \mathbb{P}_{\Sym}}{\prod} p^{e_p}\right)
\end{array}\\
\textbf{elif } \Big(\rho b_2 \equiv 1 \bmod 4 \textbf{ and }
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\legendre{b_2}{2}=1\Big)
\textbf{ or}\\
\Big(\rho b_2 \equiv 3 \bmod 4 \textbf{ and }
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}+1}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
\epsilon\legendre{b_2}{2}=1\Big) \textbf{ then}\\
\begin{array}{lll}
~~\wp &\equiv & 2\rho a_p \bmod p ~~ \text{ for all }p\in S\\
~~\wp &\equiv& \rho b_2 \bmod 8 \\
~~e_p &=& \left\{\begin{array}{ll}
0 & \text{if }p \in S \\
0 & \text{if }p \in \mathbb{P}_{\Sym} \setminus (\{2\}\cup S),
\legendre{a_p}{p}=\legendre{2\rho\wp}{p} \\
i_p & \text{if }p \in \mathbb{P}_{\Sym} \setminus (\{2\}\cup S),
\legendre{a_p}{p}\neq \legendre{2\rho\wp}{p}
\end{array}\right.\\
~~t &=& \rho 2^{i_2}\wp \left(\underset{p\in\mathbb{P}_{\Sym}\cap\mathbb{P}}{\prod}p^{e_p}\right)
\end{array}
\end{array}
\end{align}

Note that the set of possibilities under which we can write
the congruence for $\wp$ is not exhaustive. It is, as we show later,
exhaustive for every valid symbol $\Sym$.

We show that $t$ has a primitive representation in
$\Sym$, or equivalently, $t$ has a $p^*$-primitive representation
in $\Sym$ for all $p \in \{-1,2\}\cup \mathbb{P}$.
For this, it
suffices to show that $t$ has a primitive $p^*$-representation in $\Sym$
for all $p \in \{p \mid \ord_p(2t\det(\Sym))>0\}\cup\{-1\}$
(see Lemma \ref{lem:Siegel12}).
\begin{enumerate}[(i).]
\item ($p=-1$) The value of $\rho=-1$ iff $\sig(\Sym)=-2$. Thus,
$t$ has a representation over $\mathbb{R}$ in $\Sym$.

\item (odd $p \in \mathbb{P}_{\Sym} \setminus S$) In this case,
$\Upsilon_p \overset{p^*}{\sim} a_p \oplus p^{i_p}b_p$ and $\ord_p(t)=i_p$, where
$i_p$ is even. By Lemma \ref{lem:RepModPDim2},
$t$ has a primitive representation in $a_p \oplus p^{i_p} b_p$.

\item ($p=2$) By construction, either $t \overset{2^*}{\sim} a_2$ or $t\overset{2^*}{\sim} 2^{i_2}b_2$.
In either case, $t$ has a primitive $2^*$-representation in $\Sym$
(Lemma \ref{lem:Square}).

\item ($p=\wp$) In this case, we need to show that
$\legendre{-\det(\Sym)}{\wp}=1$. We split the proof into
two sub-cases.
\begin{enumerate}[(a).]
\item ($\wp \equiv \rho a_2 \bmod 8$)
We first compute the value of
$\prod_{p \in \{2\}\cup S} \legendre{\wp}{p}$.
\begin{align*}
\prod_{p \in \{2\}\cup S} \legendre{\wp}{p}
&= \prod_{p\in\{2\}\cup S}\legendre{\rho a_p}{p}
=(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\legendre{a_2}{2}
\end{align*}
And then, we insert it into the computation
of $\legendre{-\det(\Sym)}{\wp}$ in Lemma \ref{lem:RepresentWP}.
\begin{align*}
\legendre{-\det(\Sym)}{\wp} &= \left\{\begin{array}{ll}
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\legendre{a_2}{2}
& \text{if }\wp\equiv 1 \bmod 4\\
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}+1}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\epsilon\legendre{a_2}{2}
& \text{otherwise}
\end{array}\right.
\end{align*}

\item ($\wp \equiv \rho b_2 \bmod 8$) Similarly, we compute,
\begin{align*}
\prod_{p \in \{2\}\cup S} \legendre{\wp}{p}
&= \legendre{\rho b_2}{2}\prod_{p \in S}\legendre{2\rho a_p}{p}
=(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\legendre{b_2}{2}
\end{align*}
And then, we insert it into the computation
of $\legendre{-\det(\Sym)}{\wp}$ in Lemma \ref{lem:RepresentWP}.
\begin{align*}
\legendre{-\det(\Sym)}{\wp} &= \left\{\begin{array}{ll}
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\legendre{b_2}{2}
& \text{if }\wp\equiv 1 \bmod 4\\
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}+1}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\epsilon\legendre{b_2}{2}
& \text{otherwise}
\end{array}\right.
\end{align*}
\end{enumerate}
In either case, $\legendre{-\det(\Sym)}{\wp}=1$, proving the
primitive $\wp^*$-representativeness.
\end{enumerate}

This completes the proof of the claim that $t$ has a primitive
representation in the genus $\Sym$.

Finally, we show that the set of possibilities when we can write
a congruence (see Equation \ref{TypeIOdd:wp}) is exhaustive, if the
input symbol $\Sym$ is valid.
The proof of this statement is computer assisted and the code
can be found in Appendix \ref{sec:Code}.

We design the test program as follows. For all possible choices of
$\epsilon, \rho \in \{1,-1\}$, $a_2,b_2 \in \{1,3,5,7\}$
and $\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{db} \in \{0,1,2,3\}$, we
compute $\sig(\Sym), \odty(\Sym)$ by Equation \ref{dim2:sigodty}.
We also compute $\sum_{p \in \mathbb{P}}\excess_p(\Sym)$ by Lemma
\ref{lem:dim2pexcess}. Then, we check the oddity condition i.e,
\[
\sig(\Sym)+\sum_{p \in \mathbb{P}}\excess_p(\Sym)\equiv\odty(\Sym) \pmod 8
\]
We next check the following determinant condition for $\Upsilon_2$.
\[
\legendre{a_2b_2}{2} = (-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}}
\]
If either of these conditions is not satisfied then the symbol $\Sym$
is not valid. For the others, we check if at least one of these
condition holds.
\begin{align}\label{TypeIOdd:good}
\begin{array}{l}
(\rho a_2 \equiv 1 \bmod 4,
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\legendre{a_2}{2}=1)\\
(\rho a_2 \equiv 3 \bmod 4,
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}+1}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
\epsilon\legendre{a_2}{2}=1)\\
(\rho b_2 \equiv 1 \bmod 4,
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,5\}}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}\legendre{b_2}{2}=1)\\
(\rho b_2 \equiv 3 \bmod 4,
(-1)^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{-}+\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{5,7\}}+1}\rho^{\mathcal{S}}\newcommand{\fT}{\mathcal{T}_{\{3,7\}}}
\epsilon\legendre{b_2}{2}=1)
\end{array}
\end{align}
In each of these cases, a $\wp$ and hence $t$ exists as in Figure~5.1.
The test program never finds itself in
a situation when none of the conditions in Equation \ref{TypeIOdd:good}
are true. This completes the proof of existence of a primitively
representable $t$.

\end{proof}

\subsection{Representation: putting it together}\label{dim2end}

\begin{proof}(Theorem \ref{thm:FindT})
The construction follows from the constructive nature of
Lemma \ref{lem:TInDim4}, Lemma \ref{lem:TInDim3} and the constructions
for the case of dimension~2. The only remaining task in case of
dimension $2$, is to find a $\wp$ which satisfies the
given set of congruence relations.

Assuming ERH, one can find $\sigma_p$ i.e., the smallest non-residue
modulo $p$ in $O(\log^3 p)$ ring operations over $\zRz{p}$.
If done for every prime that divides
$\det(\Sym)$, this takes $O(|\mathbb{P}_{\Sym}|\log ^3 \det(\Sym))$ ring
operations over $\mathbb{Z}/\det(\Sym)\mathbb{Z}$.

Let $p_1,\cdots,p_s$ be the primes which appear with odd parity in the
symbol and $\alpha=8p_1\cdots p_s$. Then, we form the required set of
congruent equations i.e.,
\[
x \equiv \left\{
	\begin{array}{ll}
	x_{p_i} \bmod{p_i} & \text{if $\epsilon_i=-1$,
	where $x_{p_i} \in (\zRz{p})^\times$} \\
	\tau \bmod8 & \text{where $\tau \in \{1,3,5,7\}$}
	\end{array}\right.
\]
Solve this set of
congruence using the Chinese Remainder and let $a$ be a solution.
Pick a $b$ uniformly
at random from the range $[0,\alpha^2]$. If
$S=\{a+z\alpha \mid z \in \mathbb{Z}, z \leq \alpha^2\}$, then $a+b\alpha$ is
a uniformly random element of $S$. By Theorem \ref{thm:ERH} with probability
$\frac{1}{\log |S|}$ the number $a+b\alpha$ is prime. One then sets
$\wp = a+b\alpha$. If repeated $O(\log^2|S|)$ times, one can find $\wp$ with
overwhelming probability. The time complexity of the algorithm follows from
the fact that $|S| \leq \alpha^2 \leq \det(\Sym)^2$.
\end{proof}

The next step is to devise an algorithm that given the local form $\MS$,
positive integer $q$ and the generated
$t$ finds a primitive $\Vx$ such that $\Vx'\MS\Vx\equiv t\bmod{q}$.
Instead, we find primitive representations $\Vx_p$ for all $p$ that divides $q$
such that $\Vx_p'\MS_p\Vx_p \equiv t \bmod{p^k}$, where $\MS_p$ is
the $p^*$-equivalent
form, $k = \ord_p(q)$, and then combining them using Chinese Remainder.

The construction of $t$ used at most~4 diagonal entries of $\MS_p$
and so to find $\Vx_p$ we use Theorem \ref{thm:PolyRep}
and construct
$\Vx$ by filling the rest of the dimensions with $0$. The time taken
by this algorithm does not not depend on $n$ and is
$\poly(k,\log p)$, for each prime factor of $q$.

\section{Polynomial Time Algorithm}\label{sec:QFGenPoly}

In this section, we give the main contribution of this thesis.

\begin{theorem}\label{thm:Main}
Let $\Sym^n$ be a valid genus. Then, there exists a randomized
$\poly(n,\log \det(\Sym))$ algorithm that
outputs a quadratic form $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n \in \Sym$ with constant probability.
\end{theorem}
\begin{proof}
Recall definition of the
reduced genus. By Lemma \ref{lem:ReducedGenus}, it follows that
finding a quadratic form in $\Sym^*=\red(\Sym)$ suffices for generating
a quadratic form in $\Sym$.

The algorithm described in Section
\ref{sec:QFGen} is correct; but is not polynomial as it is.
The analysis of the time
complexity will be done on a different algorithm, the correctness
of which will follow from the proof of correctness of the algorithm
in Section \ref{sec:QFGen}. We now describe the algorithm.

\paragraph{}\textsc{QFGenPoly}({\em input:} valid symbol $\Sym^n$)
{\em output:} $\mathtt{Q}} \newcommand{\MS}{\mathtt{S}^n \in \Sym$
\begin{enumerate}[i.]
\addtolength{\itemsep}{-4pt}
\item If $n<4$ then return \textsc{QFGen}($\Sym$).
\item Compute $\gcd(\Sym)$ and let $\Sym^*=\Sym/\gcd(\Sym)$.
\item Find $t$ which has a primitive representation in $\Sym^*$.
Let $q=\overline{t^{n-1}\det(\Sym^*)}$ and $K_p=\ord_p(q)$.
\item For every $p\in\mathbb{P}_{\Sym}$, we construct a block diagonal matrix
$\MS_p$ and a matrix $[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p] \in \mathbb{Z}/p^{K_p}\mathbb{Z}$ as follows.
Use Theorem \ref{thm:LocalQF} to find a block diagonal matrix $\MD_p\overset{p^*}{\sim}\Upsilon_p^*$.
Recall the construction of $t$ in Lemma \ref{lem:TInDim4}.

If $p$ is odd then by construction, $t$ has a primitive representation in
$\mathbb{Z}/p^{K_p}\mathbb{Z}$ of two different types; (a) $t$ has a primitive representation
by the first entry of $\MD_p$. Let $x$ be the primitive representation.
Then, set $\MS_p=\MD_p$
and $[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p]=\begin{pmatrix}x & 0\\0 & x^{-1}\end{pmatrix}\oplus\MI^{n-2}$
, (b) otherwise, $t$ has a primitive representation
by two of the first three entries of $\MD_p$, say $d_1,d_2$ where
$\ord_p(d_1)\geq \ord_p(d_2)$. If $(x_1,x_2)$ is a primitive $p^{K_p}$
representation of $t$ then
in this case $x_1$ is primitive. Let $(\MD_p)_{3+}$ be the rest of the blocks
in $\MD_p$ then we set $\MS_p=d_1\oplus d_2 \oplus (\MD_p)_{3+}$ and
$[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p]=\begin{pmatrix}x_1 & 0\\x_2 & x_1^{-1}\end{pmatrix}\oplus\MI^{n-2}$.

On the other hand, when $p=2$ then too $t$ has a primitive representation in
$\mathbb{Z}/2^{K_2}\mathbb{Z}$ of two different kinds; (a) when $\Upsilon_2^*$ has a type II
block then if $x_1,x_2$ be the primitive representation with $x_1$ odd then we set
$\MS_2$ as the block diagonal form equivalent to $\MD_p$ where the first
block is the type II block which was used to represent $t$. Then, we set
$[\Vx_2,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_2]=\begin{pmatrix}x_1 & 0\\x_2 & x_1^{-1}\end{pmatrix}\oplus\MI^{n-2}$,
(b) otherwise the first four Type I entries of $\MD_2$ were used to represent
$t$ and $\ord_2((\MD_2)_4)=\ord_p(t)$, by construction. Also, if $x_1,x_2,x_3,x_4$
is the primitive representation of $t$ then $x_4$ is primitive. In this case, we set
$\MS_2$ as $(\MD_2)_4\oplus\cdots\oplus(\MD_2)_1\oplus(\MD_2)_{4+}$, and
$[\Vx_2,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_2]=\begin{pmatrix}x_4 & 0 & 0 &0\\x_3 & x_4^{-1}&0&0\\
x_2&0&1&0\\x_1&0&0&1\end{pmatrix}\oplus\MI^{n-4}$.

{\bf Property.} The construction satisfies the property that for each
$p \in \Upsilon_p$, $[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p] \in \gln(\mathbb{Z}/p^{K_p}\mathbb{Z})$ and
$\Vx_p'\MS_p\Vx_p\equiv t\bmod{p^{K_p}}$.

\item For each $p\in\mathbb{P}_{\Sym}$, let $\tilde{\Sym}_p=\SYM_p(\mathtt{H}} \newcommand{\MI}{\mathtt{I}_p)$, where $\mathtt{H}} \newcommand{\MI}{\mathtt{I}_p$
is defined as follows.
\begin{align}\label{HALG:dHP}
\begin{array}{ll}
\Vd_p=\Vx_p'\MS_p\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p \bmod{p^{K_p}}  &
\mathtt{H}} \newcommand{\MI}{\mathtt{I}_p = (t\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p'\MS_p\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p - \Vd_p'\Vd_p) \bmod{p^{K_p}}\\
\end{array}
\end{align}

\item Let $\tilde{\Sym}=\{\tilde{\Sym}_p:p\in\mathbb{P}_{\Sym}\}$, and $\tilde{\Sym}^*=\tilde{\Sym}/\gcd(\tilde{\Sym})$.
\item Call this algorithm recursively with input
$\tilde{\Sym}^*$. Let us suppose that the algorithm returns $\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}^* \in \gen(\tilde{\Sym}^*)$.
Then, set $\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}=\gcd(\tilde{\Sym})\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}^*$.
\item Use Chinese Remaindering to compute $[\Vx,\mathtt{A}} \newcommand{\MB}{\mathtt{B}]$ from
$\{[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p] \bmod{p^{K_p}}:p\in \mathbb{P}_{\Sym}\}$, $\MS$ from
$\{\MS_p\bmod{p^{K_p}}:p\in\mathbb{P}_{\Sym}\}$
and $\mathtt{H}} \newcommand{\MI}{\mathtt{I}$ from $\{\mathtt{H}} \newcommand{\MI}{\mathtt{I}_p\bmod{p^{K_p}}:p\in\mathbb{P}_{\Sym}\}$.
\item Canonicalize both $\mathtt{H}} \newcommand{\MI}{\mathtt{I}$ and $\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}$ over $\zRz{q}$, i.e., we find
$\tilde{\MU} \in \gl_{n-1}(\zRz{q})$ such that $\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}\equiv \tilde{\MU}'\mathtt{H}} \newcommand{\MI}{\mathtt{I}\tilde{\MU} \bmod q$.
\item Output the following quadratic form.
\begin{align}\label{ALGO:Q}
\mathtt{Q}} \newcommand{\MS}{\mathtt{S} = \gcd(\Sym)\begin{pmatrix}t & \Vd\tilde{\MU} \\
(\Vd\tilde{\MU})' & \frac{\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}+\tilde{\MU}'\Vd'\Vd\tilde{\MU}}{t}\end{pmatrix}
\end{align}
\addtolength{\itemsep}{4pt}
\end{enumerate}

The correctness of this algorithm follows from the proof before.

Let us compute the time complexity of this algorithm.

Our first step is to show that the recursions do not blow up the
size of the symbol. Notice that to calculate the $(n-1)$-dimensional
symbol, we multiply by $t$ in Equation \ref{HALG:dHP}. The analysis
is done below, separately for odd primes and $p=2$.

\paragraph{Odd primes.}
In this case, we show that $\ord_p(\tilde{\Sym}^*)=\ord_p(\Sym^*)$.
\medskip

For each odd $p\in\mathbb{P}_{\Sym}$, $\Vx_p'\MS_p\Vx_p\equiv t\bmod{p^{K_p}}$
and $[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p] \in \gln(\mathbb{Z}/p^{K_p}\mathbb{Z})$. Recall the two
cases discussed in the algorithm while constructing $\MS_p$ and
$[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p]$.
\begin{enumerate}
\item[Case 1:] Suppose $t$ is primitively
representable by the first entry of $\MS_p$. Let $x$ be the primitive
representation. Note
that $x$ is primitive and $(\MS_p)_1$ has $p$-scale~0 because
$\Sym^*$ is reduced.
The computation for $\mathtt{H}} \newcommand{\MI}{\mathtt{I}_p$ (and $\ord_p(\tilde{\Sym}))$
is as follows.
\begin{gather*}
[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p] \equiv \begin{pmatrix}x & 0 \\ 0 & x^{-1}\end{pmatrix}\oplus
\MI^{n-2}\bmod{p^{K_p}} \qquad \MS_p=s_1\oplus\cdots \oplus s_n\\
[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p]'\MS_p[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p] \equiv x^2s_1 \oplus s_2x^{-2}
\diag(s_3,\cdots) \bmod{p^{K_p}}\\
\mathtt{H}} \newcommand{\MI}{\mathtt{I}_p \equiv t\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p'\MS_p\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p - \Vd_p'\Vd_p\equiv
s_1s_2 \oplus x^2s_1\diag(s_3,\cdots,s_n) \bmod{p^{K_p}} \\
\ord_p(\tilde{\Sym})=\ord_p(\mathtt{H}} \newcommand{\MI}{\mathtt{I}_p)=\ord_p(x^2s_1s_n)=\ord_p(s_n)=\ord_p(\Sym^*)
\end{gather*}

\item[Case 2:] Otherwise, the first two entries of $\MS_p$
represent $t$. In this case, if $\MS_p=s_1\oplus\cdots \oplus s_n$,
then by construction, $\ord_p(s_1)\geq \ord_p(s_2)$ and $\ord_p(x_1)=0$,
where $x_1,x_2$ is the primitive representation of $t$ in $\MS_p$.
Then,
\begin{gather*}
[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p] = \begin{pmatrix}x_1 & 0 \\ x_2 & x_1^{-1}\end{pmatrix}\oplus \MI^{n-2}
\qquad \MS_p = s_1\oplus\cdots\oplus s_n\\
[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p]'\MS_p[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p] \equiv
\begin{pmatrix}s_1x_1^2+s_2x_2^2 & s_2x_1^{-1}x_2\\
s_2x_1^{-1}x_2 & s_2x_1^{-2}\end{pmatrix} \oplus \diag(s_3,\cdots,s_n)\bmod{p^{K_p}}\\
\mathtt{H}} \newcommand{\MI}{\mathtt{I}_p \equiv t\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p'\MS_p\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p - \Vd_p'\Vd_p
= s_1s_2\oplus(s_1x_1^2+s_2x_2^2)\diag(s_3 \cdots s_n) \bmod{p^{K_p}}
\end{gather*}
By construction, $s_1x_1^2+s_2x_2^2\equiv t\bmod{p^{K_p}}$, $x_1$ is primitive
and $\ord_p(s_2)=\ord_p(t)$. Thus, each entry of $\mathtt{H}} \newcommand{\MI}{\mathtt{I}_p$ is divisible by
$p^{\ord_p(t)}$. When we reduce $\tilde{\Sym}$ to $\tilde{\Sym}^*$, we have
$\ord_p(\tilde{\Sym}^*)=\ord_p(s_n)=\ord_p(\Sym^*)$.
\end{enumerate}
Thus, for odd prime $p$, in either case, $\ord_p(\tilde{\Sym}^*)=\ord_p(\Sym^*)$.

\paragraph{Prime $p=2$.} Recall the two cases discussed in the algorithm.
The first case is when $t$ has a primitive representation using a type II block.
By construction of $\MS_2$ in Theorem \ref{thm:LocalQF}, the block is
either $\mathtt{T}^{+}$ or $\mathtt{T}^{-}$. Let $i$ be the $2$-order of the block, then
\begin{gather*}
[\Vx_2,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_2] = \begin{pmatrix}x_1 & 0 \\ x_2 & x_1^{-1}\end{pmatrix}\oplus \MI^{n-2}
\qquad \MS_2 = 2^i\begin{pmatrix}2&1\\1&2c\end{pmatrix}\oplus(\MS_p)_{3+}\\
[\Vx_2,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_2]'\MS_2[\Vx_2,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_2] \equiv 2^i\begin{pmatrix}2x_1^2+2x_1x_2+2cx_2^2
& 1+2cx_2x_1^{-1}\\
1+2cx_2x_1^{-1} & 2cx_1^{-2}\end{pmatrix} \oplus (\MS_p)_{3+}\\
\mathtt{H}} \newcommand{\MI}{\mathtt{I}_2 = 4^i(4c-1) \oplus 2^i(2x_1^2+2x_1x_2+2cx_2^2)(\MS_p)_{3+}
\end{gather*}
Hence, $\ord_2(\tilde{\Sym}^*)\leq 1+\ord_2(\Sym^*)$. There could be at most~n Type II blocks
in a quadratic form of dimension~n, which can be generated during the recursion.
Thus, the $2$-order of the recursively generated reduced $2$-symbols remain
bounded by $\ord_p(\Sym^*)+n$.

Otherwise, $t$ has a primitive representation using the first four type I blocks
of $\MS_2$. In this case, the calculations are as follows.
\begin{gather*}
[\Vx_2,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_2] = \begin{pmatrix}x_4 & 0 & 0 & 0 \\ x_3 & x_4^{-1} & 0 & 0\\
x_2 & 0 & 1 & 0\\ x_1 & 0 & 0 & 1\end{pmatrix}\oplus \MI^{n-4}
\qquad \MS_2 = \diag(d_4,\cdots,d_1,s_5,\cdots,s_n)\\
t \equiv d_4x_4^2+\cdots+d_1x_1^2 \bmod{2^{K_2}}\\
[\Vx_2,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_2]'\MS_2[\Vx_2,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_2] =
\begin{pmatrix}t & d_3x_3x_4^{-1} &d_2x_2 & d_1x_1 \\
d_3x_3x_4^{-1} & d_3x_4^{-2} & 0 & 0\\
d_2x_2 & 0 & d_2 & 0\\
d_1x_1 & 0 & 0 & d_1\\
\end{pmatrix} \oplus (\MS_2)_{5+} \bmod{2^{K_2}}\\
\mathtt{H}} \newcommand{\MI}{\mathtt{I}_2 = \begin{pmatrix}d_3\frac{d_1x_1^2+d_2x_2^2+d_4x_4^2}{x_4^2}
& -\frac{x_3d_3x_2d_2}{x_4} & -\frac{x_3d_3x_1d_1}{x_4}\\
-\frac{x_3d_3x_2d_2}{x_4} & (d_1x_1^2+d_3x_3^2+d_4x_4^2)d_2 & -x_2d_2x_1d_1\\
-\frac{x_3d_3x_1d_1}{x_4} & -x_2d_2x_1d_1 & (d_2x_2^2+d_3x_3^2+d_4x_4^2)d_1
\end{pmatrix}\\
\oplus t(\MS_2)_{5+} \bmod{2^{K_2}}
\end{gather*}
Recall Lemma \ref{lem:RepMod2Dim4}. By
construction of $x_1,\cdots,x_4$
it follows that for each $i\in[4]$,
$\ord_2(d_ix_i^2)\geq \ord_2(d_4)=\ord_2(t)$,
$\ord_2(d_4)\geq \cdots \geq \ord_2(d_1)$ and $\ord_2(x_4)=0$.
This implies that $\ord_2(x_1)\geq \cdots\geq \ord_2(x_4)=0$ and
by inspection, every entry in the first $3\times3$ submatrix
of $\mathtt{H}} \newcommand{\MI}{\mathtt{I}_2$ is divisible by $2^{\ord_2(t)}$. Thus,
$\ord_2(\tilde{\Sym}^*)=\ord_2(\Sym^*)$.

To recapitulate, $\ord_p(\tilde{\Sym}^*)$ is equal to $\ord_p(\Sym^*)$
unless we use a Type II block to represent $t$ modulo $\mathbb{Z}/2^{K_2}\mathbb{Z}$,
in which case it increases by exactly~1.

The step by step calculation of the time taken by the algorithm is
as follows.

\begin{enumerate}[(i.)]
\item After calculating the reduced symbol $\Sym^*$, the algorithm
starts by computing a positive
integer $t$ which is primitively representable in $\Sym^*$. For
$n\geq4$ such an integer can be found by looking at the first~4
dimensions of the symbol $\Sym$, see Lemma \ref{lem:TInDim4}.
This takes time linear in the number of relevant primes of $\Sym$
i.e., $O(|\mathbb{P}_{\Sym}|(\log\det(\Sym^*))^2)$.
\item Next, we find a quadratic form $\MS$ which is equivalent
to $\Sym^*$ over the ring $\zRz{q}$, for $q=\overline{t^{n-1}\det(\Sym^*)}$.
By Lemma \ref{lem:TInDim4}, the integer $t$ has the property that
$t$ divides $\det(\Sym^*)$. Thus, we do not introduce any new primes and
for every prime $p \in \mathbb{P}_{\Sym}$;
\[
\ord_p(q) \leq n\ord_p(\det(\Sym^*))+k_p\;.
\]
By Theorem \ref{thm:LocalQF}, finding such an integral quadratic form
$\MS_p$ takes time $\poly(n,\log \det(\Sym) , \log p)$. There are $|\mathbb{P}_{\Sym}|$
relevant primes and hence the total time in this step is.
\begin{align}\label{Time:FindS}
\poly(|\mathbb{P}_{\Sym}|, n,\log\det(\Sym^*))
\end{align}
\item Then, we find a primitive representation $\Vx_p$ of $t$ in $\MS_p$ over
$\zRz{p^k}$, $k=\ord_p(q)\leq n\log\det(\Sym^*)$,
for all $p \in \mathbb{P}_{\Sym}$. Note that
the representation is done by
Theorem \ref{thm:PolyRep} on a $4\times 4$ submatrix, which takes time
$\poly(k,\log p)$. By the bound on $k$, we get the following
expression.
\begin{align}\label{Time:Findx}
O(|\mathbb{P}_{\Sym}|,n,\log\det(\Sym^*))\;.
\end{align}
\item Then, we Chinese Remainder the matrices $[\Vx_p,\mathtt{A}} \newcommand{\MB}{\mathtt{B}_p]$, $\MS_p$
and $\mathtt{H}} \newcommand{\MI}{\mathtt{I}_p$ entry-by-entry ($ \leq n^2$ entries in each matrix)
to get $[\Vx,\mathtt{A}} \newcommand{\MB}{\mathtt{B}]$, $\MS$ and $\mathtt{H}} \newcommand{\MI}{\mathtt{I}$, respectively.
The modulus of the Chinese Remainder is $q$. This takes time
$\poly(|\mathbb{P}_{\Sym}|,n, \log q)$.
\item Finally, we canonicalize both $\mathtt{H}} \newcommand{\MI}{\mathtt{I}$ and $\tilde{\mathtt{H}} \newcommand{\MI}{\mathtt{I}}$ modulo $q$. This
is again done by canonicalizing for each prime that divides $q$ and then
Chinese Remaindering the results. For each $p$,
$\ord_p(q) \leq n\log\det(\Sym^*)$. Thus, the time taken for each $p$ is
bounded by $\poly(|\mathbb{P}_{\Sym}|, n, \log\det(\Sym^*))$.
\end{enumerate}

The next step is to calculate the reduced form $\tilde{\Sym}^*$ and recurse.
By the discussion of the blowup above, it follows that
$\det(\tilde{\Sym}^*) \leq 2^{n-2}\det(\Sym^*)$. Or,
$\log \det(\tilde{\Sym}^*)\leq (n-2)\log 2+\log \det(\Sym)$. Thus the total
time complexity of the algorithm can be written recursively
as
\begin{align*}
T(n,\det(\Sym^*)) &= T(n-1,2^{n-2}\det(\Sym^*))
+ \poly(|\mathbb{P}_{\Sym}|,n, \log\det(\Sym^*))
\end{align*}

Although the blowup in the determinant is exponential, all our
algorithms run in $\poly(\log d, |\mathbb{P}_{\Sym}|)$, where $d$ is the
determinant of the input genus. For $n \leq 3$,
$t \leq \wp d$, and $\wp \leq d^2$. Thus, for any constant $\delta > 0$
the generation algorithm runs in time
$\poly(n,\log d, \log \frac{1}{\delta})$ and succeeds with
probability at least $1-\delta$.
\end{proof}

\bibliographystyle{alpha}

redpajama_set_name: RedPajamaArXiv