ATLAS: Black box algorithms

Black box groups

• 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

• 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 M₂₂.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

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 simple subroutines.

return

Return to the location of the most recent 'call' instruction.

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.

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.

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

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