Encoding of external direct product in terms of encodings of direct factors
Contents
Statement
This article describes how to construct an encoding of the external direct product given separate encodings of and . Note that the nature of the encodings for and may be quite different.
For instance, may have a permutation encoding and may have a linear encoding. This does not matter -- we will still get an encoding of albeit it will be neither a permutation encoding nor a linear encoding.
Encoding method
New code-words
The idea is to encode by combining the code-words for and . 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 , then the comma separator, then the code-word for .
- Harder but in some cases more useful possibility: Alternate the code-word letters for and .
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 in and in . Just output the element . |
group multiplication | Consider two input code-words and that need to be multiplied. First, parse to recover the code-words for . Then, compute the products and . Finally, output . |
inverse | Parse the code-word for to get code-words for and . Use the inversion algorithms within the groups and to find code-words for and . Finally, output . |
membership test | Parse the code-word for to obtain the code-words for and . Then, check whether is a valid code-word for and also whether is a valid code-word for . |
Additional algorithms
Shorthand for algorithm | Description of algorithm for in terms of algorithms for and separately |
---|---|
list all group elements (also called an enumeration algorithm) | We use for the outer traversal loop and for the inner traversal loop. For each element , list all pairs for all . |
order of the whole group | multiply the known orders of and . See order of direct product is product of orders |
uniform random sampling from the whole group | we can use separate uniform random samplers for and and then output the element we obtain by combining the answers: if the random element of is and the random element of is , the random element of is . |
algorithm for the power computation problem | Carry out the power computations separately in each coordinate. Explicitly, to find , compute and 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). |
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 in terms of multi-encodings of and . 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.