~~~ From:

~~~ ~~~ Subject:

Since there seems to be a surge of interest in Shamir's method, I

thought I would mention a few points about it and my implementation

of it:

1. How the group must be represented in order to use Shamir's method.

We suppose that elements of our group G are represented by ordered

tuples, which can be ordered lexicographically; we want to generate

the list ST in this lexicographical order. Suppose that we have an element

s of S, and elements t and u in T which first differ in coordinate i. For

Shamir's method to work, we need to be able to order st and su given

only the length i initial segments of t and u. This is true for

permutation groups if we represent them as acting on {1,...,n}

(st compares to su as s(t(i)) compares to s(u(i)).)

It is also true for the wreath products occurring in the cube group:

suppose G = H wr K, where H is a permutation group acting on {1,...,n},

and K is a product of cyclic groups with index set {1,...,n}. Then

if we write an element g of G as ( g(1), ..., g(n), g'(1), ..., g'(n) ),

the g(i)'s being in {1,...,n} and the g'(i)'s in the cyclic groups,

we can write

( h(1), ..., h(n), h'(1), ..., h'(n) ) ( k(1), ..., k(n), k'(1), ..., k'(n) ) = ( h(k(1)), ..., h(k(n)), h'(k(1)) + k'(1), ..., h'(k(n)) + k'(n) ). Hence if t and u's first difference is in t(i) != u(i), st and su compare as s(t(i)) and s(u(i)), and if t and u's first difference is in t'(i) != u'(i), st and su compare as s'(t(i)) + t'(i) and s'(u(i)) + u'(i).

Since you do a lot of composition in Shamir's method, I felt it best to

leave the permutations unpacked. I used the wreath product representation

above, with H = S_8 x S_12 and K = (Z/3Z)^8 x (Z/2Z)^12. Each permutation

then used 8 + 12 + 8 + 12 = 40 bytes. All members of both S and T must be

stored in memory (see below.) This used up a lot of memory. (You could,

of course, also represent the cube group as a permutation group on the 48

facelets.)

2. The data structure for T.

Jerry Bryan has alluded to this. I used a tree each of whose leaves

contained a member of T, and each of whose internal nodes contained

an index indicating which tuple coordinate was being branched on, a

value of this coordinate for each son, and pointers to each son.

I also included a pointer to the father to make traversal easier.

The data structure for T does not change during the algorithm; you

can use it with more than one S at once.

3. The data structure for S.

By traversing the T tree approriately, we can output the sequence

X(s) = (lexicographical sort of {st | t in T}) for each s. For all elements s

of S, we need to store s itself, and a marker to show our position in X(s)

(for me, this was just a pointer to the T tree.)

We also need enough structure to make merging the X(s)'s easy. I used a

`tree of losers' (cf. Knuth, Chapter 5.) Since there seems to be

some uncertainty about this, I will go into detail. Let S = {s_0, ..., s_(N-1)}.

The tree will then have 2N nodes: N internal ones, 0 through N-1, and N

leaves, N through 2N-1. Each internal node i contains a pointer to a leaf.

The leaves contain the actual s_j's, as well as the pointers to T. Node i

has nodes 2i and 2i+1 as sons if 0<i<N; node 0 has only node 1 for a son.

(Since these relations are fixed, no tree traversal pointers need be stored.)

Leaf N+j always corresponds to s_j. The tree is initialized by conducting an

elimination tournament: the leaves are initialized with the first elements of

the X(s_j)'s, and sons repetitively battle for their fathers, the lesser value

always winning, i.e., initializing the father's pointer. After the tournament

is finished (the overall winner ending up in both nodes 0 and 1) we

simultaneously, for all i=1,...,N-1, reinitialize node i's pointer from its

other son, i.e., the loser of the battle that was just played for node i.

After we do this, each value occurs exactly once in a leaf and once in an

internal node (everybody in a tournament, except the winner, loses exactly one

game.)

The advantage of using losers instead of winners is that it makes updating

the tree easy. Suppose each internal node i points to leaf N + a_i. To

update, we output the first element of X(s_a_0) and advance X(s_a_0). We

can then execute the following loop to update the tree:

i := floor((N + a_0)/2) while i > 0 do if the next element of X(s_a_0) is greater than the next element of X(s_a_i) then swap a_i and a_0 (we have a new loser) i := floor(i/2) od

As you see, we perform many comparisons between the first elements of the

X(s_i)'s. It is convenient to store the next element of X(s_i) in

the data structure with s_i. This uses up much more memory (a comparable

amount with that taken by S and T themselves) but does speed up the program

somewhat.

-- David Moews dmoews@xraysgi.ims.uconn.edu