Root Extraction in Certain Finite Abelian $p$-Groups

Abstract

We formulate a problem called \emph{Generalized Root Extraction} in finite Abelian groups that have more than one generator. We then study this problem for the specific case of the torsion subgroups of elliptic curves. We give a necessary and sufficient condition for the existence of a solution. We also present an algorithm to find a solution. Our algorithm easily generalizes to Abelian groups of prime power order that have a specific structure. We then discuss a variant of this problem called \emph{Simultaneous Root Extraction} and present an algorithm for solving it.

This work appeared as a chapter in the author's Ph.D. thesis, titled Isogeny-based Quantum Resistant Undeniable Blind Signature and Authenticated Encryption Schemes, 2018