Alexander Ushakov - Constrained inhomogeneous spherical equations: average-case hardness

gcc:13555 - journal of Groups, complexity, cryptology, July 9, 2024, Volume 16, Issue 1 - https://doi.org/10.46298/jgcc.2024.16.1.13555
Constrained inhomogeneous spherical equations: average-case hardnessArticle

Authors: Alexander Ushakov

    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).


    Volume: Volume 16, Issue 1
    Published on: July 9, 2024
    Accepted on: July 6, 2024
    Submitted on: May 7, 2024
    Keywords: Mathematics - Group Theory,20F16, 20F10, 68W30

    Consultation statistics

    This page has been seen 582 times.
    This article's PDF has been downloaded 201 times.