journal of Groups, Complexity, Cryptology

In this paper we analyze computational properties of the Diophantine problem (and its search variant) for spherical equations $\prod_{i=1}^m z_i^{-1} c_i z_i = 1$ (and its variants) over the class of finite metabelian groups $G_{p,n}=\mathbb{Z}_p^n \rtimes \mathbb{Z}_p^\ast$, where $n\in\mathbb{N}$ and $p$ is prime. We prove that the problem of finding solutions for certain constrained spherical equations is computationally hard on average (assuming that some lattice approximation problem is hard in the worst case).

• 20F10 - Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
• 20F16 - Solvable groups, supersolvable groups
• 68W30 - Symbolic computation and algebraic computation

• 1 zbMATH Open