Root computation problem

From Groupprops
Jump to: navigation, search

Definition

The root 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 and an integer m such that we are promised that the group is powered over all primes dividing m, so every element has a unique m^{th} root. In the finite case, this is equivalent to requiring that m is relatively prime to the order of the group. The goal is to find the unique h such that h^m = g. Note that uniqueness follows from the fact that kth power map is bijective iff k is relatively prime to the order.

Related problems

Relation with cryptography

The RSA algorithm is based on the idea that the root computation problem is much harder than the power computation problem if the order of the group is unknown. Thus, we can perform encryption by computing a power (with a "public encryption key" specifying what power to compute) but decryption is still hard if the order of the group is unknown.

Solution

Solution dependent on power computation and order-finding