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

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