Constructive Membership Testing in Black-Box Classical Groups

Sophie Ambrose, Scott Murray, Cheryl Praeger, Csaba Schneider

    Research output: Contribution to journalConference article

    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
    Pages (from-to)54-57
    Number of pages4
    JournalLecture Notes in Computer Science
    Volume6327
    DOIs
    Publication statusPublished - 2010
    EventInternational Congress on Mathematical Software ICMS2010 - Kobe, Kobe, Japan
    Duration: 13 Sep 201017 Sep 2010

    Fingerprint

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

    Cite this

    Ambrose, Sophie ; Murray, Scott ; Praeger, Cheryl ; Schneider, Csaba. / Constructive Membership Testing in Black-Box Classical Groups. In: Lecture Notes in Computer Science. 2010 ; Vol. 6327. pp. 54-57.
    @article{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",
    volume = "6327",
    pages = "54--57",
    journal = "Lecture Notes in Computer Science",
    issn = "0302-9743",
    publisher = "Springer Verlag",

    }

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

    In: Lecture Notes in Computer Science, Vol. 6327, 2010, p. 54-57.

    Research output: Contribution to journalConference article

    TY - JOUR

    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 article

    VL - 6327

    SP - 54

    EP - 57

    JO - Lecture Notes in Computer Science

    JF - Lecture Notes in Computer Science

    SN - 0302-9743

    ER -