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

From Groupprops
Jump to: navigation, search

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_1h_1 and g_2h_2. Finally, output (g_1h_1,g_2h_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.