Power computation problem

Definition

The power computation problem is a problem usually asked in the context of an encoding of a group or multi-encoding of a group. The input is an element $g$ of the group (in the form of its code-word) and an integer $n$ and the goal is to compute the code-word for $g^{n}$.

Related problems

• Element order-finding problem
• Root computation problem
• Algorithm for group isomorphism problem for abelian groups based on order statistics

Solution

For black-box groups

• Repeated squaring algorithm for power computation

For permutation groups

• Permutation group algorithm for power computation problem