CS Paper Radar

On Applications of Polynomial-Time Group Isomorphism Algorithm

Wenkang Zhang, Zhinan Wang, Jincheng Zhuang

cs.CC ·submitted 2026-11-13 12:08 UTC · v1

Abstract

The group isomorphism problem is a fundamental problem in computational group theory and is closely related to many other problems. Recently, Qiao and Zhang proposed a polynomial-time algorithm for finite group isomorphism in the multiplication-table model that computes the coset of all isomorphisms. Based on the algorithm of Qiao and Zhang, we study applications to finite associative ring isomorphism, bilinear map isotopism over finite commutative rings and free three-tensor isomorphism over finite commutative rings. First, we obtain a polynomial-time algorithm that returns the coset of all isomorphisms for finite associative rings. Second, we extend efficient isotopism and isomorphism algorithms for bilinear maps and free three-tensors from fields to general finite commutative rings.

Comment
10 pages

Closest papers

Nearest neighbours by meaning across the whole index.

On the complexity of isomorphism problems for tensors, groups, and polynomials V: over commutative rings

cs.CC math.ACmath.NT ·2026-10-31 ·Joshua A. Grochow, Youming Qiao, Katherine E. Stange, Xiaorui Sun
top venuehighly cited similarity 0.67
Abstract · 74 pages, extended abstract appeared at STOC'25, abstract shortened to meet arXiv requirement

Tensors over commutative rings naturally appear in number theory, geometry, and group theory. For example, $2\times 2\times 2$ tensors over $\mathbb{Z}$ form the starting point of Bhargava's celebrated works generalising Gauss's composition law (Bhargava, Ann. Math., 2004). Symmetric tensors over $\mathbb{Z}$ are central to the classification of Calabi--Yau threefolds (Yau, Commun. Pure Appl. Math., 1978; Wall, Invent. Math., 1966), geometric objects of significance in string theory. Additionally, tensors over finite commutative rings closely correspond to finite nilpotent groups of class 2 (Baer, Trans. Am. Math. Soc., 1938). In this work, we study isomorphism testing of tensors over commutative rings from a complexity-theoretic viewpoint, and its applications. Some of our main results are: 1. Let $\mathrm{R}$ be a commutative ring. We introduce two complexity classes: $\mathsf{3TI}_\mathrm{R}$ consisting of problems that are polynomial-time reducible to isomorphism problems of tensor products of three modules over $\mathrm{R}$, and $\mathsf{3FTI}_\mathrm{R}$ consisting of problems that are polynomial-time reducible to isomorphism problems of tensor products of three free modules over $\mathrm{R}$. 2. We show that some classical problems considered by Grunewald and Segal (ibid.), and the problem of classifying Calabi--Yau threefolds, are $\mathsf{3FTI}_\mathbb{Z}$-complete. We also show that many natural problems are complete for $\mathsf{3TI}_{\mathbb{Z}/p^e\mathbb{Z}}$. 3. We show that testing isomorphism of tensors in $\mathbb{Z}^2\otimes\mathbb{Z}^2\otimes\mathbb{Z}^2$ is polynomial-time equivalent to the principal ideal problem in algorithmic number theory. 4. We present an $N^{O((\log N)^{8/9})}$-time algorithm for testing isomorphism of finite nilpotent groups of class $2$ and odd order $N$.

0.73

Integral Tensor Isomorphism via Cubic Rings and Lattice Methods

cs.CC quant-ph ·2026-11-17 ·Thomas Huffstutler
theory similarity 0.57
Abstract · 51 pages

We prove that isomorphism of integral $2\times3\times3$ tensors under $\mathrm{GL}_2(\mathbb{Z})\times\mathrm{GL}_3(\mathbb{Z})\times\mathrm{GL}_3(\mathbb{Z})$ is decidable in bounded-error quantum polynomial time. For a tensor $T=(A,B)$ with nonzero determinant form $\det(xA-yB)$, we use the parametrization of Wood by balanced modules to reduce the isomorphism problem to principality tests for compatible lattices, and use the algorithms of Bley, Hofmann, and Johnston to solve this in BQP. When the determinant form vanishes identically, we get either an integral $2\times2\times2$ core, or a polynomial kernel vector of degree one or two. The linear-kernel case yields another compatible lattice problem, while the quadratic-kernel case reduces to a fixed system of polynomial congruences and unimodular lifting. A quantifier-elimination argument decides these congruences in deterministic polynomial time given the prime factorization of the modulus, which quantum integer factorization supplies. Finally, we show that zero padding preserves integral $2\times2\times2$ tensor isomorphism, yielding a polynomial-time reduction from real-quadratic principality to the identically singular $2\times3\times3$ problem.

0.39

Algorithms for Finite Group Epimorphism Testing

cs.DS cs.CCmath.GR ·2026-09-07 ·Joshua A. Grochow, Pranjal Srivastava, Dhara Thakkar
top venue similarity 0.57
Abstract · 19 pages, A preliminary version of this article appeared in the proceedings of the 53rd EATCS International Colloquium on Automata, Language…

The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about its complexity for structured classes of finite groups. In this paper, we study the computational complexity of GpEpi for several well-studied classes of finite groups. Our main results are polynomial-time epimorphism tests for several classes of groups for which polynomial-time isomorphism testing was previously known: Groups with Abelian normal Hall subgroups with cyclic complement; Groups with (product of) elementary Abelian normal Hall subgroup with elementary Abelian complement; and Groups with some constraints on their Abelian chief factors.

0.63

Tensor--Action Ko--Lee Cryptography: A Framework and Structural Cryptanalysis of Commuting Subgroup Constructions

cs.CR ·2026-08-15 ·Ziyan Chen, Yuqiao Wang
similarity 0.54
Abstract · 28 pages, 3 images, 1 table

Tensor isomorphism has been studied as an algebraic problem relevant to post-quantum cryptography, while its use in public-key encryption remains open. In this paper, we formulate a Ko--Lee-style framework for public-key encryption from cubic tensor actions and prove its formal correctness. We then show that the framework is generically insecure when the commuting matrix subgroups are given by public finite generating sets. Viewing a cubic tensor as a vector in a $d^3$-dimensional space, a linear decomposition attack recovers the shared tensor from the public transcript in polynomial time without recovering either secret action. We also cryptanalyze three natural commuting-subgroup constructions---field-extension, block-diagonal, and tensor-product constructions---and give toy-scale experiments illustrating their specific structural leakage. Finally, we examine the lower-dimensional leakage caused by scaled-block structure. The contribution is therefore a framework proposal together with its cryptanalysis; it does not provide a secure public-key encryption scheme.

0.10

Quasilinear multiplication in the Cayley-Dickson tower

cs.SC math.RAmath.NA ·2026-09-10 ·Harrison Lemley
code/data similarity 0.53
Abstract · 28 pages, 2 tables. v2: title changed from 'Quasilinear multiplication in the real Cayley--Dickson tower'; results generalized from $\mathbb…

Direct evaluation of the defining product of the Cayley-Dickson algebra $A_n$ of rank $N:=2^n$ over a unital commutative ring $R$ in which $2$ is invertible requires a quadratic number of arithmetic operations. This paper gives a uniform bilinear algorithm for multiplication in this algebra costing $O(N \log N)$ arithmetic operations in $R$ and $O(N)$ auxiliary storage when the doubling parameters of $A_n$ are units whose square roots lie in a fixed commutative coefficient algebra $S$ finitely generated as an $R$-module and admitting an $R$-linear map $π\colon S \to R$ with $π(1) = 1$. In particular, over $\mathbb{R}$ and every finite field $\mathbb{F}_{q}$ of odd characteristic, a quadratic field extension contains a square root of every possible doubling parameter, so the algorithm applies to every Cayley-Dickson tower over these fields, and the tensor rank of multiplication in $A_n$ over them is at most $(9n-21)2^n+28$ when $n\ge2$. When the top doubling parameter is a non-square, as in the standard real tower, the bound is $(9n-15)2^{n-1}+10$. To the author's knowledge, the algorithm presented in this paper is the first uniform subquadratic algorithm for multiplication in $A_n$. When $R=\mathbb{R}$ with every doubling parameter equal to $-1$, the real quasilinear schedule uses fewer total arithmetic operations than both direct multiplication and a uniform algorithm of Cariow-Cariowa for $n\ge4$. An implementation for the standard real tower is available in the MIT-licensed C11 library fastCD, with a NumPy-backed Python interface. In single-core benchmarks against direct multiplication and the uniform Cariow-Cariowa method, the quasilinear implementation had the lowest mean time of the three at every tested dimension $N\ge32$, for both single and batched products, and was over $17$ times faster than direct multiplication at $N=1024$.

0.34

Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness

cs.CR quant-ph ·2026-09-07 ·Bhanwar Gupta
theory similarity 0.53
Abstract · 29 pages, 7 tables, 5 figures

Several public-key schemes base their security on the belief that inverting a unit of a group ring is hard. A recent result showed that this belief is false on a quantum computer when the group is abelian. To restore security, designers moved to non-abelian groups, especially dihedral groups, believing that the hardness of the dihedral hidden subgroup problem (HSP) would protect the scheme. This paper shows that unit inversion is a different problem and does not require an HSP solver. Instead, it can be solved by a change of basis that splits the group ring into small matrix blocks. We prove that unit inversion is polynomial-time, classically and quantumly, when an efficient generalized Fourier transform exists, the group ring is semisimple, and the largest matrix block has polynomial size. Dihedral group rings satisfy these conditions because their irreducible representations have dimension at most 2 and an efficient Fourier transform exists. We give an explicit reversible quantum circuit for the block-inversion step and validate it in a register-level simulator. We also identify the exact structural boundary where the method stops and propose a candidate construction in the surviving regime under a new, clearly stated security assumption. The constructive results are supported by reproducible software artifacts and experiments.

0.27

Standard bases for shift-stable groups and Subgroup Membership in wreath products

cs.SC math.GR ·2026-08-25 ·Ruiwen Dong
theory similarity 0.53
Abstract · added a consequence of Theorem 1.2, plus other minor changes

We develop a notion of standard bases for subgroups of the restricted direct product $G^{(\mathbb{N}^n)}$ that are stable under translation by $\mathbb{N}^n$, where $G$ is an arbitrary finite group. We construct an algorithm that computes standard bases for such subgroups and use them to solve several algorithmic problems, including membership, saturation, and variable elimination. Our approach is inspired by Buchberger's algorithm and the theory of Gröbner bases for ideals in polynomial rings. Building on the standard bases and our solutions to the algorithmic problems above, we prove that Subgroup Membership is decidable in wreath products $G \wr \mathbb{Z}^n$ for finite $G$ and $n \in \mathbb{N}$.

0.44

The rank of 3x3 matrix multiplication over F2 is 23

cs.CC math.RA ·2026-10-08 ·Tejasvi Singh Tomar
theorycode/data similarity 0.52
Abstract · 18 pages. Kernel-only Lean proof: https://github.com/tejasvi/rank333-f2-kernel (archived at https://doi.org/10.5281/zenodo.23304899). Lean p…

The rank of the tensor of $3\times 3$ matrix multiplication over the field with two elements is at most $23$ by Laderman's algorithm, and Rudich and Rousseau recently proved that it is at least $22$. We prove that it equals $23$. Hence Laderman's algorithm uses the fewest multiplications among all bilinear algorithms over $\mathbb{F}_2$ and among all bilinear algorithms with integer coefficients. The proof uses the substitution method in the form developed by D'Ambrosio, Wang and Yang et al., which bounds the number of first factors of a decomposition that lie in a given subspace of the space of first factors. We sharpen these bounds for $111$ of Wang's $496$ classes of subspaces, constrain the ranks of the first factors through a $27\times 27$ flattening of the tensor, and list, up to symmetry, all sets of $22$ first factors that satisfy these constraints. An exact completion search shows that none of them is the set of first factors of a decomposition. The computation emits certificates, which are checked in the Lean 4 proof assistant. In one formal proof the largest checks are evaluated as compiled code, and in a second one the kernel evaluates every check, so that its final theorem depends only on the three standard axioms of Lean. The Lean proofs build on the formalization of Rudich and Rousseau and import their table of bounds and their reduction for block algorithms.

0.22