- multiply two elements;
- invert an element;
- test whether an element is the trivial element;
- compute the order of an element (the order oracle);
- find a pseudo-random element (the random element oracle)

- Algorithms to find standard generators of a given group. These are available in a computer-readable format in files named Group
*[n]*-find*[m]*. - Algorithms to check whether elements of a given group are standard generators. These are available in a computer-readable format in files
named Group
*[n]*-check*[m]*.

The file M22d2G1-find1 finds
a pair of standard generators for M_{22}.2.

The file LyG1-check1 checks that a pair of elements of Ly is a pair of standard generators.

The language (BBOX) we use to implement black box algorithms is described below. An interpreter for this language can be found at the BBOX Interpreter page.

The language is an extension of the language used for straight line programs for making conjugacy class representatives, generators for maximal subgroups and so forth.

As for straight line programs, group elements are labelled by integers. In addition, we allow 26 counters (integer variables) labelled A to Z.

Each command should appear on a separate line. Anything after a '#' symbol is a comment and is to be ignored.

- oup [n] [g1] ... [gn]
- Output a list of n group elements and end the program.
- mu g1 g2 g3
- Let the group element g3 be g1 multiplied by g2.
- iv g1 g2
- Let the group element $g_2$ be the inverse of $g_1$.
- pwr n g1 g2
- Let g2 be the nth power of g1. Here n can be a number or a counter.
- cj g1 g2 g3
- Let g3 be g1 conjugated by g2.
- cjr g1 g2
- Conjugate g1 by g2 `in place'.
- com g1 g2 g3
- Let g3 be the commutator of g1 and g2.
- cp g1 g2
- Copy the element g1 into g2.
- rand g1
- Let g1 be a (pseudo-)random element of the group.
- ord g1 c
- Let the counter c be the order of the element g.
- chor g1 n
- Check whether element g has order n. Fail if not.

- lbl L
- Marker for a program label L.
- jmp L
- Jump to the label L.
- call L
- Jump to the label $L$ and record the current position in the callstack. The command 'return' takes the program back. This allows us to implement simple subroutines.
- return
- Return to the location of the most recent 'call' instruction.

- incr
- Increment the counter c.
- decr c
- Decrement the counter c.
- set c n
- Set the counter c to be n.
- add n1 n2 c
- Let the counter c be n1 + n2.
- sub n1 n2 c
- Let the counter c be n1 - n2.
- mul n1 n2 c
- Let the counter c be n1 n2. This command should not be confused with `mu' (which works with group elements).
- div n1 n2 c
- Let the counter c be (the integer part of) n1 / n2.
- mod n1 n2 c
- Let the counter c be the residue of n1 modulo n2.

The single line form is:

```
if predicate then statement
```

The multi-line form is:

```
if predicate then
```

statements

elseif predicate then

statements

else

statements

endif

Nested if-statements are only allowed with the multiline form.

Predicates take one of the following forms:

- c eq n
- Counter c is equal to n
- c noteq n
- Counter c is not equal to n
- c in n1 n2 ... nk
- Counter c is one of n1, n2, ... nk
- c notin n1 n2 ... nk
- Counter c is not one of n1, n2, ... nk
- c lt n
- Counter c is less than n
- c leq n
- Counter c is less than or equal to n
- c gt n
- Counter c is greater than n
- c geq n
- Counter c is greater than or equal to n

- true
- End the program, and return the boolean value `true' as an answer to a decision problem.
- false
- End the program, and return the boolean value `false' as an answer to a decision problem.
- timeout
- Report that the algorithm has spent `too long' on some task. This may suggest that the incorrect group has been given to the algorithm, or it may just be that we were unlucky. Whether the program actually terminates with a timeout is implementation dependent.
- fail
- End the program, and report that the algorithm has determined that the input given is invalid (\eg the group given is not of the correct isomorphism type). This is a more final mode of failure than that indicated by `timeout'.

Go to main ATLAS (version 2.0) page.

Version 2.0 created on 31st January 2005 by Simon Nickerson.

Last updated 31.01.05 by SJN.