Constructive homomorphisms for classical groups

Scott Murray, Colva Roney-Dougal

    Research output: Contribution to journal › Article

    4 Citations (Scopus)

    Abstract

    Let be a quasisimple classical group in its natural representation over a finite vector space , and let . We construct the projection from to and provide fast, polynomial-time algorithms for computing the image of an element. Given a discrete logarithm oracle, we also represent as a group with at most 3 generators and 6 relations. We then compute canonical representatives for the cosets of . A key ingredient of our algorithms is a new, asymptotically fast method for constructing isometries between spaces with forms. Our results are useful for the matrix group recognition project, can be used to solve element conjugacy problems, and can improve algorithms to construct maximal subgroups.
    Original languageEnglish
    Pages (from-to)371-384
    Number of pages14
    JournalJournal of Symbolic Computation
    Volume46
    DOIs
    Publication statusPublished - 2011

    Fingerprint

    Classical Groups
    Homomorphisms
    Conjugacy Problem
    Discrete Logarithm
    Matrix Groups
    Maximal Subgroup
    Coset
    Isometry
    Polynomial-time Algorithm
    Vector space
    Projection
    Generator
    Vector spaces
    Computing
    Polynomials
    Form

    Cite this

    Murray, Scott ; Roney-Dougal, Colva. / Constructive homomorphisms for classical groups. In: Journal of Symbolic Computation. 2011 ; Vol. 46. pp. 371-384.
    @article{d083e7ff8e3141a1b7d4cc4ce3b6fbef,
    title = "Constructive homomorphisms for classical groups",
    abstract = "Let be a quasisimple classical group in its natural representation over a finite vector space , and let . We construct the projection from to and provide fast, polynomial-time algorithms for computing the image of an element. Given a discrete logarithm oracle, we also represent as a group with at most 3 generators and 6 relations. We then compute canonical representatives for the cosets of . A key ingredient of our algorithms is a new, asymptotically fast method for constructing isometries between spaces with forms. Our results are useful for the matrix group recognition project, can be used to solve element conjugacy problems, and can improve algorithms to construct maximal subgroups.",
    keywords = "Classical groups",
    author = "Scott Murray and Colva Roney-Dougal",
    year = "2011",
    doi = "10.1016/J.JSC.2010.09.003",
    language = "English",
    volume = "46",
    pages = "371--384",
    journal = "Journal of Symbolic Computation",
    issn = "0747-7171",
    publisher = "Academic Press Inc.",

    }

    Murray, S & Roney-Dougal, C 2011, 'Constructive homomorphisms for classical groups', Journal of Symbolic Computation, vol. 46, pp. 371-384. https://doi.org/10.1016/J.JSC.2010.09.003

    Constructive homomorphisms for classical groups. / Murray, Scott; Roney-Dougal, Colva.

    In: Journal of Symbolic Computation, Vol. 46, 2011, p. 371-384.

    Research output: Contribution to journal › Article

    TY - JOUR

    T1 - Constructive homomorphisms for classical groups

    AU - Murray, Scott

    AU - Roney-Dougal, Colva

    PY - 2011

    Y1 - 2011

    N2 - Let be a quasisimple classical group in its natural representation over a finite vector space , and let . We construct the projection from to and provide fast, polynomial-time algorithms for computing the image of an element. Given a discrete logarithm oracle, we also represent as a group with at most 3 generators and 6 relations. We then compute canonical representatives for the cosets of . A key ingredient of our algorithms is a new, asymptotically fast method for constructing isometries between spaces with forms. Our results are useful for the matrix group recognition project, can be used to solve element conjugacy problems, and can improve algorithms to construct maximal subgroups.

    AB - Let be a quasisimple classical group in its natural representation over a finite vector space , and let . We construct the projection from to and provide fast, polynomial-time algorithms for computing the image of an element. Given a discrete logarithm oracle, we also represent as a group with at most 3 generators and 6 relations. We then compute canonical representatives for the cosets of . A key ingredient of our algorithms is a new, asymptotically fast method for constructing isometries between spaces with forms. Our results are useful for the matrix group recognition project, can be used to solve element conjugacy problems, and can improve algorithms to construct maximal subgroups.

    KW - Classical groups

    U2 - 10.1016/J.JSC.2010.09.003

    DO - 10.1016/J.JSC.2010.09.003

    M3 - Article

    VL - 46

    SP - 371

    EP - 384

    JO - Journal of Symbolic Computation

    JF - Journal of Symbolic Computation

    SN - 0747-7171

    ER -

    Murray S, Roney-Dougal C. Constructive homomorphisms for classical groups. Journal of Symbolic Computation. 2011;46:371-384. https://doi.org/10.1016/J.JSC.2010.09.003

    Access to Document