# ATLAS: Black box algorithms

### Black box groups

In this ATLAS, a black box group is an implementation of a group where the following operations are feasible:
• 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)
All the matrix and permutation groups we supply can be thought of as black box groups. A black box algorithm is an algorithm which works with any black box group.

### Black box algorithms provided

We currently provide two types of black box algorithm.
• 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].

#### Examples

The file M22d2G1-find1 finds a pair of standard generators for M22.2.

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

### BBOX: a language for implementing black box algorithms

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.

#### Basics

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.

#### Commands for manipulating group elements

The following commands perform operations with group elements.
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.

#### Commands for jumping and looping

lbl L
Marker for a program label L.
jmp 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

#### Commands for counter arithmetic

incr
Increment the counter c.
decr c
Decrement the counter c.
set c n
Set the counter c to be n.
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.

#### Logical commands

There are two forms for logical commands.

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

#### Terminating commands

As well as the oup command for outputting group elements, there are other commands which can end a program.
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.