Encoding of external direct product in terms of encodings of direct factors
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.
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 .
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 .|
|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).|
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.
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.