Constructive Membership Testing in Black-Box Classical Groups

Sophie Ambrose, Scott Murray, Cheryl Praeger, Csaba Schneider

Research output: A Conference proceeding or a Chapter in BookConference contribution

3 Citations (Scopus)

Abstract

The research described in this note aims at solving the constructive membership problem for the class of quasisimple classical groups. Our algorithms are developed in the black-box group model (see [HCGT, Section 3.1.4]); that is, they do not require specific characteristics of the representations in which the input groups are given. The elements of a black-box group are represented, not necessarily uniquely, as bit strings of uniform length. We assume the existence of oracles to compute the product of two elements, the inverse of an element, and to test if two strings represent the same element. Solving the constructive membership problem for a black-box group G requires to write every element of G as a word in a given generating set. In practice we write the elements of G as straight-line programs (SLPs) which can be viewed as a compact way of writing words; see [HCGT, Section 3.1.3]
Original languageEnglish
Title of host publicationMathematical Software – ICMS 2010
Subtitle of host publicationThird International Congress on Mathematical Software, Kobe, Japan, September 13-17, 2010. Proceedings
EditorsKomei Fukuda, Joris van der Hoeven, Michael Joswig, Nobuki Takayama
Place of PublicationHeidelberg, Germany
Pages54-57
Number of pages4
Volume6327
ISBN (Electronic)978-3-642-15582-6
DOIs
Publication statusPublished - 2010
EventInternational Congress on Mathematical Software ICMS2010 - Kobe, Kobe, Japan
Duration: 13 Sep 201017 Sep 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Congress on Mathematical Software ICMS2010
Abbreviated titleICMS2010
CountryJapan
CityKobe
Period13/09/1017/09/10

Fingerprint

Classical Groups
Black Box
Testing
Strings
Straight-line Programs
Generating Set
Model

Cite this

Ambrose, S., Murray, S., Praeger, C., & Schneider, C. (2010). Constructive Membership Testing in Black-Box Classical Groups. In K. Fukuda, J. van der Hoeven, M. Joswig, & N. Takayama (Eds.), Mathematical Software – ICMS 2010: Third International Congress on Mathematical Software, Kobe, Japan, September 13-17, 2010. Proceedings (Vol. 6327, pp. 54-57). (Lecture Notes in Computer Science). Heidelberg, Germany. https://doi.org/10.1007/978-3-642-15582-6_11
Ambrose, Sophie ; Murray, Scott ; Praeger, Cheryl ; Schneider, Csaba. / Constructive Membership Testing in Black-Box Classical Groups. Mathematical Software – ICMS 2010: Third International Congress on Mathematical Software, Kobe, Japan, September 13-17, 2010. Proceedings. editor / Komei Fukuda ; Joris van der Hoeven ; Michael Joswig ; Nobuki Takayama. Vol. 6327 Heidelberg, Germany, 2010. pp. 54-57 (Lecture Notes in Computer Science).
@inproceedings{23069de5c28a4fe7a8fda83a7390b5d0,
title = "Constructive Membership Testing in Black-Box Classical Groups",
abstract = "The research described in this note aims at solving the constructive membership problem for the class of quasisimple classical groups. Our algorithms are developed in the black-box group model (see [HCGT, Section 3.1.4]); that is, they do not require specific characteristics of the representations in which the input groups are given. The elements of a black-box group are represented, not necessarily uniquely, as bit strings of uniform length. We assume the existence of oracles to compute the product of two elements, the inverse of an element, and to test if two strings represent the same element. Solving the constructive membership problem for a black-box group G requires to write every element of G as a word in a given generating set. In practice we write the elements of G as straight-line programs (SLPs) which can be viewed as a compact way of writing words; see [HCGT, Section 3.1.3]",
author = "Sophie Ambrose and Scott Murray and Cheryl Praeger and Csaba Schneider",
year = "2010",
doi = "10.1007/978-3-642-15582-6_11",
language = "English",
isbn = "978-3-642-15581-9",
volume = "6327",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "54--57",
editor = "Fukuda, {Komei } and {van der Hoeven}, {Joris } and Joswig, {Michael } and Takayama, {Nobuki }",
booktitle = "Mathematical Software – ICMS 2010",

}

Ambrose, S, Murray, S, Praeger, C & Schneider, C 2010, Constructive Membership Testing in Black-Box Classical Groups. in K Fukuda, J van der Hoeven, M Joswig & N Takayama (eds), Mathematical Software – ICMS 2010: Third International Congress on Mathematical Software, Kobe, Japan, September 13-17, 2010. Proceedings. vol. 6327, Lecture Notes in Computer Science, Heidelberg, Germany, pp. 54-57, International Congress on Mathematical Software ICMS2010, Kobe, Japan, 13/09/10. https://doi.org/10.1007/978-3-642-15582-6_11

Constructive Membership Testing in Black-Box Classical Groups. / Ambrose, Sophie; Murray, Scott; Praeger, Cheryl; Schneider, Csaba.

Mathematical Software – ICMS 2010: Third International Congress on Mathematical Software, Kobe, Japan, September 13-17, 2010. Proceedings. ed. / Komei Fukuda; Joris van der Hoeven; Michael Joswig; Nobuki Takayama. Vol. 6327 Heidelberg, Germany, 2010. p. 54-57 (Lecture Notes in Computer Science).

Research output: A Conference proceeding or a Chapter in BookConference contribution

TY - GEN

T1 - Constructive Membership Testing in Black-Box Classical Groups

AU - Ambrose, Sophie

AU - Murray, Scott

AU - Praeger, Cheryl

AU - Schneider, Csaba

PY - 2010

Y1 - 2010

N2 - The research described in this note aims at solving the constructive membership problem for the class of quasisimple classical groups. Our algorithms are developed in the black-box group model (see [HCGT, Section 3.1.4]); that is, they do not require specific characteristics of the representations in which the input groups are given. The elements of a black-box group are represented, not necessarily uniquely, as bit strings of uniform length. We assume the existence of oracles to compute the product of two elements, the inverse of an element, and to test if two strings represent the same element. Solving the constructive membership problem for a black-box group G requires to write every element of G as a word in a given generating set. In practice we write the elements of G as straight-line programs (SLPs) which can be viewed as a compact way of writing words; see [HCGT, Section 3.1.3]

AB - The research described in this note aims at solving the constructive membership problem for the class of quasisimple classical groups. Our algorithms are developed in the black-box group model (see [HCGT, Section 3.1.4]); that is, they do not require specific characteristics of the representations in which the input groups are given. The elements of a black-box group are represented, not necessarily uniquely, as bit strings of uniform length. We assume the existence of oracles to compute the product of two elements, the inverse of an element, and to test if two strings represent the same element. Solving the constructive membership problem for a black-box group G requires to write every element of G as a word in a given generating set. In practice we write the elements of G as straight-line programs (SLPs) which can be viewed as a compact way of writing words; see [HCGT, Section 3.1.3]

U2 - 10.1007/978-3-642-15582-6_11

DO - 10.1007/978-3-642-15582-6_11

M3 - Conference contribution

SN - 978-3-642-15581-9

VL - 6327

T3 - Lecture Notes in Computer Science

SP - 54

EP - 57

BT - Mathematical Software – ICMS 2010

A2 - Fukuda, Komei

A2 - van der Hoeven, Joris

A2 - Joswig, Michael

A2 - Takayama, Nobuki

CY - Heidelberg, Germany

ER -

Ambrose S, Murray S, Praeger C, Schneider C. Constructive Membership Testing in Black-Box Classical Groups. In Fukuda K, van der Hoeven J, Joswig M, Takayama N, editors, Mathematical Software – ICMS 2010: Third International Congress on Mathematical Software, Kobe, Japan, September 13-17, 2010. Proceedings. Vol. 6327. Heidelberg, Germany. 2010. p. 54-57. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-15582-6_11