论文标题
用于测试多项式，代数和多线性形式的同构的平均案例算法
Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms
论文作者
论文摘要
我们研究了多项式，代数和多线性形式的同构测试问题。我们的第一个主要结果是这些问题的平均案例算法。例如，我们开发了一种算法，该算法采用两个立方体表单$ f，g \ in \ mathbb {f} _q [x_1，\ dots，x_n] $，并且决定$ f $ and $ g $在时间上是同构成的$ q^{o（n）} $，对于最多$ f $。自1990年代以来，这种平均案例设置具有直接的实际含义，在多元密码学上进行了研究。我们的第二个结果涉及测试交替三线性形式的等效性的复杂性。这个问题在数学和密码学上都引起了人们的关注。我们表明，这个问题是多项式时间等同于测试对称三线性形式的等效性，通过表明它们都是张张量同构完全完整的（Grochow-qiao，ITCS，2021），因此等同于在大多数领域测试Cobic形式的同构。
We study the problems of testing isomorphism of polynomials, algebras, and multilinear forms. Our first main results are average-case algorithms for these problems. For example, we develop an algorithm that takes two cubic forms $f, g\in \mathbb{F}_q[x_1,\dots, x_n]$, and decides whether $f$ and $g$ are isomorphic in time $q^{O(n)}$ for most $f$. This average-case setting has direct practical implications, having been studied in multivariate cryptography since the 1990s. Our second result concerns the complexity of testing equivalence of alternating trilinear forms. This problem is of interest in both mathematics and cryptography. We show that this problem is polynomial-time equivalent to testing equivalence of symmetric trilinear forms, by showing that they are both Tensor Isomorphism-complete (Grochow-Qiao, ITCS, 2021), therefore is equivalent to testing isomorphism of cubic forms over most fields.
