Black-box group algorithm

From Groupprops
Jump to: navigation, search

Definition

A black-box group algorithm is an algorithm involving a group described by an encoding, that treats all the group operations as well as the membership testing in the group, as oracle queries. In other words, it solves whatever problem we are considering in terms of oracle queries to the group operations and any pre-processing or post-processing that needs to be done.

Any black-box group algorithm gives an actual algorithm if we are actually provided an encoding. The actual algorithm is obtained by replacing each of the oracle queries with an actual subroutine call that does the relevant computation.

Thus, the time taken by the actual algorithm is obtained as the time taken by the black-box algorithm, plus the time taken for each kind of query, multiplied by the number of times that query is made.

Note that black-box group algorithms cannot exploit any special properties of a particular encoding of the group.

Measures of complexity

Query complexity

The query complexity of a black-box group algorithm is defined as the number of queries made to the oracle. Since there are different kinds of queries, we can associate query complexities for each kind of query.

The problem of finding black-box group algorithms that minimize the query complexity is an important problem, because such algorithms will work well even for encodings which are inefficient (in the sense that the multiplication and inversion may take a lot of time).

Total complexity

Since the black-box group algorithm involves both oracle queries and other computation, the total complexity cannot directly be computed. However, we can usually compute the total complexity as a linear combination of the complexity for each query, and a constant number (in other words, this gives a number when we put particular values for each of the query complexities).

Promise problems

A promise problem in the context of black-box group algorithms is a problem where we are given a promise that the black-box group satisfies some property upto isomorphism. For instance, we may actually be told the isomorphism type of the group, but we may not be given an explicit isomorphism from the group to a white-box group of that type. This situation is fairly common; for instance, given a prime number p, we know that the multiplicative group modulo p (i.e., the multiplicative group of the finite field \mathbb{F}_p) is isomorphic to the cyclic group of order p-1.