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:
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.
- 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)
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
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.
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
- 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
- Return to the location of the most recent 'call' instruction.
Commands for counter arithmetic
- 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.
There are two forms for logical commands.
The single line form is:
if predicate then statement
The multi-line form is:
if predicate then
elseif predicate then
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
As well as the oup command for outputting group elements, there
are other commands which can end a program.
- End the program, and return the boolean value `true' as an answer to
a decision problem.
- End the program, and return the boolean value `false' as an answer to
a decision problem.
- 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.
- 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.