Encoding of external direct product in terms of encodings of direct factors

Statement

This article describes how to construct an encoding of the external direct product $G_{1}\times G_{2}$ given separate encodings of $G_{1}$ and $G_{2}$. Note that the nature of the encodings for $G_{1}$ and $G_{2}$ may be quite different.

For instance, $G_{1}$ may have a permutation encoding and $G_{2}$ may have a linear encoding. This does not matter -- we will still get an encoding of $G_{1}\times G_{2}$ albeit it will be neither a permutation encoding nor a linear encoding.

Encoding method

New code-words

The idea is to encode $(g_{1},g_{2})$ by combining the code-words for $g_{1}$ and $g_{2}$. How the combination is done depends on our goals. Two possibilities:

• Easier possibility: Introduce a new symbol for a comma separator, then write the new code-word by writing the code-word for $g_{1}$, then the comma separator, then the code-word for $g_{2}$.
• Harder but in some cases more useful possibility: Alternate the code-word letters for $g_{1}$ and $g_{2}$.

Algorithms

The idea behind each algorithm (identity element, multiplication, inversion, and membership test) for the direct product is as follows:

Shorthand for algorithm	How it's executed
identity element	We have algorithms for the identity elements $e_{1}$ in $G_{1}$ and $e_{2}$ in $G_{2}$. Just output the element $(e_{1},e_{2})$.
group multiplication	Consider two input code-words $(g_{1},g_{2})$ and $(h_{1},h_{2})$ that need to be multiplied. First, parse to recover the code-words for $g_{1},g_{2},h_{1},h_{2}$. Then, compute the products $g_{1}h_{1}$ and $g_{2}h_{2}$. Finally, output $(g_{1}h_{1},g_{2}h_{2})$.
inverse	Parse the code-word for $(g_{1},g_{2})$ to get code-words for $g_{1}$ and $g_{2}$. Use the inversion algorithms within the groups $G_{1}$ and $G_{2}$ to find code-words for $g_{1}^{-1}$ and $g_{2}^{-1}$. Finally, output $(g_{1}^{-1},g_{2}^{-1})$.
membership test	Parse the code-word for $(g_{1},g_{2})$ to obtain the code-words for $g_{1}$ and $g_{2}$. Then, check whether $g_{1}$ is a valid code-word for $G_{1}$ and also whether $g_{2}$ is a valid code-word for $G_{2}$.

Additional algorithms

Shorthand for algorithm	Description of algorithm for $G_{1}\times G_{2}$ in terms of algorithms for $G_{1}$ and $G_{2}$ separately
list all group elements (also called an enumeration algorithm)	We use $G_{1}$ for the outer traversal loop and $G_{2}$ for the inner traversal loop. For each element $g_{1}\in G_{1}$, list all pairs $(g_{1},g_{2})$ for all $g_{2}\in G_{2}$.
order of the whole group	multiply the known orders of $G_{1}$ and $G_{2}$. See order of direct product is product of orders
uniform random sampling from the whole group	we can use separate uniform random samplers for $G_{1}$ and $G_{2}$ and then output the element we obtain by combining the answers: if the random element of $G_{1}$ is $g_{1}$ and the random element of $G_{2}$ is $g_{2}$, the random element of $G_{1}\times G_{2}$ is $(g_{1},g_{2})$.
algorithm for the power computation problem	Carry out the power computations separately in each coordinate. Explicitly, to find $(g_{1},g_{2})^{m}$, compute $g_{1}^{m}$ and $g_{2}^{m}$ separately, then combine.
algorithm for the element order-finding problem: computing the order of an element	Compute the orders of the coordinates separately, then compute the least common multiple of the orders (if the orders come equipped with prime factorizations, this is easy; otherwise, use the Euclidean algorithm to compute the gcd and then compute the lcm from that).

Adaptation to related settings

Quasi-encodings

A quasi-encoding of a group is like an encoding, except that we lack a membership test. The construction of the quasi-encoding for the direct product is the same as that described above. The only difference is that we do not have a membership test for the direct product, because we are lacking membership tests for the individual direct factors.

Multi-encodings

A multi-encoding of a group is like an encoding, except that there could be multiple code-words for the same element, and we have a separate equality test to determine whether two code-words represent the same element. We can use the procedure described above to obtain a multi-encoding for $G_{1}\times G_{2}$ in terms of multi-encodings of $G_{1}$ and $G_{2}$. The main difference is that we will need to add in an equality test that would first parse to obtain the coordinates, then check equality coordinate-wise.