style="font-variant:small-caps;">LIP6</span>, F-75005, Paris, France'
- '<span style="font-variant:small-caps;">CNRS</span>, <span style="font-variant:small-caps;">UMR 7606</span>, <span style="font-variant:small-caps;">LIP6</span>, F-75005, Paris, France'
- '<span style="font-variant:small-caps;">INRIA</span>, Équipe <span style="font-variant:small-caps;">PolSys</span>, Centre Paris – Rocquencourt, F-75005, Paris, France'
author:
- Jérémy Berthomieu
- 'Jean-Charles Faugère'
- Ludovic Perret
bibliography:
- 'main.bib'
title: 'Polynomial-Time Algorithms for Quadratic Isomorphism of Polynomials: The Regular Case'
---

Quadratic forms ,computer algebra ,polynomial isomorphism ,multivariate cryptography ,module isomorphism

12Y05 ,94A60 ,68W20 ,68W30 ,68Q25

Introduction
============

A fundamental question in computer science is to provide algorithms allowing to test if two given objects are *equivalent* with respect to some transformation. In this paper, we consider equivalence of nonlinear polynomials in several variables. Equivalence of polynomials has profound connections with a rich variety of fundamental problems in computer science, ranging – among others topics – from cryptography (*e.g.* [@DBLP:conf/eurocrypt/Patarin96; @DBLP:conf/nss/TangX12; @Tang2014; @DBLP:conf/ispec/YangTY11]), arithmetic complexity (*via* Geometric Complexity Theory (GCT) for instance, see [@DBLP:conf/coco/Burgisser12; @DBLP:conf/stoc/Kayal12; @DBLP:journals/cacm/Mulmuley12; @DBLP:journals/siamcomp/MulmuleyS01]), testing low degree affine-invariant properties  ([@DBLP:conf/soda/BhattacharyyaFL13; @DBLP:journals/cdm/GreenT09; @DBLP:journals/eccc/BhattacharyyaGRS11], $\ldots$). As we will see, the notion of equivalence can come with different flavours that impact the intrinsic hardness of the problem considered.

In [@DBLP:conf/stacs/AgrawalS06; @Saxena2006], the authors show that Graph Isomorphism reduces to equivalence of cubic polynomials with respect to an invertible 