isomorphism_polynomials.tex

\documentclass{amsart}
%\usepackage[margin=30mm]{geometry}
\usepackage{unicode}
\DeclareUnicodeCharacter{22F1}{\smash\ddots}
\DeclareUnicodeCharacter{22F0}{\smash\iddots}
\DeclareUnicodeCharacter{2264}{\leqslant}
\DeclareUnicodeCharacter{2265}{\geqslant}
\usepackage{amsmath,amssymb,mathrsfs}
\usepackage{bm}
\usepackage{lmodern}
\usepackage{mathdots}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{graphicx}
% \usepackage{lineno}\linenumbers
\usepackage{booktabs,multirow}

\newif\ifapx \apxtrue % If appendix

% Colors%<<<
\usepackage{color}
\definecolor{purple}{rgb}{.49,.11,.61}
\definecolor{green}{rgb}{.08,.69,.10}
\definecolor{blue}{rgb}{.01,.26,.87}
\definecolor{pink}{rgb}{1,.5,.75}
\definecolor{brown}{rgb}{.39,.21,.00}
\definecolor{red}{rgb}{.89,0,0}
\definecolor{lightblue}{rgb}{.58,.81,.98} 
\definecolor{teal}{rgb}{0,.57,.52}
\definecolor{orange}{rgb}{.97,.45,.02}
\definecolor{lightgreen}{rgb}{.53,.99,.01}
\definecolor{magenta}{rgb}{.76,0,.47}
%>>>
\usepackage{soulutf8}\sethlcolor{pink} \def\todo#1{\hl{#1}}
% Theorems, equations, counters%<<<
\def\linkcounter#1#2{\edef\magic{\noexpand\let
  \expandafter\noexpand\csname c@#1\endcsname
  \expandafter\noexpand\csname c@#2\endcsname}\magic}
\def\newthm#1#2{\newtheorem{#1}{#2}[section]\linkcounter{#1}{equation}}
\newthm{prop}{Proposition}
\newthm{thm}{Theorem}
\newthm{lem}{Lemma}
\def\theequation{\thesection.\arabic{equation}}

\def\labelenumi{(\roman{enumi})}
\def\itemref#1{\expandafter\ifx\csname r@#1\endcsname\relax
  {\bfseries ??}\else{\setcounter{enumi}{\ref{#1}}\labelenumi}\fi}
\def\proofof{Proof of }
\let\realpar\paragraph
\def\paragraph#1{\realpar{\textbf{#1}}}
% Bib aliases
\makeatletter%<<<
\def\@citex[#1]#2{\leavevmode
  \let\@citea\@empty
  \@cite{\@for\@citeb:=#2\do
    {\@citea\def\@citea{,\penalty\@m\ }%
\edef\magic##1{\let##1\expandafter\noexpand\csname bibalias@\@citeb\endcsname}%
\magic\tmp \ifx\tmp\relax\else \let\@citeb\tmp\fi
     \edef\@citeb{\expandafter\@firstofone\@citeb\@empty}%
     \if@filesw\immediate\write\@auxout{\string\citation{\@citeb}}\fi
     \@ifundefined{b@\@citeb}{\hbox{\reset@font\bfseries ?}%
       \G@refundefinedtrue
       \@latex@warning
         {Citation `\@citeb' on page \thepage \space undefined}}%
       {\@cite@ofmt{\csname b@\@citeb\endcsname}}}}{#1}}
\def\bibalias#1#2{\expandafter\def\csname bibalias@#1\endcsname{#2}}
\makeatother%>>>
\bibalias{2013bfp}{DBLP:journals/corr/BerthomieuFP13}
%>>>
% Misc. math stuff%<<<
\def\bigperp{\mathop{\vcenter{\hbox{\scalebox{2}{\ensuremath{\perp}}}}}%
  \displaylimits}
\let\fr\mathfrak
\let\ro\mathscr
% \def\transpose{\,{}^{\mathrm{t}\!}}
\def\transpose#1{{\vphantom{#1}}^{\mathrm{t}}\!#1}
\def\pa#1{\left(#1\right)}
\def\floor#1{\left\lfloor#1\right\rfloor}
\def\chev#1{\left\langle#1\right\rangle}
\def\acco#1{\left\{#1\right\}}
\def\abs#1{\left|#1\right|}
\def\mat#1{\begin{pmatrix}#1\end{pmatrix}}
\def\smat{\def\arraystretch{.66}\mat}
\def\card#1{\abs{#1}}
\def\chk#1{#1^{\smash{\scalebox{.7}[1.4]{\rotatebox{90}{\guilsinglleft}}}}}
\DeclareMathOperator\Ker{Ker}
\DeclareMathOperator\Hom{Hom}
\DeclareMathOperator\End{End}
\DeclareMathOperator\GL{GL}
\DeclareMathOperator\PGL{PGL}
\DeclareMathOperator\Tr{Tr}
\def\F{\mathbb{F}}
\def\Id{\mathrm{Id}}
\def\M{\mathsf{M}}
\def\Ot{\widetilde{O}}
\def\plusort{\stackrel{⟂}{⊕}}
\def\gitkw$#1:#2${{\small \textbf{#1: }\texttt{#2}}}
%>>>
% Stretching diagonal dots%<<<
\makeatletter
\def\clap #1{\hbox to 0pt{\hss#1\hss}}
\def\stretchdots#1#2#3#4{
  \setbox0=\hbox{$#4$}\dimen0= \wd0 \advance \dimen0 2\arraycolsep
  \rlap{\kern -\arraycolsep \hbox to \dimen0 {%
  \hss \raise #1 \clap{$.$}\hss
  \hss \raise #2 \clap{$\m@th.$}\hss
  \hss \raise #3 \clap{$\m@th.$}\hss}}%
  \kern \wd0
}
\def\siddots{\stretchdots{0pt}{4pt}{8pt}}
\def\sddots{\stretchdots{8pt}{4pt}{0pt}}
\makeatother%>>>
%>>>1

% $Date:$
\title[Pairs of quadratic forms]%<<<1
{Computing Isomorphisms between Pairs of Quadratic Forms in Polynomial Time}
% {Solving the ``Isomorphism of Polynomials with Two Secrets'' Problem
% for All Pairs of Quadratic Forms}
% \keywords{Quadratic forms, pencils of quadratic forms,
% isomorphism of polynomials, multivariate cryptography}
% \subjclass[2000]{15A63, 15A22, 15A21, 11T71}
% \author{Jérôme Plût}
% \email{jerome.plut@ssi.gouv.fr}
% \address{Agence Nationale de la Sécurité des Systèmes d'Information --- 51,
% boulevard de La Tour-Maubourg, 75007 Paris, France}
% \author{Pierre-Alain Fouque}
% \email{pierre-alain.fouque@ens.fr}
% \address{Université Rennes 1, Campus de Beaulieu ---
% 263, avenue du Général Leclerc - Batiment 12
% 35042 Rennes Cedex, France}
% \author{Gilles Macario-Rat}
% \email{gilles.macariorat@orange.com}
% \address{Orange Labs --- 38-40, rue du Général Leclerc,
% 92130 Issy-les-Moulineaux, France}
% \author{Jérôme Plût\footnote{ANSSI}
% \and Pierre-Alain Fouque\footnote{Université Rennes 1 and Institut
% Universitaire de France}
% \and Gilles Macario-Rat\footnote{Orange Labs}}
\author[J. Plût, P.-A. Fouque and G. Macario-Rat]%
{Jérôme Plût, Pierre-Alain Fouque and Gilles Macario-Rat}

% \centerline{\gitkw $Id:$
% \gitkw $Author:$
% \gitkw $Date:$}

\begin{document}
\maketitle
\begin{abstract}%<<<
We study the Isomorphism of Polynomial (IP2S) problem
with~$m=2$ homogeneous quadratic polynomials of $n$ variables over a finite field
characteristic: given two pairs~$(\bm{a}, \bm{b})$
of quadratic forms on $n$~variables,
we compute two bijective linear maps $(s,t)$ such that
$\bm{b}=t\circ \bm{a}\circ s$.
We give an algorithm computing~$s$ and~$t$
in worst-case time complexity~$O(n^{ω+1})$ in odd characteristic
and~$O(n^{2ω})$ in characteristic two,
and~$O(n^3)$ on average in all characteristics,
where $ω$~is a linear algebra exponent.
% 
% The IP2S problem was introduced in cryptography by Patarin back in 1996.
% The special case of this problem when $t$ is the identity is called
% the isomorphism with one secret (IP1S) problem.
% Generic algebraic equation solvers (for example using Gröbner bases)
% solve quite well random instances of the IP1S problem. For the particular
% \emph{cyclic} instances of IP1S, a cubic-time algorithm was later
% given~\cite{MPG2013} and explained in terms of pencils of quadratic forms
% over all finite fields; in particular, the cyclic IP1S problem in odd
% characteristic reduces to the computation of the square root of a matrix.
% 
% We give here an algorithm solving all cases of the IP1S problem in odd
% characteristic using two new tools, the Kronecker form for a singular
% quadratic pencil, and the reduction of bilinear forms over a non-commutative
% algebra. Finally, we show that the second secret in the IP2S problem may
% be recovered in cubic time.
\end{abstract}%>>>
\maketitle
\section*{Introduction}
\subsection*{The IP1S and IP2S problems}


The \emph{Isomorphism of Polynomial with Two Secrets} (IP2S) problem is
the following: given a field~$k$ and two $m$-uples $\bm{a} = (a_1, …,
a_m)$ and~$\bm{b} = (b_1, …, b_m)$ in $n$~variables~$(x_1, …, x_n)$, compute
two invertible linear maps~$s ∈ \GL_n(k)$ of the variables~$x_i$
and~$t ∈ \GL_m(k)$ of the polynomials~$a_i$ such that
\begin{equation*}
\bm{b} = t ∘ \bm{a} ∘ s.
\end{equation*}
The particular case where we restrict~$t$ to the identity transformation
is also known as \emph{Isomorphism of Polynomials with One Secret}
(IP1S).
Both these problems were introduced in cryptography by
Patarin~\cite{DBLP:conf/eurocrypt/Patarin96} to construct an efficient
authentication scheme, 
as an alternative to the Graph Isomorphism Problem (GI) proposed by Goldreich, Micali and Wigderson~\cite{DBLP:journals/jacm/GoldreichMW91}.
The IP problem was appealing since 
it seems more difficult than the Graph Isomorphism problem~\cite{DBLP:conf/eurocrypt/PatarinGC98}. 
Agrawal and Saxena reduced~\cite{DBLP:conf/stacs/AgrawalS06} the Graph
Isomorphism problem to a particular case of IP1S using two polynomials.
% one of them being a quadratic form encoding the adjacency matrix of the
% graph, and the other one being the cubic~$\sum x_i^3$, over a finite field of
% odd characteristic.
For the case of quadratic polynomials, the status of this problem is unclear despite recent 
intensive research in the cryptographic community since this case is the most interesting 
for practical schemes. There exists a claimed reduction between the quadratic IP1S problem and the GI
problem~\cite{DBLP:conf/eurocrypt/PatarinGC98}, but we realized that this proof is incomplete. 
Indeed, the proof works by induction and decomposes any permutation as the composition of 
transpositions. It is possible to write a system of quadratic polynomials such that the only solutions 
of the IP1S problem will be the identity or a transposition by modifying a bit the systems proposed 
in~\cite{DBLP:conf/eurocrypt/PatarinGC98}. However, it is not obvious how we can compose the systems 
of equations such that the solutions will be the composition of the solutions. 

\bigbreak

The defining parameters of the IP problems are the number~$n$ of
variables, the number~$m$ of polynomials, their degree, and the finite
field~$k$.
For efficiency reasons, the degree is generally small:
only quadratic and cubic equations are involved.
To our knowledge, no significant progress has been done on the cubic case.

We limit ourselves to the special case of two equations, both
being homogeneous polynomials of degree~two. According to previous
literature~\cite{DBLP:conf/eurocrypt/Perret05,DBLP:conf/eurocrypt/FaugereP06,DBLP:conf/pkc/BouillaguetFFP11,DBLP:conf/eurocrypt/BouillaguetFV13},
this is the most difficult case.

The case of only one homogeneous quadratic equation
is solved by reduction of quadratic forms,
which has been known for centuries~\cite{gauss,lidl1997finite}.
In the non-homogeneous case, the presence of affine terms
gives linear relations between
the secret unknowns~\cite{DBLP:conf/eurocrypt/PatarinGC98},
and this extra information actually helps generic solvers,
for example those using Gröbner bases~\cite{DBLP:conf/eurocrypt/FaugereP06}.
The case of more than two equations is easier since we can relinearize
the systems~\cite{DBLP:conf/pkc/BouillaguetFFP11}.

\subsection*{Previous work}

The (closely related) problem of finding a normal form
for pairs of symmetric bilinear forms
has been studied since the second half of the 19\textsuperscript{th} century.
The problem depends on both the characteristic of the base field,
and on the regularity of the bilinear forms
(\emph{i.e.} whether one of the forms in the pair is invertible).
Since bilinear and quadratic pairs over the real numbers occur naturally
in a large class of physics and optimization problems,
these cases have historically been studied in much more depth
than the corresponding problem over finite fields,
and some textbook proofs even use complex analysis~\cite[XII(56)]{Gantmacher}.
The following table gives a summary of proofs of the various cases
of reduction of a pair of symmetric bilinear forms.
Another report is given in~\cite{olomouc2004fv}.

\setlength\tabcolsep{.2em}\smallbreak
\begin{center}\begin{tabular}{llll}
Characteristic & zero & odd & two \\
\toprule
regular & Weierstraß 1858\cite{1858weierstrass}
  & Dickson 1909\cite{ams1909dickson}
  & \multirow{2}{*}{Waterhouse 1977\cite{pacific1977waterhouse}} \\
singular & Kronecker 1890\cite{1890kronecker}
  & Waterhouse 1976\cite{inventiones1976waterhouse} & \\
\bottomrule
\end{tabular}\end{center}\medbreak

% Despite the different techniques used in the proof,
% depending on the characteristic
% (\emph{e.g.} the first proofs in characteristic zero
% used complex-analytic methods),
% in the end the result is always the same
% (and it is possible to give a unified proof of it):
% a pair of bilinear forms is the direct sum of a \emph{regular} part,
% which is classified by invariant factors;
% and of a \emph{singular} part, which is classified by dimensions.
% 
If $2 ≠ 0$, then quadratic and bilinear forms coincide,
thus the odd-characteristic case of the problem
was solved before it was even proposed.
After the proposal of using pairs of quadratic forms by Patarin,
there were also some advances by cryptographers,
most of them unaware of the previous work cited above.

Bouillaguet, Fouque and Macario-Rat solved
in 2011~\cite{DBLP:conf/asiacrypt/BouillaguetFM11}
the special case where, in odd characteristic,
one of the maps is the Weil restriction of $x ↦ x σ(x)$,
where $σ$~is the Frobenius automorphism.

% used \emph{pencils} of quadratic forms,
% which are pairs~$(b_{∞}, b_0)$ of such forms,
% to recover the secret mappings $s$ and $t$ when three equations are available
% and one of the quadratic equations $\bm{a}$
% comes from a special mapping $X\mapsto X^{q^\theta+1}$ over $\F_q$.
% In the case of the IP problem,
% this is optimal using an information theoretic argument.
% A case of interest is the particular case of \emph{cyclic} pencils: a
% pencil~$\bm{b} = (b_{∞}, b_0)$ is \emph{cyclic} if $b_{∞}$~is invertible
% and $b_{∞}^{-1} b_{0}$ is a cyclic matrix, \emph{i.e.} its characteristic
% polynomial is equal to its minimal polynomial. The cyclic case is
% dominant (it is defined by the non-cancellation of some polynomial
% functions of the coefficients of~$\bm{b}$). For cyclic instances of the
% IP1S problem, the Gröbner basis approach works
% well~\cite{DBLP:conf/pkc/BouillaguetFFP11} since the number of solutions
% is known to be small. For all other instances, the number of solutions is
% empirically large and such algorithms are then well known to be less
% efficient.
Macario-Rat, Plût and Gilbert gave in 2013~\cite{MPG2013}
an algebraic solution to the cyclic instances of the IP1S problem
for $m=2$ over finite fields of any characteristic.
% Macario-Rat, Plût and Gilbert explained in 2013~\cite{MPG2013} how to
% solve cyclic instances of the IP1S problem for~$m=2$ over finite fields
% of any characteristic. A pencil~$\bm{b} = (b_{∞}, b_0)$ is \emph{cyclic}
% if $b_{∞}$~is invertible and~$b_{∞}^{-1} b_{0}$ is a cyclic matrix,
% \emph{i.e.} its characteristic polynomial is equal to its minimal
% polynomial. Although the cyclic case is dominant (it is defined by the
% non-cancellation of some polynomial functions
% of the coefficients of~$\bm{b}$), it is not the general case in a
% practical sense. In the cyclic instances, Gröbner bases works
% well~\cite{DBLP:conf/pkc/BouillaguetFFP11} since in this case, the number
% of solutions is small. For all other instances, the number of solutions
% is large, and it is well-known that in this case, such algorithms are
% less efficient.

Finally, Berthomieu, Faugère and Perret
proposed in 2014~\cite{DBLP:journals/corr/BerthomieuFP13}
a polynomial algorithm for the regular, odd-characteristic instances of IP1S
with any number of equations,
inspired by the characteristic-zero methods.
We compare our method to theirs in Appendix~\ref{ap:polar}.

% Given two families of polynomials over a field~$k$,
% they give a solution to the IP1S problem
% over a tower~$k'$ of real quadratic extensions of~$k$
% (where a \emph{real quadratic extension} is obtained by
% adjoining the square root of a sum of squares).
% This solves the IP1S problem over the original field~$k$ only when
% $k$~is \emph{Euclidean}, \emph{i.e.} has no real quadratic extension.
% This is the case for example if $k$~is a closed real field such as~$ℝ$
% or the field~$ℝ_{\mathrm{alg}}$ of real algebraic numbers,
% or an algebraically closed field;
% however, since any quadratic extension of a finite field is real,
% no finite field is Euclidean.

% Over the
% original field, this solves the \emph{decisional} IP1S problem:
% determining whether two families of polynomials are isomorphic. This
% latter problem does not have many cryptographic applications.

\subsection*{Our contributions}

These previous works left open the case of singular pencils,
as well as the characteristic-two case
and the IP2S problem.
We give here a solution to these three problems.

We first review the mathematical theory behind pairs of \emph{bilinear} forms,
adding an algorithmic point of view to the classic theorems.
% Since this is a solved problem, we have been able to omit most proofs in
% this part.
% 
% We start by studying the bilinear forms associated to
% a pair of quadratic forms.
Such a bilinear pair decomposes canonically as the orthogonal sum of
a “totally singular” and a regular part.
The totally singular part is canonically isomorphic to a sum of
standard objects called Kronecker modules,
while the regular parts is classified by invariant factors
and some quadratic invariants.

In characteristic different from two,
this theory gives a full classification of quadratic forms.
We use this to give a solution to the IP1S problem.
% In that case, the mathematics of bilinear pairs
% directly translate to a polynomial algorithm for solving the IP1S problem.
In this first part, we follow the previous treatment of
the bilinear case given by Waterhouse~\cite{inventiones1976waterhouse};
our contributions consist in detailing some algorithms
as well as clarifying the status of characteristic~two.

We then cover the case of quadratic forms in characteristic two.
In both the singular and the regular case,
we give a description of the groups of automorphisms
of the associated bilinear forms.
We then show how to find, in these sets,
a transformation with the required action on the diagonal coefficients.


The last section explains how to recover the second (``outer'') secret
in the two-secret IP2S problem.
We determine this transformation by its action on the invariant factors.
% Since applying an outer linear combination to a Kronecker module
% leaves it unchanged (up to almost-unique isomorphism),
% the regular part is enough to recover the outer secret.
% This is done using the factorization of the characteristic polynomial.

\subsection*{Mathematical background and notations}
Throughout this document, $k$~is a finite field
and $V$~is a $n$-dimensional vector space over~$k$.
We study the IP1S and IP2S problems for \emph{$k$-quadratic forms} on~$V$,
which are homogeneous polynomials of degree~$2$ in coordinates on~$V$
and with coefficients in~$k$.
To a quadratic form~$q$,
one may associate its \emph{polar form}~$b$ defined by
\begin{equation*}\label{eq:polar}
b(x,y) = q(x+y) - q(x) - q(y);
\end{equation*}
this is a symmetric $k$-bilinear form,
and it satisfies the \emph{polarity identity}
\begin{equation*}\label{eq:polarity}
b(x,x) = 2q(x).
\end{equation*}
If~$2 ≠ 0$ in~$k$, then the polarity identity is a bijection between
quadratic forms and bilinear forms.
Therefore, instead of quadratic forms, we shall study bilinear forms.

In the case where~$2 = 0$ in~$k$, the situation is more complicated;
the polarity map is neither injective nor surjective
(polar forms are always alternating bilinear forms).
We refer to~\cite{milnorhusemoller} for a classification of
binary quadratic forms.

It will be convenient here do designate by \emph{polar forms}
the image of the polarity map: that is, symmetric bilinear forms if~$2 ≠ 0$,
and alternating bilinear forms if~$2 = 0$.

\medbreak
We define a \emph{pencil} of quadratic forms
as a pair~$(q_0, q_∞)$ of quadratic forms,
or equivalently, as the affine line~$(q_λ = q_0 - λ q_{∞})$
with base points~$q_0, q_∞$.
Likewise, we define bilinear and polar pencils.
There are obvious notions of orthogonal sum and polarity for these pencils.

We say that a bilinear pencil is \emph{regular}
if its characteristic polynomial~$\det (q_λ)$ is not zero,
and \emph{singular} otherwise.
A quadratic pencil is regular if its polar pencil is regular.


% This means that their classification is%<<<
% quite different from the odd-characteristic case~\cite{milnorhusemoller}.
% and relies on the Arf invariant.
% 
% Let~$\chk{V}$ be the dual of the vector space~$V$.
% A bilinear form~$b$ on~$V$ is the same as a linear map~$b: V → \chk{V}$.
% The bilinear form is \emph{regular} if it defines
% an invertible linear map~$V → \chk{V}$.
% In this case, for any endomorphism~$u$ of~$V$,
% there exists a unique endomorphism~$u^{⋆}$ of~$V$
% such that~$b(x,u(y)) = b(u^{⋆}(x), y)$;
% the endomorphism~$u^{⋆}$ is called the \emph{left-adjoint} of~$u$.
% If $b$~is symmetric then left- and right-adjoints coincide.
% 
% An \emph{(affine) pencil of symmetric bilinear forms} over~$V$,
% or a \emph{symmetric pencil} in short,
% is a pair of symmetric bilinear forms~$\bm{b} = (b_{∞}, b_{0})$ over~$V$.
% We write this pencil in affine form as~$b_{λ} = λ b_{∞} + b_{0}$,
% and in projective form as~$b_{λ:μ} = λ b_{∞} + μ b_{0}$,
% where $b_{0}$ and~$b_{∞}$ are symmetric bilinear forms.
% Given two vector spaces equipped with pencils~$(V, b)$ and~$(V', b')$, a
% \emph{linear map} of pencils is a linear map~$s: V → V'$ such
% that~$b'_{λ} ∘ s = b_{λ}$.
% A \emph{projective map} of pencils is a pair~$(s, t)$,
% where $s: V → V'$ is a linear map
% and $t ∈ \PGL_2 (k)$~is a homography such that~$b'_{λ} ∘ s = b_{t(λ)}$.
% We define quadratic pencils in the same way.
% The IP1S problem is then the computation of
% a linear isomorphism of quadratic pencils,
% whereas the IP2S problem is the computation of a projective isomorphism.
%>>>
% We define a \emph{(affine) pencil} of symmetric bilinear forms%<<<
% as an ordered pair of quadratic forms~$\bm{b} = (b_∞, b_0)$ on~$V$.
% Such a pencil also corresponds to the affine line~$b_{λ} = λ b_∞ + b_0$.
% There is an obvious definition of orthogonal sum for bilinear pencils.
% We define in the same way affine pencils of quadratic forms;
% the polar of a quadratic pencil is a symmetric bilinear pencil.
%%>>>
% Two elements~$x$ and~$y$ of~$V$ are \emph{orthogonal} for a%<<<
% bilinear form~$b$ if~$b(x,y) = 0$.
% They are orthogonal for a pencil~$(b_{λ})$ if,
% for all~$λ$, $b_{λ}(x,y) = 0$.
% We write~$x ⟂_{b} y$,
% or $x ⟂ y$ when the context makes the bilinear form, or pencil, obvious.
% We write~$W^{⟂}$ for the orthogonal of a subspace~$W ⊂ V$.
% A space~$W$ is \emph{self-orthogonal} if~$W ⊂ W^{⟂}$.
%>>>

\bigbreak

For any ring~$R$, we write~$R^{m×n}$ for the vector space of
matrices with entries in~$R$ having $m$~lines and $n$~columns,
and $\transpose{A}$~for the transpose of a matrix~$A$.
% A \emph{symmetric} matrix is a matrix such that~$A = \transpose{A}$.
Symmetric bilinear forms~$b$ correspond to symmetric matrices~$B$.
A bilinear form is regular iff its matrix is invertible.
For any endomorphism~$u$ with matrix~$U$,
the adjoint endomorphism (relatively to~$B$)
has the matrix~$U^{⋆} = B^{-1} · \transpose{U} · B$.
The \emph{companion matrix}~$M_f$ of a polynomial~$f$
is the matrix of multiplication by~$x$
in the basis~$\acco{1,x,…,x^{\deg f-1}}$ of the quotient ring~$k[x]/f(x)$.

\medbreak

We also recall Hensel's lemma~\cite[II~(4.6)]{neukirch1999algebraic},
which is a powerful tool for solving algebraic equations in a local ring.
Let~$R$ be a complete local ring with maximal ideal~$\fr m$ and quotient
field~$k = R/\fr m$; let~$f ∈ R[x]$ be a polynomial and~$a ∈ k$ such
that~$f(a) = 0$ and~$f'(a) ≠ 0$ (\emph{i.e.} $a$~is a simple root of~$f$
modulo~$\fr m$). Then there exists a unique simple root~$b$ of~$f$ in~$R$
such that~$b ≡ a \pmod{m}$.

\medbreak

All complexities will be given as a number of operations
in the base field~$k$.
We write~$\M(n)$ for the cost of multiplication of polynomials of degree~$n$,
and~$ω$ for an exponent such that linear algebra of dimension~$n$
has cost~$n^{ω}$.
% For example,
% since Hensel lifts are computed via Newton's approximation method,
% lifting a root of a degree~$d$ polynomial to a ring of length~$n$
% requires $O(d \log n)$ operations.
% For simplicity, we will assume that the ``schoolbook'' methods are used
% for matrix and polynomial algebra;
% thus, matrix inversion has a cost of~$O(n^3)$,
% and polynomial multiplication has a cost of~$O(n^2)$.

%>>>1
\section{A review of results on bilinear pencils}
\label{s:bilinear}
\subsection{Kronecker decomposition}


For any integer~$h ≥ 0$, we define the \emph{Kronecker module}
of degree~$h$ as the vector space~$k^{2h+1}$
equipped with the bilinear pencil with matrix
\begin{equation}\label{eq:def-K}
{\def\arraystretch{.8}
q_0 - λ q_∞ = K_{h} = \mat{0&K'_{h}\\\transpose{K'_{h}}&0},
\quad \text{where}\quad
K'_h = \mat{-λ&&0\\1&\sddots{-λ}&\\&\sddots{-λ}&-λ\\0&&1}}.
\end{equation}
This is a singular symmetric bilinear pencil.

% We know~\cite[§3]{inventiones1976waterhouse}
% that any pencil has a unique \emph{Kronecker decomposition},
% that is, as an orthogonal sum of a regular pencil and of Kronecker modules.
% Moreover, the multiplicity of each Kronecker module~$K_h$ in this
% decomposition are also unique.

\begin{prop}[Kronecker decomposition]\label{prop:kronecker-decomposition}
Let~$(b_{λ}) = b_0 - λ b_∞$ be a symmetric bilinear pencil on~$k^n$.
Further assume that either~$2 ≠ 0$ in~$k$,
or that both $b_0$~and~$b_∞$ are alternating.
\begin{enumerate}
\item There exists a unique decomposition of the pencil~$(b_λ)$
as an orthogonal sum of a regular pencil
and of Kronecker modules.
\item There exists an algorithm computing this decomposition
in a time polynomial in~$n$.
\end{enumerate}
\end{prop}
\begin{proof}[\proofof Proposition~\ref{prop:kronecker-decomposition}]
The proof of the Kronecker decomposition~(i) published
by Waterhouse in 1976~\cite[Theorem 3.1]{inventiones1976waterhouse}
gives an algorithm for computing it.
That proof was written under the assumption that~$2 ≠ 0$ in~$k$;
but the only divisions by two used in the proof
involve halving some diagonal coefficients~$A(x,x)$ and~$B(x,x)$,
and it is therefore still valid in characteristic two
if we assume that $A$~and~$B$ are alternating.

The 1976 algorithm begins by computing (a Hermite normal form of)
the kernel of the matrix~$q_0 - λ q_∞$,
with coefficients in the polynomial ring~$k[λ]$.
Since the maximum degree appearing in the coefficients is~$n$,
and assuming that school-book multiplication is used in~$k[λ]$,
this requires at most~$O(n^ω\, \M(n))$~operations in the field~$k$.
\end{proof}

We give in Appendix~\ref{ap:kronecker} an algorithm
with complexity~$O((h_{\max}+1)\,n^ω)$,
where $h_{\max}$~is the maximal degree of
a Kronecker module factor of the pencil.
Since~$2h_{\max}+1 ≤ n$,
this algorithm has a worst-case complexity of~$O(n^{ω+1})$,
and, given that a generic bilinear pencil is regular,
an average-case complexity of~$O(n^ω)$.

% Let~$h$ be the smallest degree such that $E_{h} ∩ (\Ker A)$ is not zero.%<<<
% By \cite[Lemma 3.2]{inventiones1976waterhouse}, we know that
% $V$~contains $(2h + 1)$ linearly independent
% elements~$v_0, …, v_h; x_0, …, x_{h-1}$ such
% that~$(A - λ B) (∑ λ^i v_i) = 0$, $B x_i = A x_{i-1}$, and $B(x_0, v_0) = 1$.
% All that remains to do to find a factor of~$V$ isomorphic to~$K_h$
% is to find linear combinations~$w_i = x_i - ∑ a_{i,r} v_r$;
% such all vectors~$w_i$ are mutually orthogonal.
% Given that the only non-zero scalar products between the~$v_i$
% and the~$x_j$ are~$A(v_{i+1}, x_{i}) = B(v_i, x_i) = 1$,
% the relations for this are given by
% \begin{equation}\label{eq:w-orthogonal}
% a_{i,j} + a_{j,i} = B(x_i, x_j), \quad
% a_{i,j+1} + a_{j,i+1} = A(x_i, x_j) \quad (0 ≤ i, j ≤ h-1).
% \end{equation}
% The second equation may be replaced
% by~$a_{i,j} + a_{j-1,j+1} = A(x_i, x_{j-1})$ for~$1 ≤ j ≤ h$.
% This shows that all the coefficients~$(a_{i,j})$ are determined
% by the $(2h-1)$ coefficients~$a_{i,i}$ and~$a_{i,i+1}$,
% subject to the relations
% \begin{equation}\label{eq:w-orthogonal-diag}
% 2 a_{i,i} = B(x_i, x_i), \quad 2 a_{i,i+1} = A (x_i, x_i).
% \end{equation}
% If~$2 ≠ 0$ in~$k$, then these equations have unique solutions.
% If~$2 = 0$ and $A, B$ are both alternating,
% then these equations are always satisfied.
% In all cases, it is always possible to compute all coefficients~$a_{i,j}$,
% and hence the basis of a Kronecker module isomorphic to~$K_{h}$.
% Moreover, all the computations involved only linear algebra in~$V$,
% for a total computational cost of at most~$O(n^3)$ operations.%>>>
% % pre-ANTS%<<<
% Let~$B_∞, B_0$ be the matrices of the pencil
% and transform the concatenated~$n × (2n)$-matrix~$(B_{∞} \; B_0)$
% to the lower row echelon form
% \begin{equation}
% (B_{∞} \; B_0) \;=\; (⋆) · \mat{A_{∞} & 0\\ C & A_0},
% \end{equation}
% where $(⋆)$~is an invertible~$n × n$-matrix and
% $0$~is a $r × n$-block with $r$~being the largest possible value.
% This implies that the $n-r$~lines of~$A_0$ are linearly independent, and
% therefore that its columns have full rank~$n-r$; therefore, there exists
% a matrix~$F$ such that~$C = -A_0 F$. From this, we see that
% \begin{equation}
% B_{∞} x + B_0 y = 0 \;⇔ \; \begin{cases} A_{∞} x = 0\\ y ∈ Fx + \Ker A_0.
% \end{cases}
% \end{equation}
% In particular, the case~$x = 0$ tells us that $\Ker A_0 = \Ker B_0$.
% By using the \emph{upper} row echelon form, we likewise compute a matrix~$G$
% such that~$B_{∞} x = B_0 y$ implies~$x ∈ G y + \Ker B_{∞}$.
% 
% We define a \emph{chain} of length~$h$ as a solution~$(e_0,…,e_h)$ of
% the $h$ equations~$b_0(e_i) + b_{∞}(e_{i-1}) = 0$ for~$i = 1,…,h$
% and~$b_{∞}(e_h) = 0$.
% We define by induction a sequence~$(U_i)$ of vector spaces such that the
% $h$-chains are defined by the relations~$e_0 ∈ U_h$ and~$e_i ∈ F(e_{i-1})
% + U_{h-i}$.
% 
% The base case is that of chains of length~$0$, which are the
% elements of~$\Ker B_{∞}$. We define $U_0 = \Ker B_{∞}$.
% 
% A $(h+1)$-chain is a $(h+2)$-uple~$(e_0,…,e_{h+1})$ such that
% $(e_1,…,e_{h+1})$~is a $h$-chain and $b_{0} e_1 + b_{∞} e_0 = 0$.
% The first condition amounts to~$e_1 ∈ U_h$ and~$e_i = f(e_{i-1}) +
% U_{h-i}$ for all~$i ≥ 2$; the second one means that $e_0 ∈ G U_{h} + \Ker
% B_{∞}$. We define~$U_{h+1} = G U_h + \Ker B_{∞}$.
% 
% This allows us to compute minimal isotropic vectors of length~$h$ as
% satisfying the relations
% \begin{equation}\label{eq:m.i.v.-matrix}
% e_0 ∈ U_{h} ∩ \Ker B_0, \quad e_{i} ∈ F e_{i-1} + U_{h-i}.
% \end{equation}
% This determines the space of isotropic vectors of degree~$≤ h$ with
% total complexity~$O(n^3 (h+1))$; moreover, as this computation is
% triangular, it also gives the space of isotropic vectors of degree~$≤ h'$
% for all~$h' ≤ h$, so that we only need to perform one run of this
% algorithm over all the singular part of the pencil. Once we have isolated
% the minimal Kronecker module~$K$ of~$V$ in Step 2, we may then project
% this basis on the quotient~$V/K$ to directly obtain a (sorted) basis of
% the isotropic vectors of~$V/K$.
%%>>>
\subsection{Primary decomposition of regular bilinear pencils}
\label{ss:bil-regular}

Any regular bilinear pencil~$b_0 - λ b_∞$ is canonically isomorphic to
an orthogonal direct sum~\cite[Theorem 4.2]{inventiones1976waterhouse},
indexed over powers~$p(λ)^e$ of irreducible polynomials in~$k[λ]$,
of regular polar pencils over the local rings~$k[λ]/p(λ)^e$.
Moreover, if~$2 ≠ 0$, then all symmetric bilinear forms over this local ring
are congruent to one of the diagonal forms~$(1,…,1)$ or~$(1,…,1,δ)$,
where $δ$~is a prescribed non-square in the field~$k[λ]/p(λ)$.

Note that the proof of primary decomposition
in~\cite{inventiones1976waterhouse} again
only claims the result to hold when~$2 ≠ 0$; however,
that hypothesis is used only in two places:
in the Kronecker decomposition~\cite[Theorem 3.1]{inventiones1976waterhouse},
which we know by Proposition~\ref{prop:kronecker-decomposition} above
to be valid for alternating pencils when~$2 = 0$;
and in the reduction of quadratic forms over
local rings~\cite[Proposition~1.2]{inventiones1976waterhouse}.
% Therefore, the result~\cite[Theorem 4.2]{inventiones1976waterhouse},
For clarity, we state here a result covering all cases.

If $b = b_0 - λ b_∞$ is a regular bilinear pencil on~$V$,
its \emph{characteristic endomorphism} is~$c = b_∞^{-1} b_0$.
For any polynomial~$f ∈ k[λ]$,
we say that $b$~is \emph{free} over~$R = k[λ]/f(λ)$
if~$f(c) = 0$ and the action of~$R$ on~$V$,
with multiplication by~$λ$ given by~$c$,
makes~$V$ into a free $R$-module;
we then define the \emph{rank} of~$b$ as the rank of~$V$ over~$R$.

\begin{prop}\label{prop:primary}
Let~$b_0 - λ b_∞$ be a regular symmetric bilinear pencil on~$V = k^n$.
\begin{enumerate}
\item There exists a unique decomposition of~$V$ as
an orthogonal sum~$⨁ V_{p^e}$,
running over all powers~$p^e$ of (finite or infinite) places of~$k[λ]$,
such that $V_{p^e}$ is a free module over~$k[λ]/p(λ)^e$.
\item Assume that~$2 ≠ 0$ in~$k$.
Let~$p$ be an irreducible polynomial of degree~$d$ in~$k[λ]$,
and $e$~be an integer.
Write~$M_{p}$ for the companion matrix of~$p$ and
$T_p$~for a prescribed invertible matrix such that
both~$T_p$ and~$T_p M_p$ are symmetric.
Then $V_{p^e}$ is isomorphic to an orthogonal sum of pencils of
the following form, written as $e × e$~blocks of size~$d × d$:
\begin{equation*}
L_{p,e,u} \;=\; \mat{0&&-T_p u&T_p u (λ - M_p)\\
  &\siddots{-T_p u}&\siddots{-T_p u}&\\
  -T_p u&\siddots{-T_p u}&\\T_p u(λ-M_p)&&&0},
\end{equation*}
where $u$~is either the identity matrix,
or a prescribed non-square element of the field~$k[M_p]$,
with the extra condition that $u = 1$ for all but at most one summand.
\item There exists algorithms computing these decompositions
with at most~$O(n^3)$ operations in addition to those performed in
Proposition~\ref{prop:kronecker-decomposition}.
\end{enumerate}
\end{prop}

% By ``a free module over $k[λ]/p^e$'' in point~(i) above,
% we mean the following.
% If $p$~is a finite place, \emph{i.e.} an irreducible polynomial, then
% after restriction to~$V_{p^e}$: $B$~is a regular bilinear form;
% the endomorphism~$H = B^{-1} A$ satisfies the relation $p(H)^e = 0$;
% and $V_{p^e}$, seen as a $k[λ]/p(λ)^e$-module with
% multiplication by~$λ$ given by~$H$, is free.
In point~(i), following~\cite[§~4]{inventiones1976waterhouse},
we define the summand corresponding to the place at infinity%
\footnote{This could also be done in a way consistent with the finite places,
by considering the \emph{homogeneous} characteristic polynomial
$f(λ: μ) = \det (μ b_0 - λ b_∞)$.
However, using the inhomogeneous polynomial yields a simpler proof,
at the cost of this \emph{ad hoc} definition for the place at infinity.}
of~$k[λ]$ for the pencil~$b_0 - λ b_∞$ as the summand corresponding to
the place zero for the pencil~$b_∞ - λ b_0$.

An algorithm proving point~(iii)
is given in Appendix~\ref{ap:primary}.

\subsection{Bilinear and quadratic forms commuting with an algebra}
\label{ss:commute}
We state here some propositions about bilinear and quadratic forms
that are used in this work.
Let~$A → B$ be a ring morphism and $M$~be a $B$-module.
Then $M$~is also a $A$-module.
We say that a $A$-bilinear form~$b: M ⊗ M → A$ \emph{commutes with~$B$}
if, for any~$c ∈ B$, we have~$b(α x, y) = b(x, α y)$;
we say that a $A$-quadratic form commutes with~$B$ if its polar does.

Let~$b_0 - λ b_∞$ be a regular symmetric bilinear pencil,
and let~$c = b_∞^{-1} b_0$ be its characteristic endomorphism.
Since both $b_∞$ and~$b_0=b_∞ c$~are symmetric, for any~$x, y ∈ V$ we have
\begin{equation}
b_∞(x, c y) = b_0(x, y) = b_0(y, x) = b_∞(y, c x) = b_∞(c x, y).
\end{equation}
This implies that, for all~$α ∈ k[c]$, $b_∞(α x, y) = b_∞(x, α y)$.
Therefore, $b_∞$~commutes with~$k[c]$ in the previous sense.

\begin{prop}\label{prop:trace-ext}
Let~$K/k$ be a separable field extension,
and~$V$ be a finite-dimensional vector space over~$K$.

For any $k$-bilinear form~$b: V ⊗ V → k$ commuting with~$K$, there
exists a unique $K$-bilinear form~$b_K: V ⊗ V → K$ such that~$b =
\Tr_{K/k} \,∘ \,b_K$.
\end{prop}
\begin{proof}
By choosing a $K$-basis of~$V$ and noticing that
all coordinates of a bilinear form are themselves bilinear forms,
we may assume that~$V = K$.

In that case, the result is classical. We recall the proof here.
Let~$z$ be a primitive element of~$K$ and write $d = [K:k]$.
Since~$K/k$ is separable, the trace form is
non-degenerate~\cite[VI~5.2]{lang-algebra}
and there exists a unique element~$a ∈ K$ such that
$\Tr (a z^i) = b(1, z^i)$ for all~$i=0, …, d-1$.
We immadiately see that, for all~$x, y ∈ k$, $\Tr (a x y) = b(x, y)$.

\end{proof}

Let~$k$ be a field and $R$~be the local ring~$R = k[π]/π^e$.
Define the $k$-linear map~$τ: R → k$ by~$τ(∑ x_i π^i) = x_{e-1}$.
Then $(x, y) ↦ τ(xy)$ is a $k$-bilinear map on~$R$,
non-degenerate and commuting with~$R$.
(It is also a natural choice of an isomorphism
between $R$ and its dual $k$-vector space).

\begin{prop}\label{prop:trace-local}
For any $k$-bilinear form~$b$ on~$R^m × R^n$ commuting with~$R$,
there exists a unique $R$-bilinear form~$b_R: R^m × R^n → R$
such that~$b = τ ∘ b_R$.
\end{prop}
\begin{proof}
% (Note that we do not demand that $M$, $N$ be \emph{free} as
% $R$-modules.))
% By the structure theorem of modules over a principal ring,
% we have~$M = ⊕ R_{m_i}$ for some finite sequence of integers~$m_i$.
% If the result holds for modules~$(M', N)$ and~$(M'', N)$ then
% it also holds for~$(M' ⊕ M'', N)$.
% Therefore, using induction on the length of both modules,
% we only need to prove the case where~$M = R_m$ and~$N = R_n$ where~$m ≥ n$.
% In this case, since $b$~commutes with~$k[π]$,
% we see that for~$x = ∑ x_i π^i$, $y = ∑ y_i π^i$:
By taking coordinates we may assume~$m=n=1$.
For any~$x = ∑ x_i π^i$ and $y = ∑ y_i π^i$:
\begin{equation}
b(x,y) \;=\; ∑_{i,j} x_i y_j\: b(1, π^{i+j})
  \;=\; ∑_{i+j+r = m-1} x_i y_j\: b(1, π^{m-1-r}) π^r.
\end{equation}
Let~$a = ∑ b(1, π^{i}) π^{m-1-i}$. Since $b(1, π^{r}) = 0$ for all~$r ≥
n$, $a$~belongs to the ideal~$π^{m-n} R_m = \Hom_R (R_n, R_m)$, so that
the product~$a\,y$ is well-defined in~$R_m$. The bilinear form~$b_R$ is
finally the form defined by~$b_R(x,y) = a\:x y$.
\end{proof}

The unicity of~$b_R$ shows that both forms~$b$ and~$b_R$ are
simultaneously symmetric or antisymmetric.
However, when $k$~is a field of characteristic two
and $b$~is alternating, in general $b_R$~is not
(its diagonal coefficients~$a$ only verify~$τ(a x^2) = 0$,
which is equivalent to~$a_{e-2i-1} = 0$ for all~$i$).
On the other hand, if both $b(x,y)$ and~$b(π x, y)$ are alternating
then $b_R$~is also alternating.

\medskip
For quadratic forms in characteristic two,
the analog to~\ref{prop:trace-ext},
which generalizes a result already known
for cyclic pencils~\cite[Prop.~5]{MPG2013}, holds:
\begin{prop} \label{prop:trace-quad}
Let~$K$ be a finite separable extension of~$k$ and~$V$ be a $K$-vector
space. For any $k$-quadratic form~$q: V ⊗ V → k$ commuting with~$K$,
there exists a unique $K$-quadratic form~$q_K: V ⊗ V → K$ such that~$q =
\Tr_{K/k} \, ∘ \, q_K$.
\end{prop}
\begin{proof}
This needs proof only in characteristic two.
First assume that~$V = K$.
Let~$b$ be the polar form of~$q$.
By Proposition~\ref{prop:trace-ext},
there exists~$b_K ∈ K$ such that~$b(x,y) = \Tr_{K/k} (b_K xy)$;
in particular, since $b$~is alternating,
for all~$x$ we have~$\Tr_{K/k} (b_K x^2) = 0$ and therefore~$b_K = 0$.
Since the polar of~$q$ is zero, $q$~is additive
and, since $q(a x) = a^2 q(x)$, it is a semi-linear form.
Since the trace map is non-degenerate,
there exists~$q_K$ such that~$q(x) = \Tr_{K/k} (q_K x^2)$.

As for Prop.~\ref{prop:trace-ext}, the $n$-dimensional case directly follows by
taking coordinates. Here all diagonal entries correspond to quadratic
forms, and all others to bilinear forms; all of these commute with~$K$.
\end{proof}



\section{Fully singular quadratic pencils in characteristic two}
\label{S:quad-sing}
In this section and the following one, we assume that the field~$k$ has
characteristic two.
We write~$σ: x ↦ x^2$ for the absolute Frobenius automorphism of~$k$.

Let~$q$ be a quadratic form over a~$k$-vector space~$V$. Since $2 = 0$
in~$k$, the polarity equation shows that the associated polar form~$b$ is
an \emph{alternating} bilinear form; namely, it satisfies~$b(x,x) = 0$
for all~$x ∈ V$. Moreover, the polarity map is not a bijection from
quadratic forms to alternating bilinear forms; its kernel is the space of
\emph{$σ$-linear forms} on~$V$. This means that, if a basis of~$V$ is
chosen, then a quadratic form is determined by its polar (which is an
alternating bilinear form) and its diagonal coefficients (corresponding to a
$σ$-linear form).

The classification of section~\ref{s:bilinear} still applies to
the polar part of quadratic pencils.
To compute an isomorphism between two such pencils,
we write down an explicit description of the group of automorphisms
preserving this polar part,
and compute how these automorphisms act
on the diagonal coefficients of a quadratic pencil.
We conclude the proof by showing that the corresponding equations
may be solved in polynomial time.

This section solves the case of totally singular pencils;
regular pencils are studied in the next one.

\subsection{An intrinsic description of Kronecker modules}
We give an intrinsic construction of the Kronecker modules.
Except where indicated, all tensor products and duals are understood as
operations on $k$-vector spaces.
For any integer~$d ≥ 0$, let~$H_d$ be
the $d+1$-dimensional vector space of homogeneous polynomials
of degree~$d$ in the variables~$(x:y)$,
$\chk{H_d}$ be the vector space dual to~$H_d$,
and~$\chev{φ,f}: \chk{H_d} × H_d → k$ be the standard bilinear pairing.
(For consistency, we let~$H_d = 0$ when~$d < 0$).

For any $h ∈ H_m$, multiplication by~$h$ defines a linear map,
which we again write~$h: H_d → H_{m+d}$,
as well as a transposed map~$\chk{h}: \chk{H_{d+m}} → \chk{H_d}$.
This means that~$\chev{\chk{h} φ, f} = \chev{φ, hf}$ for all~$φ ∈
\chk{H_{d+m}}$ and~$f ∈ H_d$.
All the maps~$h$ and~$\chk{h}$ commute with each other.

The \emph{Kronecker module} of degree~$d$ is
the $2d+1$-dimensional vector space~$K_d = H_{d-1} ⊕ \chk{H_{d}}$,
equipped with the symmetric bilinear pencil~$(q_λ)$ such that,
for~$f, f' ∈ H_{d-1}$ and~$φ, φ' ∈ \chk{H_d}$:
\begin{equation}\label{eq:kronecker-bilinear}
q_λ (f, f') \;=\; q_λ (φ, φ') \;=\; 0; \qquad
q_λ (f, φ) \;=\; \chev {φ, (λ y - x) f}.
\end{equation}

% The next proposition shows that multiplication by polynomials essentially
% defines all homomorphisms between the bilinear spaces~$K_d$.
% As in Subsection~\ref{SS:bil-reg-local},
% we write~$f ≻ g$ for the relation~$b_{∞} f + b_0 g = 0$.
We define a relation~$≻$ on~$K_{d}$ by: $u ≻ v$ if $B u = A v$.
In particular, for all~$f, g ∈ H_{d-1}$ and~$φ, ψ ∈ \chk{H_d}$,
\begin{equation}\label{eq:chain-Kd}
f ≻ g \;\text{ iff }\; y f = x g; \quad
φ ≻ ψ \;\text{ iff }\; \chk{y} φ = \chk{x} ψ.
\end{equation}
\begin{prop}\label{prop:end-Kd}
For any integers~$d, d'$, the linear maps from~$K_d$ to~$K_{d'}$
preserving the relation~$≻$ are the maps of the form
\begin{equation*}
\begin{array}{lclclcl}H_{d-1} &⊕& \chk{H_d} &→&H_{d'-1} &⊕& \chk{H_{d'}}\\
(f,&& φ) & ↦ & (u f ,&& \chk{v} φ + \chk{f} w)
\end{array},
\end{equation*}
where $u ∈ H_{d'-d}$, $v ∈ H_{d-d'}$, and~$w ∈ \chk{H_{d+d'-1}}$.
\end{prop}
\begin{proof}
(This proof is independent of the characteristic.)
Since we never have~$a ≻ b$ for~$a ∈ H_{d-1}$ and~$b ∈ \chk{H_{d}}$,
a map~$F: K_d → K_{d'}$ is $≻$-preserving
iff each of the four induced maps~$H_{d-1} → H_{d'-1}$, etc.
is $≻$-preserving.

Let~$(x^{i} y^{d-1-i})$ be a basis of~$H_{d-1}$
and write~$ξ_{j,d-j}$ for the dual basis of~$\chk{H_d}$.
We then have the relations
\begin{equation}\label{eq:chain-Kd-zero}
0 ≻ ξ_{0,d} ≻ ξ_{1,d-1} ≻ … ≻ ξ_{d,0} ≻ 0;
\end{equation}
on the other hand, by~\eqref{eq:chain-Kd},
for any chain~$0 ≻ f_0 ≻ … ≻ f_{n} ≻ 0$ in~$H_d$,
we have~$f_0 = … = f_n = 0$.
This proves that there is no non-zero $≻$-preserving map
$g: \chk{H_d} → H_{d'-1}$.

Finally, by observation~\eqref{eq:chain-Kd},
each of the remaining three maps has the required form.
% 
% We first prove that any $≻$-map~$g: \chk{H_{d}} → H_{d'-1}$ is zero.
% By relation~\eqref{eq:chain-Kd-zero}, we have
% \begin{equation}
% 0 ≻ g(ξ_{
% \end{equation}
% Let~$F: K_{d} → K_{d'}$ be a $≻$-homomorphism.
% For~$j = 0, …, d$, let~$g_j$ be
% the projection to~$H_{d'-1}$ of~$F(ξ_{j, d-j})$.
% Applying~$F$ to the relation~\eqref{eq:chain-Kd-zero}, we see that
% \begin{equation}
% 0 ≻ g_0 ≻ g_1 ≻ … ≻ g_d ≻ 0.
% \end{equation}
% This and~\eqref{eq:chain-Kd} imply that~$g_j = 0$ for all~$j$.
% From this we deduce that $F(\chk{H_d}) ⊂ \chk{H_{d'}}$.
% Let~$v_j = \chev{F(ξ_{j,d-j}), y^{d'}}$ and~$v = ∑ v_j x^j y^{d-d'-j}$.
% By~\eqref{eq:chain-Kd-zero},
% we see that $v_j = \chev{F(ξ_{0,d}), x^{j} y^{d'-j}}$,
% so that~$F(ξ_{0,d}) = ∑ v_j ξ_{j,d'-j} = \chk{v} ξ_{0,d}$.
% Applying~\eqref{eq:chain-Kd-zero} once more,
% we deduce from this that $F(ξ_{j,d-j}) = \chk{v} ξ_{j,d-j}$ for all~$j$,
% and therefore~$F(φ) = \chk{v} φ$ for all~$φ ∈ \chk{H_{d'}}$.
\end{proof}
\subsection{Kronecker modules with coefficients}


Let~$E = k^{n}$ equipped with its diagonal scalar product.
Then $E ⊗ K_d = K_d^n$ is a bilinear space in a natural way.
% $(x, y) ↦ x · y = ∑ x_i y_i$;
% For any linear maps~$α: V → E$, $β: W → E$,
% we write~$α · β$ for the bilinear form on~$V × W$
% defined by~$(α · β) (x, y) = (α(x) · β(y))$.
The multiplication maps for homogeneous polynomials extends as
a natural map on~$E ⊗ H_m$ on~$H_d$ and~$\chk{H_d}$,
defined for~$a ∈ E, h ∈ H_m$ and~$f ∈ H_d$, $φ ∈ \chk{H_d}$ by
\begin{equation}
(a ⊗ h) f = a ⊗ (h f) \;∈ E ⊗ H_{d+m} \quad\text{and}\quad
(a ⊗ h) φ = a ⊗ (\chk{h} φ) \;∈ E ⊗ \chk{H_{d-m}}.
\end{equation}
Likewise, for~$u ∈ \Hom(E, E')$, $f ∈ H_d$, $φ ∈ \chk{H_d}$,
and $h ∈ H_m$, $ψ ∈ \chk{H_m}$, we define
\begin{equation}
\begin{array}{rcll}
(u ⊗ h) (a ⊗ f) &=& u(a) ⊗ (hf) &∈ E' ⊗ H_{d+m},\\\
\chk{(u ⊗ h)} (a ⊗ φ) &=& u(a) ⊗ (\chk{h} φ) &∈ E' ⊗ \chk{H_{d-m}},\\
(u ⊗ ψ) \chk{(a ⊗ f)} &=& u(a) ⊗ (\chk{f} ψ) &∈ E' ⊗ \chk{H_{m-d}}.
\end{array}
\end{equation}
% \subsection{Automorphisms of a direct sum of Kronecker modules}%<<<2

We now consider a totally irregular pencil of bilinear forms,
isomorphic to the orthogonal sum~$⨁ K_d^{n_d} = ⨁ E_d ⊗ K_d$
for a unique finite sequence of integers~$(n_d)$,
where we write~$E_d = k^{n_d}$.

\begin{prop}\label{prop:aut-Ed-Kd}
The automorphisms of~$⨁ E_d ⊗ K_d$ are exactly the maps of the form
\begin{equation}\label{eq:aut-Ed-Kd}
a ⊗ f ↦ ∑_{d' ≥ d} u_{d',d} (a ⊗ f) + ∑_{d'} w_{d',d} \chk{(a ⊗ f)},
\quad a ⊗ φ ↦  ∑_{d' ≤ d} \chk{v_{d',d}} (a ⊗ φ),
\end{equation}
where~$u_{d',d} ∈ \Hom (E_d, E_{d'}) ⊗ H_{d'-d}$, $v_{d',d} ∈ \Hom (E_d,
E_{d'}) ⊗ H_{d-d'}$ and~$w_{d',d} ∈ \Hom (E_{d}, E_{d'}) ⊗
\chk{H_{d+d'-1}}$ satisfy the following relations: let~$U, V, W$ be the
matrices~$(u_{d',d})$, $(v_{d',d})$, and~$(w_{d',d})$; then
\begin{equation}\label{eq:aut-Ed-Kd-ABC}
\transpose{V} · U = 1, \quad\text{and}\quad
\transpose{W} · U + \transpose{U} · W = 0.
\end{equation}
\end{prop}

In the above proposition, we understand the elements~$a ⊗ f$ and~$a ⊗ φ$ to
belong to the spaces~$E_d ⊗ H_{d-1}$ and~$E_d ⊗ \chk{H_d}$.
For~$d > d'$, the space~$H_{d' - d}$ is zero,
and therefore~$u_{d,d'} = v_{d',d} = 0$.
The relation~$\transpose{U} · V = 1$ means that, for all~$d, d'$,
$∑_i \transpose{u_{i,d}} · v_{i,d'} ∈ \Hom (E_{d'}, E_d) ⊗ H_{d'-d}$
is the identity of~$E_d$ if $d = d'$ and~$0$ else.
% this product is to be interpreted as
% the collection of the corresponding terms of all degrees in~$(x:y)$,
% and the scalar product is taken in~$E_i$.
Therefore, the elements~$u_{i,j}$ uniquely determine all of the~$v_{i,j}$.
Likewise, the relation~$\transpose{U} · W + \transpose{W} · V = 0$
means that $∑_i \transpose{u_{i,d}} · w_{i,d'} +
\transpose{w_{i,d}} · u_{i,d'} = 0 ∈ \Hom (E_{d'}, E_d) ⊗ \chk{H_{d+d'-1}}$.


\begin{proof}[\proofof Prop.~\ref{prop:aut-Ed-Kd}]
Let~$F$ be an orthogonal automorphism of~$V = ⨁ E_d ⊗ K_d$.
For any basis of the coefficient spaces~$E_d$,
the restrictions of~$F$ to maps~$K_d → K_{d'}$
are $≻$-preserving in the sense of~\ref{prop:end-Kd}.
This shows that $F$~is of the form given in~\eqref{eq:aut-Ed-Kd}.

Let now $F$~be any linear map defined as in~\eqref{eq:aut-Ed-Kd}.
Writing down the expansion of~$(b_0 - λ b_∞) (F(a ⊗ f), F(b ⊗ φ))$,
straightforward linear algebra shows that $F$~is orthogonal if, and only if,
its coefficients~$u_{d',d}$, $v_{d',d}$ and~$w_{d',d}$
satisfy the relations~\eqref{eq:aut-Ed-Kd-ABC}.
\end{proof}

\subsection{Action on the diagonal coefficients}
We now assume that the characteristic of the base field is~two,
and write~$σ: x ↦ x^2$ for the Frobenius automorphism.
We now consider a pencil of quadratic forms~$q = (q_{λ})$
whose polar~$b = (b_{λ})$ is the totally irregular pencil~$⨁ E_d ⊗ K_d$;
let~$F$ be an automorphism of this polar form and~$q' = q ∘ F$.
Keeping the notations of Proposition~\ref{prop:aut-Ed-Kd},
we then have, for all~$a ∈ E_d, f ∈ H_{d-1}, φ ∈ \chk{H_d}$:
\begin{equation}\begin{split}\label{eq:act-on-diag}
q_{λ} (F (a ⊗ f))
  &= ∑_{i ≥ d} q(u_{i,d} (a) f) + ∑_{i} q(w_{i,d} (f a))
  + ∑_{i} b(w_{i,d} (a), u_{i,d} (a) f^2);\\
q_{λ} (F (a ⊗ φ))
  &= ∑_{i ≤ d} q(v_{i,d} (a) φ).
\end{split}\end{equation}
Solving the IP1S problem means computing the values~$u_{d,d'}$,
$v_{d,d'}$ and~$w_{d,d'}$ as defined in Prop.~\ref{prop:aut-Ed-Kd}.
In view of the relation~$\transpose{C} · A + \transpose{A} · C = 0$
of this proposition,
we replace the unknowns~$w_{d',d}$
by~$z_{d',d} = ∑_i \transpose{u_{i,d}} w_{i,d'}$;
then $z_{d',d}  ∈ \Hom (E_d, E_{d'}) ⊗ \chk{H_{d+d'-1}}$
and the anti-symmetry condition is $\transpose{z_{d,d'}} = z_{d',d}$.
We note that the transformation~$F$ is fully determined
by the coefficients~$u$ and~$z$, which we choose as our unknowns.
% We decompose $w_{d',d} ∈ \Hom(E_d, E_{d'}) ⊗ \chk{H_{d+d'-1}}$
% as~$w_{d', d} = ∑ w_{d',d,j}\, ξ_{j,d+d'-1-j}$
% for~$w_{d',d,j} ∈ \Hom (E_d, E_{d'})$.
% The coefficients~$w'_{d',d}$ are then given by
% $w'_{d',d,j} = ∑_{i,r} \transpose{u_{i,d,r}} · w_{i,d',r+j}$.

With its polar form known,
the quadratic pencil is determined by its diagonal coefficients.
Let~$ψ_{d}, ω_d$ be the restrictions of~$σ^{-1} ∘ q$
to~$E_d ⊗ H_{d-1}$ and~$E_d ⊗ \chk{H_d}$.
these are pencils of $k$-linear forms and they determine~$q$.
% We likewise define~$ψ'_d, ω'_d$ as the diagonal coefficients of~$q'$.
% 
% Let~$(ξ_{i,d-i})$ be the basis of~$\chk{H_d}$ dual to
% the basis~$(x^i y^{n-i})$ of~$H_D$,
% and decompose~$w_{d,d'}$ in this basis as~$∑_{i,j} w_{d,d',j} ξ_{j,d+d'-1-j}$,
% where~$w_{d,d',j} ∈ \Hom (E_d, E_{d'})$.
By~\eqref{eq:act-on-diag},
the diagonal coefficients~$ψ'_d, ω'_d$ of~$q'$ are:
\begin{equation}\begin{split}
ψ'_d &= ∑_i ψ_i ∘ u_{i,d} + ∑_i ω_i ∘ w_{i,d}
  + ∑_{i,j} σ^{-1} (z_{d,d,2j+1} - λ z_{d,d,2j}) ξ_{j,d-j},\\
ω'_d &= ∑_i ω_i ∘ v_{i,d}.
\end{split}\end{equation}

Since there are~$O(n^2)$ unknowns in total,
by performing linear algebra of dimension~$O(n^2)$
we obtain the following result.

\begin{prop}\label{prop:ip1s-semilinear}
The $n$-dimensional IP1S problem for totally irregular pencils
over a field of characteristic two is equivalent to
a semi-linear equation of the form
\begin{equation}\label{eq:semilinear}
X = A σ(X) + B,
\end{equation}
where $A$~is a square matrix and $X, B$~are column matrices of
dimension~$O(n^2)$.
\end{prop}

\subsection{Solving semi-linear equations}

As the matrix~$A$ of Proposition~\ref{prop:ip1s-semilinear}
empirically seems to be of general type,
we solve equation~\eqref{eq:semilinear} by a generic method.
In the IP1S problem, the base field~$k$ has characteristic~two; we
present here the general case for any (perfect) base field.

Let~$k[φ]$ be the non-commutative ring of polynomials in~$φ$,
with the relations~$φ c = σ(c) φ$ for all~$c ∈ k$. This ring is Euclidean.
More precisely, the (left-side) Euclidean algorithm works:
given two elements~$a, b ∈ k[φ]$, there exist elements~$u, v$
such that~$u a + v b = d$ where $d$~is the gcd of~$a$ and~$b$.
Moreover, the only two-sided ideals of~$k[φ]$
are those generated by the powers of~$φ$.
From these two remarks and \cite[Ch.~3, Th.~19]{jacobson1943rings} we get
the following\footnote{%
This proposition is also the reduction modulo~$p$ of
the Dieudonné-Manin reduction given by the Newton polygon
over the ring of Witt vectors~$W(k)$.}.
\begin{prop}
Let~$φ: k^n → k^n$ be a semi-linear endomorphism. There exists a basis
of~$k^n$ in which the matrix of~$φ$ is the direct sum of cyclic matrices.
% at most one of which is not nilpotent.
\end{prop}

Assume now that $A$~is cyclic and let~$R = k[a]/f(a)$ be the $k$-algebra
generated by~$a$; the equation of Prop.~\eqref{prop:ip1s-semilinear} may
then be written as
\begin{equation}\label{eq:semi-linear-pol}
x = a σ(x) + b,
\end{equation}
where~$a$, $b$ and~$x$ belong to the finite algebra~$k[a]$, and $σ$~is
the absolute Frobenius automorphism. To the primary factorization~$f = ∏
f_i$ of~$f$, there corresponds a factorization~$R = ∏ R_i$ where $R_i$~is
a local algebra. Using Chinese remainders, we may therefore assume that
$R$~is a local algebra and~$f = f_0^d$, where $f_0$~is irreducible.

We first see to the case where~$d = 1$, \emph{i.e.} $R$~is an extension
of the field~$k$. Let~$k_0 = \F_p$ be the field fixed by the
Frobenius~$σ$ and $N_0 = N_{R/k_0}$ and~$\Tr_0 = \Tr_{R/k_0}$ be the
norm and trace operators. Equation~\eqref{eq:semi-linear-pol} implies
that
\begin{equation}
x = b' + N_0(a) x, \quad\text{where $b' = b + a σ(b) + … + a σ(a) …
σ^{n-2}(a) σ^{n-1}(b)$.}
\end{equation}
If $N_0(a) ≠ 1$, then this gives as a unique solution~$x =
b'/(1-N_0(a))$. If, on the contrary, $N_0(a) = 1$, then by
Hilbert's theorem~90~\cite[VI.6.1]{lang-algebra3},
there exists~$u ∈ R^{×}$ such that~$a = σ(u)/u$;
then~$x' = ux$ satisfies the equation~$x' = σ(x') + ub$.
By the additive form of Hilbert's theorem~90 \cite[VI.6.3]{lang-algebra3},
this last equation, has a solution if, and only if, $\Tr_0 (ub) = 0$.
We note that both forms of Hilbert's theorem are algorithmic,
with a complexity dominated by linear algebra.

In the general case where~$d ≥ 1$, let~$\fr m$ be the maximal ideal
of~$R$. We may use the preceding paragraph to compute a solution~$x_0$ of
the equation modulo~$\fr m$. Moreover, we notice that~$f(x) = x -  a σ(x)
- b$ is a polynomial and that~$f'(x) = 1$; therefore, this polynomial is
separated, and we may use Hensel's lemma to lift the approximate
solution~$x_0$ to a full solution.

\medskip
Since equation~\eqref{eq:semilinear} has dimension~$O(n^2)$,
the linear algebra involved in solving this by this method
has a time complexity bounded by~$O(n^{2ω})$.

%>>>1
\section{Regular quadratic pencils in characteristic two}
\label{S:quad-reg}
\subsection{The action of orthogonal maps on quadratic forms}

In this subsection we compute the action of linear maps
preserving the polar of a quadratic pencil~$q$
on the diagonal coefficients of~$q$.

Here $k$~is a finite field of characteristic two
and $R$~is the local ring~$R = k[π]/π^e$.
We equip the ring~$R$ with the Frobenius and Verschiebung endomorphisms,
defined by~$σ(∑ x_i π^i) = ∑ x_i^2 π^i$ and~$V(∑ x_i π^i) = ∑ x_i π^{2i}$.
This implies that, for all~$y ∈ R$, $V σ(y) = σ V(y) = y^2$;
moreover, we have~$R = V(R) ⊕ π V(R)$,
and $V(R)$~is also the subset of squares in~$R$.

We say that an element~$c ∈ R$
is \emph{$τ$-alternating} if $τ(c x^2) = 0$ for any~$x ∈ R$.

\begin{lem}\label{lem:gamma-polar}
Let~$γ: R → R$ be the application defined, for~$x = V(u) + π V(v)$,
by~$γ(x) = π V(u v)$. Then, for all~$x,y ∈ R$, we have
\begin{enumerate}
\item $γ(x y) = γ(x) y^2 + x^2 γ(y)$;
\item $γ(x+y) = γ(x) + γ(y) + x y + V(α)$ for some~$α ∈ R$;
\item For any $τ$-alternating~$c ∈ R$,
$τ(c γ (x))$~is a $k$-quadratic form on~$R$ with polar~$τ(c x y)$.
\end{enumerate}
\end{lem}
\begin{proof}
(i)~Write~$x = V(u) + π V(v)$ and~$y = V(w) + π V(z)$. Noticing
that~$σ(x) = u^2 + π v^2$, we then have
\begin{equation}\label{eq:gamma-prod}
\begin{split}
γ(x y) &= π V\pa{(uw + π vz)(vw+uz)}\\
 &= π V\pa{u v (w^2 + π z^2)} + π V \pa{(u^2+π v^2) wz}\\
 &= γ(x) V(σ y) \;+\; V( σx) γ(y) \quad = γ(x) y^2 + x^2 γ(y).
\end{split}
\end{equation}

(ii) follows from
$γ(x+y) - γ(x) - γ(y) = π V(uz + vw) = xy - V(uw+πvz)$.

(iii)~is a direct consequence of~(i) and~(ii).
\end{proof}
\begin{prop}\label{prop:quad-tau}
Let~$q$ be a $k$-quadratic form on~$R^m$ commuting with~$R$,
$b$~its polar form, and $b_R$ be the unique $R$-quadratic form
such that~$b = τ ∘ b_R$;
write~$b_{i,j}$ for the coefficients of~$b_R$.
Then there exists a unique $σ$-linear form~$a: R^m → R$ such that,
for all~$x = (x_i) ∈ R^m$,
\begin{equation}
q(x) \;=\; τ\pa{a(x) + ∑_{i} b_{i,i} γ(x_i) + ∑_{i < j} b_{i,j} x_i x_j}.
\end{equation}
\end{prop}
The $σ$-linear form~$a$ is called the \emph{diagonal form} of~$q$;
if $a(x_1, …,x_m)=∑ a_i σ(x_i)$, then we write~$a=(a_i)$.
\begin{proof}
Since $b$~is the polar form of~$q$, it is alternating,
and therefore the diagonal coefficients of~$b_R$ are $τ$-alternating.
By Lemma~\ref{lem:gamma-polar},
% $τ(c γ(x))$~is a quadratic form on~$R$ with polar~$τ(c\, xy)$.
% It follows by linearity that
$q' = τ(∑ b_{i,i} γ(x_i) + ∑ b_{i,j} x_i x_j)$~is a $k$-quadratic form
which has the same polar as~$q$,
so that the difference~$q - q'$ is a $σ$-linear form.
\end{proof}

Since the bilinear form~$τ(x y)$ is regular on~$R$, the $k$-linear
map~$V: R → R$ has an adjoint~$θ$, such that~$τ(x\, V(y)) = τ(θ(x)\, y)$.
This map is defined by~$θ(π^{ℓ-1-2i}) = π^{ℓ-1-i}$ and~$θ(π^{ℓ-2i}) = 0$.

When computing the effect of a $R$-linear change of variable on a
$k$-quadratic form commuting with~$R$, we obtain the following result.

\begin{prop}\label{prop:quad-changevar}
Let~$q$ be a $k$-quadratic form on~$R^m$, commuting with~$R$;
let~$b$ be the polar form of~$q$, and~$a = (a_i)$ be its diagonal form.
For any $R$-linear map~$u: R^n → R^m$,
the polar form~$b'$ and the diagonal form~$a' = (a'_i)$ of~$q' = q ∘ u$ are
\begin{equation*}
b' = b ∘ u, \quad
a'_i \;=\; ∑_r a_r σ(u_{r,i})
  + θ \pa{ ∑_r b_{r,r} γ(u_{r,i}) + ∑_{r < s} b_{r,s} u_{r,i} u_{s,i} }.
\end{equation*}
\end{prop}

The \emph{hyperbolic plane} is the module $R^2$, equipped with the
$k$-quadratic form $q(x_1, x_2) = τ(x_1 x_2)$; this form commutes with~$R$.
The corresponding $τ$-alternating bilinear form~$b_R$
has the matrix~$\smat{0&1\\1&0}$.
A quadratic form is \emph{hyperbolic} if it is isomorphic to
the orthogonal sum of a number of copies of the hyperbolic plane.
We say that a quadratic form~$q$ \emph{reduces} to a form~$q'$
if $q$~is isomorphic to the direct sum of~$q'$ and a hyperbolic form.%
\footnote{Witt's cancellation theorem,
despite not being true in characteristic two for \emph{bilinear} forms,
is valid for regular
\emph{quadratic} forms~\cite[Appendix 1]{milnorhusemoller} over a field.
The proof~\cite[I.4.1]{spinors} also applies to local rings.
Therefore, our definition of reduction coincides with Witt equivalence.}%

\begin{prop}\label{prop:witt-four}
Let~$q$~be a $k$-quadratic form on~$R^m$, commuting with~$R$.
If the polar form of~$q$~is hyperbolic,
then $q$~reduces to a quadratic form of dimension at most two.
\end{prop}
\begin{proof}
Since the polar of~$q$ is hyperbolic, by Proposition~\ref{prop:quad-tau}
there exist some coefficients~$a_1, …, a_{r}; a'_1, …, a'_{r} ∈ R$
such that $q$~is isomorphic to the form
$q' = [a_1, …, a'_r]$ defined on~$R^{2m}$ by
\begin{equation}
q' (x_1, …, x_r, x'_1, …, x'_{r}) \;=\;
  τ\pa{∑_{i ≤ r} a_i σ(x_i) + a'_i σ(x'_i) + x^{}_i x'_i}.
%   τ(∑_{i ≤ 2m} a_i σ(x_i) + ∑_{i ≤ m} γ(x_{i} x_{i+m})).
\end{equation}
To prove the proposition, we show that
any form~$q = [a_1, a_2; a'_1, a'_2]$ is isomorphic to
a form~$[b, 0; b', 0]$ for some~$b, b' ∈ R$.
The polar of~$q$ is the standard hyperbolic form on~$R^4$,
% \begin{equation}
% H_4 = \mat{0&1&0&0\\-1&0&0&0\\0&0&0&1\\0&0&-1&0}.
% \end{equation}
% The automorphism group of~$H_4$
and its automorphism group~$\mathrm{Sp}_4(R)$
contains the following transformations,
with the corresponding effect on the values~$(a_i)$:
\begin{equation}\begin{array}{ll}
\mat{ & & 1 &\\ &&&1\\ 1&&&\\ &1&&} &
\begin{cases}a_1 \leftrightarrow a'_1\\
  a_2 \leftrightarrow a'_2\\\end{cases} \\
\mat{M & 0\\ 0 & \transpose{M}^{-1}}, M ∈ \GL_2(R) &
\begin{cases} (a_1, a_2) ← (a_1, a_2) · σ(M)\\
(a'_1, a'_2) ← (a'_1, a'_2) · σ(\transpose{M}^{-1}) \end{cases}\\
\mat{1&&u\\&1&&v\\ &&1&\\ &&&1} &
\begin{cases} a'_1 ← a'_1 + a_1 \, σ(u) \,+\, θ(u) \\
a'_2 ← a'_2 + a_2 \, σ(u) \,+\, θ(v)\end{cases}\\
\mat{1&&&w\\&1&w&\\ &&1&\\ &&&1} &
\begin{cases} a'_1 ← a'_1 + a_2 \, σ(w) \\
a'_2 ← a'_2 + a_1 \, σ(w) \end{cases}
\end{array}\end{equation}
Using the first transformation, we may assume that
the ideal~$(a_1, a_2)$ of~$R$ contains~$(a'_1, a'_2)$.
Using the second one, we may assume that $a_2 = 0$,
so that $a_1$~divides $a'_1$ and~$a'_2$.
Finally, using the last transformation, one may have~$a'_2 = 0$.
\end{proof}
\subsection{Reduction to the hyperbolic case}

\begin{prop}\label{prop:ip1s-bin-polynomial}
Let~$k$ be a finite field of characteristic two.
There exists a polynomial algorithm computing a linear isomorphism between
two equivalent regular quadratic pencils over~$k$.
\end{prop}
\begin{proof}
By Propositions~\ref{prop:primary}~(i) and~\ref{prop:trace-quad},
any regular quadratic pencil~$q$ over~$k^n$
splits canonically as an orthogonal sum of primary components~$q_i$,
where $q_i$~is defined on a finite extension~$K_i$ of~$k$
and defines a free module of rank~$m_i$ over the ring~$R_i = K[π]/π^{e_i}$;
moreover, $n = ∑ [K_i:k] · m_i · e_i$.

Since this decomposition is unique,
computing an isomorphism between two regular pencils is the same as
computing isomorphisms between all of their primary components.
Therefore we assume that $q$, $q'$ both are
regular pencils, defined over~$K$, and free of rank~$m$ over~$R=K[π]/π^e$.

Let~$b = b_0 - λ b_∞$ be the polar pencil of~$q$.
Since both $b_{∞}$ and~$b_{0} = π b_{∞}$ are alternating,
$b_{∞,R}$ is again alternating.
Therefore, $b_{∞, R}$ is hyperbolic~\cite[I.(3.5)]{milnorhusemoller}.
The $k$-automorphisms of the polar pencil~$b_0 - λ b_{∞}$
are exactly the $R$-automorphisms of the alternating form~$b_{∞,R}$,
\emph{i.e.} the elements of~$\mathrm{Sp}_{m} (R)$.

Using Proposition~\ref{prop:witt-four} for the form~$q_{∞}$,
we may assume that $q_{∞}$~is of the form $[a, 0, …, 0; a', 0, …, 0]$,
as defined in the proof of Proposition~\ref{prop:witt-four}.
Using Proposition~\ref{prop:witt-four} again for the restriction of~$q_{0}$
to $m-2$~coordinates, we may further assume that
$q_{0}$~is of the form~$[b, c, 0, …, 0; b', c', 0, …, 0]$.
This shows that the pencil~$(q_{λ})$ is isomorphic to
the direct sum of a pencil of $R$-rank at most~$4$
and a hyperbolic pencil.
The same applies to~$(q'_{λ})$.
Since both hyperbolic parts are isomorphic,
we only need to compute the isomorphism for pencils for which~$m ≤ 4$.

\bigskip

We conclude by proving the result for quadratic pencils for
which~$m=4$: in this case, we may write the form~$q_∞$ as
\begin{equation}
q_∞(x_1, …, x_4) = τ (∑_{i} a_i σ(x_i) + x_1 x_3 + x_2 x_4)
\end{equation}
and likewise, let~$(a'_i)$ be the diagonal form of~$q'_∞$.
An isomorphism~$u$ between~$q_∞$ and~$q'_∞$ preserving
the hyperbolic bilinear forms~$b_R, b'_R$ is given by coefficients~$u_{i,j}$
satisfying the equations of Proposition~\ref{prop:quad-changevar}.
For any~$u = V(v) + π V(w)$, $u' = V(v') + π V(w') ∈ R$, we have
\begin{equation}\begin{split}
σ (u) &= v^2 + π w^2, \quad\qquad
θ(a γ (u)) = v\, w\, θ(π a),
\quad\text{and}\\
θ(a u u') &= (v v' + π w w') θ(a) + (v w' + w v') θ(π a),
\end{split}\end{equation}
so that the equations from Proposition~\ref{prop:quad-changevar}
in the 16 variables~$u_{i,j}$ are equivalent to
the following polynomial equations
in the 32 variables~$v_{i,j}$ and~$w_{i,j}$:
\begin{equation}\begin{split}\label{eq:ip1s-polynomial}
σ (b_{i,j}) &= ∑_{r,s} σ (b_{r,s})\: (v_{r,i}^2 + π w_{r,i}^2)\:
  (v_{s,j}^2 + π v_{s,j}^2),\\
a'_{i} &= ∑_{r} a_{r} (v_{r,i}^2 + π w_{r,i}^2)
  + ∑_{r < s} (v_{r,i} v_{s,i} + π w_{r,i} w_{s,i}) θ (b_{r,s})\\
  &\hphantom{=} + (v_{r,i} w_{s,i} + w_{r,i} v_{s,i}) θ (π b_{r,s}).
\end{split}\end{equation}
We obtain a similar set of equations for the forms~$q_0, q'_0$.

This shows that the IP1S problem is equivalent to
a bounded number of polynomial equations
in a bounded number of variables in the ring~$R = K[π] /π^{e}$
(more precisely, it is enough
to determine~$v_{i,j}$ up to precision~$\floor{e/2}$
and~$w_{i,j}$ up to precision $\floor{(e-1)/2}$).
Since $R$~is a discrete valuation ring,
linear equations are solvable in~$R$
in the sense of~\cite[4.1.5]{adams1994grobner};
solving such a linear equation requires only $K$-linear algebra in~$R$,
with a cost of~$O((de)^ω)$ operations in~$k$.
Therefore, it is possible to compute a Gröbner basis of
the ideal generated by the equations~\ref{eq:ip1s-polynomial}
in~$R[v_{i,j}, w_{i,j}]$.
Computing this basis is possible with a number of ring operations
polynomial in the degree of the equations
and doubly exponential in the number of variables~\cite{dube1990grobner}.

In our case, since both the number of variables
and the degree of the equations are constant,
this number is constant (but huge: roughly $2^{2^{32}}$).
The only dependency in~$n$ is in the cost of a ring operation,
which is~$O((de)^ω)$ as noted above.
Taking all the invariant factors of the pencil into account,
the total complexity for this algorithm is~$O(n^ω)$.
\end{proof}

% \subsection{Solving the equations}%<<<2
% We now describe a method for computing a linear isomorphism~$X$ between
% two quadratic pencils on a free $R$-module~$M$.
% The coefficients~$x_{i,j}$ of~$X$ must satisfy the equations given by
% Prop.~\ref{prop:quad-changevar}.
% Writing~$x = V(y) + π V(z)$, we have
% \begin{equation}
% σ (x) = y^2 + π z^2, \qquad
% θ(a x x') = (y y' + π z z') θ(a) + (y z' + z y') θ(π a),
% \quad\text{and}\quad
% θ(a γ (x)) = y\, z\, θ(a π)
% \end{equation}
% so that the four~equations for the coefficients~$a_{i}$, together with
% the 12~equations for the symplectic group~$\mathrm{Sp}(4)$, are
% equivalent to 16~quadratic equations in the 32~variables~$y_{i,j}$
% and~$z_{i,j}$.
% 
% We now explain how to solve a system of~$M$ equations of degree~$D$ in
% $N$~variables in~$R = R_{ℓ} = k[π]/π^{ℓ}$, where $M, N$~and~$D$ are
% constants. Let~$\acco{f_i (x_j)}$ be such a system; for any multi-index~$α ∈
% [0,D]^{M}$, we write~$f_{i, α}$ for the coefficient of~$x^{α}$ in~$f_i$.
% For any element~$x = ∑ x_i π^i ∈ R$ with $π$-adic valuation~$n = v_R
% (x)$, we define the \emph{principal part} of~$x$ as~$x_n π^n$.
% 
% The \emph{Newton polytope}~$\ro N f_j$ associated to~$f_j$ is the convex
% hull of the function~$[0,D]^{M} → [0, +∞], α ↦ v_R (f_{j, α})$.
% It is a convex, piece-wise affine function, and the solutions of~$f_{j,
% α} = 0$ correspond to the ridges of the Newton polytope, \emph{i.e.} the
% locus of non-differentiability of~$\ro N f_j$. Any solution~$(x_i)$ of
% the whole system~$f_1 = … = f_{N} = 0$ is such that the exponent
% vector~$(e_i = v_R (x_i))$ belongs to the intersection of ridges of
% all~$f_{j}$, and the equations~$f_j (x) = 0$ define equations in~$k$ in
% the principal parts of the unknowns~$x_i$.


% Writing~$X$ for a column vector containing these coefficients, $X$~must
% satisfy a matrix equation of the form
% \begin{equation}\label{eq:changevar-abstract}
% A' = A σ(X) + θ(B Q(X)),
% \end{equation}
% where $A$, $A'$~contain the diagonal coefficients of both quadratic
% pencils, $B$~contains the coefficients of the polar form, and $Q$~is a
% map with coefficients of the form~$x_i x_j$ and~$γ(x_i)$.
% In particular, we see that for any sub-$R$-module~$M'$ of~$M$, the
% image~$Q(M)$ is again a $R$-module.
% This is therefore again true of~$θ(B Q(M))$.
% 
% We may therefore define a sequence of $R$-modules~$M_i$ in the following
% way: $M_0 = M$, and $M_{i+1}$ is the set of all~$X ∈ M_i$ such that~$A' ≡ A
% σ(X) + θ(B Q(M_i))$.
% This is a decreasing sequence of $R$-modules and
% therefore eventually stabilizes at a module~$M_{∞}$.

%>>>1
\section{Computation of the second secret for IP2S}
\label{S:IP2S}

\subsection{Reduction to the regular case}
Two families of polynomials~$(a_1,…,a_m)$ and~$(b_1,…,b_m)$ are
\emph{isomorphic with two secrets} if there exist bijective linear
transformations~$s$ of the $n$~variables and~$t$ of the $m$~polynomials
such that $t ∘ \bm{a} ∘ s = \bm{b}$. Assume that $m = 2$. Then the second
secret~$t$ is a homography in two variables, which we write~$γ ∈
\GL_2(k)$.

\begin{prop}
Let~$(a_λ)$, $(b_λ)$ be two pencils
and $(a'_λ)$ and~$(b'_λ)$ be their regular parts.
For any homography~$t$,
$t ∘ (a_λ)$~is isomorphic (in the IP1S sense) to~$(b_λ)$
if, and only if, $t ∘ (a'_λ)$~is isomorphic to~$(b'_λ)$
and $(a_λ)$ and~$(b_λ)$ have the same Kronecker multiplicities.
\end{prop}
\begin{proof}
We only need to prove the forward implication;
namely, that any pencil isomorphic to~$(b_λ)$
has its regular part isomorphic to~$(b'_λ)$.

The minimal index of the pencil~$(b_λ)$ is
the minimal degree of a kernel  vector~$e_0 + … +λ^h e_h$ for~$b_{λ}$;
such a vector may be written in homogeneous form in~$(λ:μ)$
as~$e(λ:μ) = ∑ λ^i μ^{h-i} e_i$,
which is in the kernel of the quadratic form~$b(λ:μ) = μ b_0 + λ b_{∞}$.
Now let~$γ = \smat{a&b\\c&d} ∈ \GL_2(k)$ be a homography.
Then the vector~$e^{γ}$ defined by~$e^{γ}(λ:μ) = e(aλ+bμ:cλ+dμ)$~is
in the kernel of~$b_{γ(λ)}$ iff $e$~is in the kernel of~$b$.
This proves that the pencils $(b_{γ(λ)})$ and~$(b_{λ})$
have the same minimal index.
By induction, all their Kronecker blocks have the same multiplicities.
\end{proof}

% \begin{prop}
% Let~$K_{λ}$ be a Kronecker block of dimension~$2h+1$ as in
% Prop.~\ref{prop:kronecker1}. Then for all~$γ ∈ \GL_2(k)$, the pencils
% with matrix~$K_{λ}$ and~$K_{γ(λ)}$ are isomorphic in the IP1S sense.
% \end{prop}
% 
% \begin{proof}
% Let~$(e_0,…,e_h; f_1,…,f_h)$ be the basis in which the pencil~$(b_{λ})$
% has the Kronecker-block matrix. Let~$e(x) = ∑ x^i e_i$ and~$f(y) = ∑
% y^{i-1} e_i$. The pencil~$(b_{λ})$ is then defined by the relation
% \begin{equation}\label{eq:def-b-intr}
% b_{λ} (e(x), f(y)) \;=\; (x+λ) F(xy), \quad F(t) = 1 + … + t^{h-1}.
% \end{equation}
% For any homography~$γ = \smat{a&b\\c&d} ∈ \GL_2(k)$, define a
% basis~$(e_i^{γ}, f_i^{γ})$ by the relations
% \begin{equation}\label{eq:def-ei-gamma}
% ∑ (a λ + b μ)^i (c λ + d μ)^{h-i} e_i = ∑ λ^i μ^{h-i} e_i^{γ}.
% \end{equation}
% We then find that in the basis 
% 
% ; then the only relation is~$b_{λ} · ∑ λ^i
% e_i = 0$, which we write as a homogeneous polynomial
% in~$(λ:μ)$ as $(λ b_{∞} + μ b_{0}) (∑ λ^i μ^{h-i} e_i) = 0$.
% Let~$γ = \smat{a&b\\c&d}$ and define a basis~$(e_i^{γ}, f_i^{γ})$ by
% Then in the basis
% \end{proof}


\subsection{IP2S in the regular case}

Let~$(a_{λ})$ and~$(b_{λ})$ be two \emph{regular} pencils of bilinear
forms such that $a_{γ(λ)}$~is isomorphic, in the IP1S sense, to~$b_{λ}$.
Then the homography~$γ$ maps the characteristic polynomial~$f(λ:μ)
= \det (a_{λ:μ})$ to~$g(λ:μ) = \det (b_{λ:μ})$. In particular, it maps the
prime factors of~$f$ to those of~$g$, respecting both their degree and
their multiplicity as a factor of the characteristic polynomial.

Let~$S_{d,e}$~and~$T_{d,e}$ be the set of factors of degree~$d$ and
multipplicity~$e$ of the polynomials~$f$ and~$g$.
Then any homography~$γ$ mapping all the elements of~$S_{d,e}$ to~$T_{d,e}$
for each pair~$(d,e)$ is a possible second secret in the IP2S problem.
We compute the intersection for~$(d,e)$ of
the set~$Γ_{d,e}$ of homographies mapping
the elements of~$S_{d,e}$ to~$T_{d,e}$.
In most cases, the first set~$Γ_{d,e}$ already contains only one candidate,
which is therefore the second secret~$γ$.
The discussion depends on the degree~$d$ of the polynomials.
We note that the sum of the cardinals of the sets~$S_{d,e}$ is
the number of variables~$n$;
therefore, we may use the worst-case estimate~$\card{S_{d,e}} = O(n)$
for each~$(d,e)$.

We shall use the following classic results.
\begin{prop}\label{prop:homography}
\begin{enumerate}
\item Let~$(x_1, x_2, x_3)$ and~$(y_1, y_2, y_3)$ be two (ordered)
triples of distinct points of~$ℙ^1(k)$. There exists a unique
homography~$γ ∈ \mathrm{PGL}_2(k)$ such that~$γ(x_i) = y_i$.
\item Let~$(x_1, x_2, x_3, x_4)$ and~$(y_1, y_2, y_3, y_4)$ be two
(ordered) quadruplets of distinct points. They are homographic iff they
have the same cross-ratio $B(x) = B(y)$, where
\begin{equation}
B(x) = \frac{(x_1-x_3)(x_2-x_4)}{(x_1-x_4)(x_2-x_3)}.
\end{equation}
\item Let~$\acco{x_1, x_2, x_3, x_4}$ and~$\acco{y_1, y_2, y_3, y_4}$ be
two (unordered) sets of four points. They are homographic iff they have
the same $j$-invariant~$j(x) = j(y)$, where
\begin{equation}\label{eq:j-invariant}
j(x) = \frac{(B(x)^2-B(x)+1)^3}{B(x)^2(1-B(x))^2}.
\end{equation}
\item Let~$u(x) = ∑ u_i x^i$ and~$v(x)$ be two monic polynomials
of degree four. They are homographic iff they have the same
$j$-invariant, where $j(u)$~is a rational function of degree~six in the
coefficients of~$u$.
\end{enumerate}
\end{prop}

We note that the formula for the $j$-invariant given
in~\eqref{eq:j-invariant} is, up to a constant factor, the formula for
the $j$-invariant of an elliptic curve. Namely, two elliptic curves with
equations~$y^2 = f(x)$ and~$y^2 = g(x)$, where $f, g$ are separable
polynomials of degree~$≤ 4$, are isomorphic iff the polynomials~$f$
and~$g$ are homographic.

\bigbreak
We now explain how we compute the set~$Γ_{d,e}$ for each pair~$(d,e)$.

\paragraph{Case~$d = 1$.}
If $\card{S_{1,e}} ≥ 3$, then we may immediately recover the
homography~$γ$: namely, fix a triple~$(x_1, x_2, x_3)$ in~$S_{1,e}$, and
iterate over the triples in~$T_{1,e}$. For each such triple, there exists
a unique homography~$γ$ such that~$γ(x_i) = y_i$. This homography belongs
to~$Γ_{1,e}$ iff the images of all the other points of~$S_{1,e}$ belong
to~$T_{1,e}$. Since there are~$3!\binom{\card{S_{1,e}}}{3} = O(n^3)$
triples~$(y_i)$, this computation requires~$O(n^3)$ field operations.

If $1 ≤ \card{S_{1,e}} ≤ 2$, then $Γ_{1,e}$~may be explicitly computed as
the union of the set of homographies mapping the elements of~$S_{1,e}$ to
those of~$T_{1,e}$ for all permutations of~$T_{1,e}$.

\paragraph{Case~$d = 2$.}
Assume $\card{S_{2,e}} ≥ 2$. Let~$u_1, u_2 ∈ S_{2,e}$ and~$v_1, v_2 ∈
T_{2,e}$ be monic polynomials of degree~two. Any homography between the
sets~$\acco{u_1, u_2}$ and~$\acco{v_1, v_2}$ will map~$u_1 u_2$ to~$v_1
v_2$. By Prop.~\ref{prop:homography}(iv), there exists at most a bounded
number of such homographies. Since there are~$\binom{\card{S_{2,e}}}{2} =
O(n^2)$ pairs~$(v_1, v_2)$, this requires~$O(n^2)$ field operations.

If~$\card{S_{2,e}} = 1$, then $Γ_{2,e}$~is the set of all homographies
mapping the unique element of~$S_{2,e}$ to the unique element
of~$T_{2,e}$.

\paragraph{Case~$d = 3$.}
Fix an element~$u ∈ S_{3,e}$. For all~$v ∈ T_{3,e}$, there exist at
most~$3! = 6$ homographies~$γ$ mapping~$u$ to~$v$. Each candidate belongs
to~$Γ_{3,e}$ iff it maps all other elements of~$S_{3,e}$ to elements
of~$T_{3,e}$. There are~$\card{S_{3,e}} = O(n)$ candidates~$u$ and
therefore~$O(n)$ candidate homographies~$γ$.

\paragraph{Case~$d = 4$.}
Fix an element~$u ∈ S_{4,e}$. The candidates as homographic images of~$u$
in~$T_{4,e}$ are the~$v$ such that~$j(v) = j(u)$. Each candidate
polynomial~$v$ gives at most $4! = 24$~candidates homographies~$γ$. This
allows to compute~$Γ_{4,e}$ in~$O(n)$ field operations.

\paragraph{Case~$d ≥ 5$.} The naïve method is to differentiate~$(d-4)$
times the elements of~$S_{d,e}$ to reduce to the case where~$d = 4$.
However, as this uses only the five leading coefficients, if the
polynomials are specially chosen we may find too many homographies; for
example, although the polynomials~$x^d-1$ and~$x^d$ are not homographic,
all their derivatives are. Instead, we first compose all the elements
of~$S_{d,e}$ and~$T_{d,e}$ by a known, randomly chosen homography~$ρ$. In
general, for any two non-homographic elements~$u_1, u_2 ∈ S_{d,e}$, the
derivatives~$(∂/∂x)^{d-4}\, (u_i ∘ ρ)$ are non-homographic. In the improbable
case where they are homographic, we only need to change the random
homography~$ρ$. In this way, we may compute the set~$Γ_{d,e}$ in at
most~$O(n)$ field operations.

\paragraph{Computing the hidden homography.}

The hidden homography~$γ$ lies in the intersection of all sets~$Γ_{d,e}$.
As each one of these sets is likely to be extremely small or even reduced
to~$\acco{γ}$, we compute them in increasing order of assumed size.
We use the above estimates: for each~$(d,e)$, we use the assumed size
\begin{equation}
C_{d,e} = \begin{cases}
\card{S_{d,e}}^3,& d = 1;\\
\card{S_{d,e}}^2,& d = 2;\\
\card{S_{d,e}},& d≥ 3,
\end{cases}
\end{equation}
and sort the pairs~$(d,e)$ by increasing values of~$C_{d,e}$. We finally
find a bounded number of candidate homographies using no more
than~$O(n^3)$ operations in~$k$.

% Conclusion
% \section*{Conclusion}%<<<1
% 
% In this paper, we show that we can solve in polynomial-time the IP
% problem with two quadratic forms over any finite field.
% The obvious questions are whether it is possible to generalize this to
% more than two equations.
% This would depart from the classic results about bilinear pencils;
% therefore, fewer tools are available.
% Even in the regular case, our work heavily uses the factorization of
% the characteristic polynomial.
% An analogous strategy for~$m ≥ 3$ would require a detailed
% geometric study of the hypersurface defined by this characteristic
% polynomial.
% 
% %>>>1
\bibliographystyle{plain}
\bibliography{biblio}%>>>1
\message{******************** PAGE=\thepage *****************^^J}
% \step{Compute the minimal isotropic vectors~$(e_1,…,e_h)$}%<<<2
% 
% Write the~$n × (2n)$-matrix~$(B_{∞} \; B_0)$ in lower row echelon form as
% \begin{equation}
% (B_{∞} \; B_0) \;=\; (⋆) · \mat{A_{∞} & 0\\ C & A_0},
% \end{equation}
% where $(⋆)$~is an invertible~$n × n$-matrix and
% $0$~is a $r × n$-block with $r$~being the largest possible value.
% This implies that the $n-r$~lines of~$A_0$ are linearly independent, and
% therefore that its columns have full rank~$n-r$; therefore, there exists
% a matrix~$F$ such that~$C = -A_0 F$. From this, we see that
% \begin{equation}
% B_{∞} x + B_0 y = 0 \;⇔ \; \begin{cases} A_{∞} x = 0\\ y ∈ Fx + \Ker A_0.
% \end{cases}
% \end{equation}
% In particular, the case~$x = 0$ tells us that $\Ker A_0 = \Ker B_0$. By
% using the \emph{upper} row echelon form, we likewise compute a matrix~$G$
% such that~$B_{∞} x = B_0 y$ implies~$x ∈ G y + \Ker B_{∞}$.
% 
% A \emph{chain} of length~$h$ is a solution~$(e_0,…,e_h)$ of the
% equations~$b_0(e_i) + b_{∞}(e_{i-1}) = 0$ and~$b_{∞}(e_h) = 0$.
% We define by induction a sequence~$(U_i)$ of vector spaces such that the
% $h$-chains are defined by the relations~$e_0 ∈ U_h$ and~$e_i ∈ F(e_{i-1})
% + U_{h-i}$.
% 
% The base case is that of chains of length~$0$, which are the
% elements of~$\Ker B_{∞}$. We define $U_0 = \Ker B_{∞}$.
% 
% A $(h+1)$-chain is a $(h+2)$-uple~$(e_0,…,e_{h+1})$ such that
% $(e_1,…,e_{h+1})$~is a $h$-chain and $b_{0} e_1 + b_{∞} e_0 = 0$.
% The first condition amounts to~$e_1 ∈ U_h$ and~$e_i = f(e_{i-1}) +
% U_{h-i}$ for all~$i ≥ 2$; the second one means that $e_0 ∈ G U_{h} + \Ker
% B_{∞}$. We define~$U_{h+1} = G U_h + \Ker B_{∞}$.
% 
% This allows us to compute minimal isotropic vectors of length~$h$ as
% satisfying the relations
% \begin{equation}\label{eq:m.i.v.-matrix}
% e_0 ∈ U_{h} ∩ \Ker B_0, \quad e_{i} ∈ F e_{i-1} + U_{h-i}.
% \end{equation}
% This determines the space of isotropic vectors of degree~$≤ h$ with
% total complexity~$O(n^3 (h+1))$; moreover, as this computation is
% triangular, it also gives the space of isotropic vectors of degree~$≤ h'$
% for all~$h' ≤ h$, so that we only need to perform one run of this
% algorithm over all the singular part of the pencil. Once we have isolated
% the minimal Kronecker module~$K$ of~$V$ in Step 2, we may then project
% this basis on the quotient~$V/K$ to directly obtain a (sorted) basis of
% the isotropic vectors of~$V/K$.
% 
% \step{Compute a Kronecker module as a direct factor}%<<<2
% Given the vectors~$e_1,…,e_h$ computed in the previous step,
% we can, with no more than~$O(n^3)$ field operations, compute
% vectors~$f_1,…,f_h$ such that~$b_0(e_i, f_j) = 1$ if~$i = j$ and
% $0$~otherwise.
% In any basis completing the family~$(e_0, …, e_h; f_1, …, f_h)$,
% the symmetric pencil~$(b_{λ})$ has the matrix
% \begin{equation}\label{eq:matrix-b1}
% B_{λ} = \mat{0 & K'_{λ} & 0\\\transpose{K'_{λ}} & A_{λ}&\transpose{C_{λ}}\\
%   0 & C_{λ} & B'_{λ}},
% \end{equation}
% where the blocks have size~$d+1$, $d$ and~$n-(2d+1)$. We use a change of
% coordinates of the form
% \begin{equation}\label{eq:p1}
% P = \mat{1 & 0 & X\\0&1&0\\0&Y&1}.
% \end{equation}
% The action of~$P$ on the sub-matrix~$C_{λ}$ of~$B_{λ}$ is given by $C_{λ}
% ← C_{λ} + \transpose{X} K'_{λ} + B_{λ} Y$. Now let~$x_0,…,x_{h}$;
% $y_1,…,y_h$; $c_1,…,c_h$; $c'_1,…,c'_h$ be the columns of~$\transpose{X}, Y,
% C_0$ and~$C_{∞}$. We then have to
% solve the equations
% \begin{equation}\label{eq:chvar-x}
% \begin{cases} c'_i + x_i + B'_0 y_i = 0\\ i = 1,…,h\end{cases};\quad
% \begin{cases} c'_i + x_{i-1} + B'_∞ y_i = 0\\i=1,…,h\end{cases}.
% \end{equation}
% This uniquely determines the values~$x_0$ and~$x_{h}$. The equations
% for~$x_1,…,x_{h-1}$ have solutions iff the values~$y_1,…,y_h$ satisfy
% the relations
% $B'_0 y_i + B'_{∞} y_{i+1} = c'_{i+1} - c_i$ for~$i = 1,…,h-1$. This
% translates into matrix form as
% \begin{equation}\label{eq:chvar-y}
% \mat{B'_0&B'_{∞}&&0\\&\;\sddots{B'_{∞}}&\sddots{B'_{∞}}&\\0&&B'_0&B'_{∞}} ·
%   \mat{y_1\\⋮\\y_h} = \mat{c'_2-c_1\\⋮\\c'_h-c_{h-1}}.
% \end{equation}
% We may solve this equation using the same technique as that of Step~1,
% for a total cost of~$O(n^3 h)$. Computing the values~$(x_i)$ is then
% straightforward.
% 
% 
% \step{Put the Kronecker module in canonical form}%<<<2
% We now compute a coordinate change
% \begin{equation}\label{eq:chvar-q}
% \def\arraystretch{.7}
% Q = \mat{1&Z&\\&1\\&&1}
% \end{equation}
% such that~$\transpose{Q} · B_{λ} · Q$~puts the Kronecker module in the
% canonical form~$K_{h}$ described in~\eqref{eq:def-K}. The action of~$Q$
% on~$A_{λ}$ is given by~$A_{λ} ← A_{λ} + \transpose{Z} K_{λ} +
% \transpose{K_{λ}} Z$. Let~$Z = (z_{i,j})$, $A_0 = (a_{i,j})$ and~$A_{∞} =
% a'_{i,j}$; the equations to solve are then
% \begin{equation}\label{eq:zij}
% z_{i,j} + z_{j,i} = a_{i,j}, \quad z_{i-1,j} + z_{j-1,i} = a'_{i,j},
% \quad \text{for~$i,j = 1,…,h$}.
% \end{equation}
% Since the matrices~$A_{0}$ and~$A_{∞}$ are symmetric, only the
% equations for~$i ≥ j$ are relevant. We derive from~$z_{i,j}$ the
% values $z_{i,i} = \frac{1}{2} a_{i,i}$ and~$z_{i-1,i} = \frac{1}{2}
% a'_{i,i}$. The remaining values~$z_{i,j}$ for~$i+j=\mathrm{constant}$ are
% deduced from the relation~$z_{i,j} - z_{i-1,j+1} = a_{i,j} - a'_{i,j+1}$.
% We check that these relations compute all the values~$z_{i,j}$ in optimal
% time, which is~$O(n^2)$ computations in the base field~$K$.
% 
% 
% \fi
% 

%>>>1
\appendix
\section{Algorithms for pencils of bilinear forms}
\label{ap:bilinear}
\subsection{Kronecker decomposition}
\label{ap:kronecker}

\begin{prop}
There exists an algorithm computing the Kronecker decomposition
of a bilinear pencil~$b_0 -λ b_∞$
with time complexity~$O((h_{\max} + 1)\, n^3)$ field operations,
where $n$~is the dimension of the pencil,
and $h_{\max}$~is the maximal degree of a Kronecker module factor.
\end{prop}
\begin{proof}
The kernel of~$b_0 - λ b_∞$, as a $k[λ]$-module,
is equipped by an increasing filtration by polynomial degrees,
and in its decomposition as a sum of Kronecker modules~$⨁ K_h^{e_h}$,
this filtration corresponds to the filtration by the increasing
indexes~$h$.
% We show here that it is possible to compute this filtration
% with at most $O(n^4)$ operations.

\medbreak

We consider the lower echelon form
of the concatenated $n × (2n)$-matrix $(b_0 b_∞)$, written as
\begin{equation}
(b_0 \; b_∞) \;=\; U · \mat{C & 0 \\ M & A},
% (B_{∞} \; B_0) \;=\; (⋆) · \mat{A_{∞} & 0\\ C & A_0},
\end{equation}
where $U$~is an invertible matrix of size~$n$
and $0$~is a $r × n$-block, with $r$~being the largest possible value.
This implies that $A$~has rank~$n-r$ and hence that
there exists~$F$ such that~$M = A F$.
Moreover, since $\smat{0\\A} = U b_0$, we have~$\Ker A = \Ker b_0$.
From this we deduce that
\begin{equation}
b_∞ x - b_0 y \;=\; 0 \quad ⇔ \quad
  \begin{cases} C x = 0 \\ b_0 (y - F x) = 0.\end{cases}
\end{equation}
Likewise, the upper echelon form of $(b_0\;b_∞)$
gives matrices $D$ and~$G$ such that
$b_∞ x - b_0 y = 0 ⇔ (D y = 0, b_∞ (x - G y) = 0)$.
We also define an increasing sequence~$(E_h)$ of subspaces of~$V$
by~$E_0 = \Ker b_∞$, $E_{h+1} = (\Ker b_∞) + G(E_h)$.
Then $E_h$ is exactly the set of elements~$x ∈ V$ such that there exists
a sequence~$x_0 = x, …, x_h$ satisfying $b_∞ x_i = b_0 x_{i+1}$ for all~$i$
and~$b_∞ x_h = 0$.
Moreover, such a sequence is determined by the choices
of~$x_0 ∈ E_h$ and~$x_{i} ∈ F(x_{i-1}) + (\Ker b_∞)$ for all~$i ≥ 1$.

We now see that the elements~$x_0 + x_1 λ + … + x_h λ^h$
of degree~$h$ of~$\Ker(b_0 - λ b_∞)$
are determined by the relations~$x_0 ∈ E_{h} ∩ (\Ker b_0)$
and~$x_{i+1} - F (x_i) ∈ (\Ker b_∞)$.
Since the filtration of~$(\Ker b_0)$ by the spaces~$E_{h} ∩ (\Ker b_0)$
has $(h_{\max} + 1)$~steps,
we can compute it with at most~$O((h_{\max}+1) · n^{ω})$ operations.

Once this filtration is computed,
all remaining steps of the 1976 algorithm use only linear algebra in~$k^n$,
with a total cost of at most~$O(n^ω)$ operations.
\end{proof}

Over the real and complex numbers,
there exist cubic algorithms computing the Kronecker decomposition
of pencils of linear maps~\cite{beelen1988improved}.
These algorithms use real rotations and floating-point arithmetic,
and are therefore not applicable to finite fields.
We do not know whether there also exists a cubic algorithm
for the Kronecker decomposition over finite fields.


\subsection{Primary decomposition}
\label{ap:primary}

We give an algorithm that proves
Proposition~\ref{prop:primary}.

% \begin{proof}[\proofof Proposition~\ref{prop:primary}]%<<<
Following~\cite[Lemma 4.1]{inventiones1976waterhouse},
we first decompose the pencil~$b_0 - λ b_∞$ as the orthogonal sum of
a pencil $b_0' - λ b_∞'$ such that $b_∞'$~is regular,
and of the summand corresponding to the place at infinity.
The latter summand is exactly
the limit~$E_{∞}$ of the increasing sequence of spaces~$(E_{h})$
already computed by the algorithm of Prop.~\ref{prop:kronecker-decomposition}.

We now assume that $b_0$~is regular
and define the endomorphism~$c = b_∞^{-1} b_0$.
Then the orthogonal sum in~Proposition~\ref{prop:primary}~(i)
is given by the Frobenius rational normal form of~$c$.
We may compute this normal form, and in particular
the prime factorization of the characteristic polynomial $\det (b_0 - λ b_∞)$,
with at most~$O(n^ω \log n)$ field operations~\cite{kaltoffen11compute}.

The summand associated to the factor~$p(λ)^e$,
where $p$~is an irreducible polynomial of degree~$d$ over~$k$,
is a free $R$-module of rank~$m$,
where $R = K[π]/π^e$ and~$K = k(α)/p(α)$.
A basis over~$R$ of this module is given by
the Frobenius rational normal form.
We also compute an isomorphism between the rings $k[λ]/p(λ)^e$ and~$R$.
Since $k[c]$ is a complete local $k$-algebra
with maximal ideal generated by~$p(c)$, by Hensel's lemma
the approximate root~$c$ of~$p$ lifts to an exact root~$α$.
We may compute~$α$ using at most $O(\log e · \M(d) · \M(de))$
operations in~$k$~\cite[Theorem 15.11]{vzgg}.
The total cost for all invariant factors is~$O(\M(n)^2)$,
and therefore~$O(n^ω)$.

\medbreak

We now prove point~(ii) of Proposition~\ref{prop:primary}.
According to what precedes, we assume here that $V$~is given as
a free $R$-module of rank~$m$.
We compute the $R$-bilinear form~$b_R$ whose trace is~$b$,
according to Propositions~\ref{prop:trace-ext} and~\ref{prop:trace-local}.
Computing each coefficient of the matrix of~$b_R$
requires computing $e$~coefficients in~$K$,
each of which needs linear algebra in the $k$-vector space~$K$;
therefore, the total computational cost of this step
is at most~$O(d^ω · e · m^2) ≤ O(n^ω)$.

We conclude the proof by reducing the $R$-bilinear form~$b_R$
to a canonical form.
This result is well-known over
a finite field of odd characteristic~\cite[IV(1.5)]{milnorhusemoller},
and lifts via Hensel's lemma to the ring~$R$.
By the Gram orthogonalization algorithm~\cite[I(3.4)]{milnorhusemoller},
$b_R$~is congruent to a diagonal bilinear form,
and computing the transformation has a cost of~$O(m^3)$
operations in~$R$~\cite[16.2]{vzgg}.
This is the dominant step of the algorithm.

Since the field~$k$ has odd characteristic,
$x^2$~is a separable polynomial over~$R$,
and two applications of Hensel's lemma in the complete ring~$R$ allow
the following lifts to~$R$ of results in the finite field~$k$:
\begin{enumerate}
\item[(a)] let~$δ$ be a non-square element of~$k[λ]/p(λ)$;
then for any invertible~$a ∈ R$,
one of~$a$ or $a/δ$ is a square in~$R$;
\item[(b)] the equation~$u^2 + v^2 = δ$ has a solution with~$u, v ∈ R$.
\end{enumerate}
By~(a), we may assume that the diagonal coefficients of~$b$
are either~$1$ or~$δ$.
From~(b), we deduce the matrix relation
\begin{equation}
\transpose{\mat{u&-v\\v&u}}·\mat{1&0\\0&1}·\mat{u&-v\\v&u} =
\mat{δ&0\\0&δ}.
\end{equation}
This allows canceling all pairs of~$δ$ in the diagonal.
The cost for each coefficient is that of a square root in~$K$,
which is subquadratic~\cite{sqrt},
plus a Hensel lift from~$K$ to~$R$.
The overall cost is therefore again~$O(n^3)$.
% \end{proof}%>>>

% \section{Classification of $τ$-alternating forms.}%<<<1
% 
% % Classification by the norm
% Although this is not directly useful for the IP1S problem,
% $τ$-alternating forms have a nice classification up to congruence.
% For any bilinear form~$b$ on a free $R$-module~$M$, we define the
% \emph{norm} of~$b$ as the ideal~$\fr{n} b$ of~$R$
% generated by the elements~$b(x, x)$ for~$x ∈ M$.
% 
% \begin{prop}\label{prop:eqv-norm}%<<<
% Two non-degenerate, $τ$-alternating forms are equivalent if and only
% if they have the same norm.
% \end{prop}%>>>
% \begin{proof}%<<<
% We show that the bilinear form~$b$ is equivalent to either the form with
% identity matrix, if $\fr n b = R$; or the orthogonal direct sum
% \[ N_a = \mat{a & 1\\1&0} ⟂ \mat{0 & 1\\1&0} ⟂ … ⟂ \mat {0 & 1\\ 1 & 0}, \]
% where $a$~is a generator of~$\fr n b$, if $\fr n b ⊂ π R$.
% We note that, when the dimension of~$V$ is odd, the identity form is
% congruent to the form~$N_1$, since the transformation~$\mat{1&1\\0&1}$
% maps the identity matrix to the form~$\mat{1&1\\1&0}$.
% 
% We write~$[u]$ for the one-dimensional form with coefficient~$u$
% and~$H_{v, w}$ for the form with matrix~$\mat{v&1\\1&w}$.
% We also write~$H = H_{0,0}$.
% 
% By~\cite[§2]{milnor2}, the $k$-bilinear form~$b_k = b ⊗_R k$ has a
% decomposition~$b_k ≃ [d_1] ⟂ … ⟂ [d_r] ⟂ H^s$, where all~$d_i$ are
% non-zero since $b$~is non-degenerate. We distinguish two cases.
% 
% \subparagraph{Case 1: $\fr n b = R$.}
% We first show that the reduced form~$b_k$ is isomorphic, over~$k$, to the
% identity form. Since $\fr n b = R$, the list of~$d_i$ in the above
% decomposition is not empty. Moreover, since the field $k$~is perfect, all
% elements~$d_i$ are squares in~$k$, so that up to a coordinate change we
% may assume that~$d_i = 1$. Finally, we note that the
% matrix~$\mat{1&1&0\\1&0&-1\\1&1&-1}$ is an isomorphism between the
% forms~$[1] ⟂ [1] ⟂ [-1]$ and~$[1] ⟂ H$, so that if $r ≥ 1$ we may cancel
% all the direct factors~$H$ and in this case $b_k$~is isomorphic to the
% bilinear form with identity matrix.
% 
% By~\cite[Corollary 3.4]{baeza1978quadratic},
% the diagonalization of~$b_k$ lifts to a diagonalization
% $b ≃ [a_1] ⟂ … ⟂ [a_r]$ over~$R$.
% Since $b$~is $τ$-alternating, all coefficients~$a_i$ are $τ$-alternating.
% If the length of~$R$ is odd, then the set of $τ$-alternating elements of~$R$
% is~$π V(R)$, which contradicts the regularity of~$b$.
% Therefore, the length of~$R$ is even, which means that $a_i ∈ V(R)$ and they are
% therefore squares in~$R$.
% From this we deduce that $b$~is isomorphic to the identity bilinear form.
% 
% \subparagraph{Case 2: $\fr n b ⊂ π R$.}
% This means that the form~$b_k$ is alternating, so that~$b_k ≃ H^s$.
% By~\cite[Corollary 3.4]{baeza1978quadratic}, this decomposition again lifts to a
% decomposition $b ≃ H_{u_1, v_1} ⟂ … ⟂ H_{u_s, v_s}$, where all
% coefficients~$u_i, v_i$ are $τ$-alternating.
% 
% Let $b = H_{u,v}$ be $τ$-alternating and regular; up to a swap of~$u, v$, we
% may write it as~$H_{u, u a^2}$ for some~$a ∈ R$. Since $b$~is
% regular, $1 + a u ∈ R^{×}$. Therefore, the coordinate
% change $P = \mat{1+a u & a/(1+a u) \\ u & 1/(1+a u)}$ transforms the
% bilinear form~$b$ to~$H_{u, 0}$.
% 
% Finally, we note that the bilinear form~$b = H_{u, 0} ⟂ H_{u a^2 u, 0}$ is
% isomorphic to~$H_{v, 0} ⟂ H_{0,0}$ via the coordinate change
% % \begin{equation}
% $\mat{1 & 0 & a & 0\\0&1&0&0\\0&0&1&0\\au & a & 0 & 1}$.
% % \end{equation}
% \end{proof}%>>>
% 
% 


\section{Comparison to the ``polar decomposition'' algorithm.}
\label{ap:polar}

The “polar decomposition” algorithm was proposed as a solution to
the odd-characteristic IP1S problem by
Berthomieu, Faugère and Perret~\cite{2013bfp}.
Their method is valid for fields where every regular matrix~$M$
has a square root polynomial in~$M$.
This property holds only for algebraically closed field,
as was noticed in~\cite[6.1]{2013bfp}.

\paragraph{Decisional IP1S and extensions of scalars.}

Considering a finite field~$k$, its algebraic closure is merely
a tower of algebraic extensions.
This raises the following question: given a finite field~$k$,
for which extensions~$k'$ of~$k$ is it true that
any two pencils that are IP1S-equivalent over~$k'$
are always equivalent over~$k$?

The structure given by Propositions~\ref{prop:kronecker-decomposition}
and~\ref{prop:primary} gives a simple answer.
Namely, since the Kronecker degrees are invariant by extension of scalars,
any totally singular pencils which are $k'$-equivalent are $k$-equivalent.
On the other hand, two regular pencils are $k$-equivalent
if and only if, for all primary factors~$R =k[λ]/p(λ)^e$,
the corresponding bilinear forms on~$k[λ]/p(λ)$ are equivalent,
which means that all squares in~$k'[λ]/p(λ)$
are squares in~$k[λ]/p(λ)$.
Therefore the answer is positive exactly when
the extension degree~$[k':k]$ is odd.

We give first a simple example to illustrate possible situations in even extension degrees.
Define the two-dimensional
quadratic pencils~$(A,B) = (x^2 - y^2, x^2 + y^2)$
and~$(A', B') = (x^2 - y^2, - x^2 - y^2)$. Both pencils have $\lambda-1$ and $\lambda+1$ for primary factors,
with corresponding factors $u$ being respectively $(1,-1)$ and $(-1,1)$.
Therefore, the two pencils are equivalent only over a field
containing a square root of $-1$.

More generally, let $k$ be finite field such that both polynomials $p=x^{2^n}-2$
and $p'=x^{2^n}+2$ are irreducible over $k$. This is the case when the 
order of $k$ is an odd power of a prime congruent to $1$ modulo $4$.
Then consider the two pencils having both $p$ and $p'$ for primary factors,
with corresponding factors $u$ being respectively $(M_p,1)$ and $(1,M_{p'})$.
Over an extension of $k$ of degree $2^m$, the two pencils are nonequivalent if $m < n$ and 
equivalent if $m \ge n$.


\end{document}



\section{Comparison to the ``polar decomposition'' algorithm.}
\label{ap:polar}

The “polar decomposition” algorithm was proposed as a solution to
the odd-characteristic IP1S problem by
Berthomieu, Faugère and Perret~\cite{2013bfp}.
This method uses ideas coming from quadratic forms over the reals.
In that case, one has the following useful property:
any positive definite symmetric matrix~$M$ has a square root
which is a polynomial in~$M$
(and therefore commuting with any matrix that commutes with~$M$).

This property is a consequence of the fact
that a sum of squares is again a square in~$ℝ$.
More generally, we say that a \emph{real quadratic extension} of a field~$k$
is an extension obtained by adjoining the square root of a sum of squares.
Then the “polar decomposition” algorithm solves the IP1S problem
over a tower of real quadratic extensions of the base field.

This solves the original problem only when the base field is \emph{Euclidean},
\emph{i.e.} when it has no real quadratic extensions.
For example, algebraically closed fields are Euclidean,
as are real closed fields, such as~$ℝ$
or the field~$ℝ_{\mathrm{alg}}$ of real algebraic numbers.
However, since any element of a finite field is a sum of (two) squares,
all quadratic extensions of a finite field are real
and no finite field is Euclidean.

\medskip
Let~$B$ be an invertible symmetric matrix.
We recall that the $B$-adjoint of a matrix~$M$
is~$M^{⋆} = B^{-1} · \transpose{M} · B$.
The two following claims about matrix square roots
are made in~\cite[(3)]{2013bfp}:
\begin{enumerate}
\item[(A)] Let~$Y$ be a regular matrix commuting with both~$H$ and~$H^{⋆}$.
Then the matrix~$Z = B· Y · \transpose{Y} · B^{-1}$ has a square root~$W$.
\item[(B)] Define $X = Y · W^{-1}$.
Then $X$~is a solution to the IP1S problem : $H· X = X · H$ and~$X^{⋆} · X = 1$.
\end{enumerate}
In the IP1S case for a bilinear pencil~$A - λ B$,
$H$~is the matrix of the characteristic endomorphism~$B^{-1} A$.
This provides us with the extra hypothesis that, since $A$~is symmetric,
$H^{⋆} = H$; this hypothesis is not used in~\cite{2013bfp}.
We give here counter-examples to both claims above,
over (almost) any finite field with odd characteristic,
and under the hypothesis~$H^{⋆} = H$.

For claim (A), let~$d$ be a non-square element of~$k$.
Since $k$~is finite, there exist~$u, v ∈ k$ such that~$d = u^2 + v^2$.
Let~$t ∈ k ∖ \acco {0, 1, -1}$ and define
\[ B = \mat{t & 0 \\ 0 & 1}, \quad
H = \mat{0 & 1 \\ t & -\frac{u}{v}(t+1)}. \]
Then~$H^{⋆} = H$ and $Y = \mat{u & v \\ t v & -t u}$ commutes with~$H$.
However,
$Z = B · Y · \transpose{Y} · B^{-1} = \mat{d & 0 \\ 0 & t^2 d}$~has no square
root.

We note that, since the only hypothesis needed on~$b$
is that it is a sum of squares,
this counter-example shows that
the “polar decomposition” algorithm really needs
a generic tower of real quadratic extensions.

\medskip

For claim B, let~$d$ be any element of~$k$ and again write~$d = u^2 + v^2$.
We modify the previous example by setting~$t = -1$: let
\[ B = \mat{-1 & 0 \\ 0 & 1}, \quad
H = \mat{0 & 1 \\ -1 & 0}. \]
We again have $H^{⋆} = H$, and $Y = \mat{u & v\\-v & u}$~commutes
with~$H$.
However, $Z = B · Y · \transpose{Y} · B^{-1} = \mat{d & 0 \\ 0 & d} = W^2$
where $W = \mat{0 & d \\ 1 & 0}$ (or any of its conjugates).
We now easily check that
$X = Y · W^{-1}$~is not a solution of the IP1S problem.

% In the real case, the ``polar decomposition'' method computes the
% square root of the matrix~$Z$ by analytic interpolation on its spectrum;
% this root then belongs to the algebra~$k[Z]$
% and therefore commutes with any matrix commuting with~$Z$.
% In the case above, since $Z = d · 1_{2}$ with~$d = u^2 + v^2 ≥ 0$,
% the analytic interpolation will compute one of the roots~$±√{d} · 1_2$.
% The square root~$W$ we give above does not belong to the algebra~$k[Z]$,
% thus making this method fail.
% 

\paragraph{Decisional IP1S and extensions of scalars.}

Over a tower of real quadratic extensions of~$k$,
a version of both claims above becomes true,
as was noticed in~\cite[6.1]{2013bfp}.
This raises the following question: given a field~$k$,
for which extensions~$k'$ of~$k$ is it true that
any two pencils that are IP1S-equivalent over~$k'$
are always equivalent over~$k$?

The structure given by Propositions~\ref{prop:kronecker-decomposition}
and~\ref{prop:primary} gives a simple answer.
Namely, since the Kronecker degrees are invariant by extension of scalars,
any totally singular pencils which are $k'$-equivalent are $k$-equivalent.
On the other hand, two regular pencils are $k$-equivalent
if and only if, for all primary factors~$R =k[λ]/p(λ)^e$,
the corresponding bilinear forms on~$k[λ]/p(λ)$ are equivalent,
which means that all squares in~$k'[λ]/p(λ)$
are squares in~$k[λ]/p(λ)$.
Therefore the answer is positive exactly when
the extension degree~$[k':k]$ is odd.
This excludes the case where $k'$~is a
real quadratic extension of~$k$.

% For any irreducible polynomial~$f$ factoring over~$k'$ as~$f = ∏ f_i$,
% we have $L_{f,ℓ,u} ⊗_{k} k' = ∏ L_{f_i, ℓ, u'_i}$,
% where $u'_i$~is the image of~$u$
% by the projection map~$k[x]/f(x) → k'[x]/f_i(x)$.
% This implies that $\bm{a}$ and~$\bm{b}$ are equivalent over~$k$
% if and only if, for all irreducible factors~$f$, they have the same value
% $u_{(f, ℓ)} (\bm{a}) = u_{(f, ℓ)} (\bm{b}) ∈ K_f^{×}/(K_f^{×})^2$,
% where $K_f = k[x]/f(x)$~is the extension of~$k$ generated by~$f$.
% Since the norm map defines
% an isomorphism~$K_f^{×}/(K_f^{×})^{2} → k^{×} / (k^{×})^2$,
% this condition is equivalent to: $\bm{a}$ and~$\bm{b}$ have the same
% characters~$χ_{f,ℓ} (\bm{a}) = N_{K_f/k} (u_{(f,ℓ)} (\bm{a}))$.

% For an irreducible polynomial~$f$, we have
% \begin{equation}\label{local-extension}
% L_{f,ℓ,u} ⊗_{k} k' = %\begin{cases}
% %L_{p,d,u'},&\text{if $p$~is irreducible over~$k'$;}\\
% ⨁ L_{f_i, ℓ,u'}, %&
% \text{if $f$~splits as~$∏_i f_i$ over~$k'$,}
% %\end{cases}
% \end{equation}
% where $u'$~is the image in~$k'^{×}/(k'^{×})^2$ of~$u$. The
% map~$k^{×}/(k^{×})^2 → k'^{×}/(k'^{×})^2$ is bijective when $[k':k]$~is
% odd and zero when it is even. From this we deduce:
% 
% \begin{prop}\label{prop:IP1S-extension}
% Let~$\bm{a}, \bm{b}$ be two pencils which are IP1S-equivalent over a
% field extension~$k'$ of the finite field~$k$.
% \begin{enumerate}
% \item If the degree~$[k':k]$~is odd, then $\bm{a}$ and~$\bm{b}$ are
% equivalent over~$k$.
% \item If the degree~$[k':k]$~is even, them $\bm{a}$ and~$\bm{b}$ are
% equivalent over~$k$ iff, for all local factors~$L_{f,ℓ,u}$, they have the
% same value~$u(f,ℓ) ∈ k^{×}/(k^{×})^2$.
% \end{enumerate}
% \end{prop}

% In particular, when $k → k'$~has even degree,
% solving the IP1S problem over~$k'$
% does not, in general, solve the decisional form of IP1S over~$k$.
For example, let~$a ∈ k$ and define the two-dimensional
quadratic pencils~$(A,B) = (2 x y, x^2 + a y^2)$
and~$(A', B') = (x^2 + y^2/a, 2 x y)$.
These two pencils are equivalent only over a field
containing a root of the equation~$x^4 + 4 a = 0$.
In general, they are inequivalent over~$k$
but equivalent over an extension of degree~$4$ of~$k$.

% Although this fact is easy to check by hand,
% we also provide an interpretation using our work.
% The characteristic endomorphism of~$\bm{b}$ is
% \begin{equation*}
% c = -\mat{0&1\\1&0}^{-1} · \mat{1&0\\0&a} \;=\; \mat{0 & -a\\-1 & 0};
% \end{equation*}
% its characteristic polynomial is~$x^2 - a$.
% Let~$R = k[c]$.
% The space~$V = k^2$ is cyclic as a $R$-module and generated by the
% vector~$e = \def\arraystretch{.5}\mat{1\\0}$,
% with~$c · e = \def\arraystretch{.5}\mat{0\\-1}$.
% Since $R$~is a separable $k$-algebra,
% we may apply Prop.~\ref{prop:trace-ext} even when it is not a field.
% Let~$b_R = (x, y) ↦ b_R x y$ be the lift of~$b_{∞}$ to~$R$; then
% \begin{equation}
% \Tr_{R/k} b_R = b_{∞} (e, e) = 0
% \quad\text{and}\quad
% \Tr_{R/k} (c b_R) = b_{∞} (e, c·e) = -1,
% \end{equation}
% which means that~$b_R = -\frac{1}{2 a} c$.
% 
% The same computations for the pencil~$\bm{b'}$
% yield~$k[c'] ≃ k[c]$ and~$b'_R = \frac{1}{2}$.
% Therefore, the pencils~$\bm{b}$ and~$\bm{b'}$
% are isomorphic exactly over the extensions~$k'$ of~$k$
% where $b'_R/b_R = -c$~is a square.
% When writing~$-c = (u/2 + v c)^{2}$,
% this means that $u^4 + 4 a = 0$ as above.
% Depending on the precise value of~$a$, the pencils~$\bm{b}$ and~$\bm{b'}$
% may become isomorphic over an extension of degree~$1$, $2$ or~$4$ of~$k$.
%