A fast implementation of the Monster group
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910304978337792 |
|---|---|
| author | Seysen, Martin |
| author_facet | Seysen, Martin |
| contents | Let $\mathbb{M}$ be the Monster group, which is the largest sporadic finite simple group, and has first been constructed in 1982 by Griess. In 1985 Conway has constructed a 196884-dimensional rational epresentation $ρ$ of $\mathbb{M}$ with matrix entries in $\mathbb{Z}[\frac{1}{2}]$. We describe a new and very fast algorithm for performing the group operation in $\mathbb{M}$.
For an odd integer $p > 1$ let $ρ_p$ be the representation $ρ$ with matrix entries taken modulo $p$. We use a generating set $Γ$ of $\mathbb{M}$, such that the operation of a generator in $Γ$ on an element of $ρ_p$ can easily be computed.
We construct a triple $(v_1, v^+, v^-)$ of elements of the module $ρ_{15}$, such that an unknown $g \in \mathbb{M}$ can be effectively computed as a word in $Γ$ from the images $(v_1 g, v^+ g, v^- g)$.
Our new algorithm based on this idea multiplies two random elements of $\mathbb{M}$ in less than 30~milliseconds on a standard PC with an Intel i7-8750H CPU at 4 GHz. This is more than 100000 times faster than estimated by Wilson in 2013. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_04223 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A fast implementation of the Monster group Seysen, Martin Group Theory 20C34, 20D08, 20C11, 20-08 Let $\mathbb{M}$ be the Monster group, which is the largest sporadic finite simple group, and has first been constructed in 1982 by Griess. In 1985 Conway has constructed a 196884-dimensional rational epresentation $ρ$ of $\mathbb{M}$ with matrix entries in $\mathbb{Z}[\frac{1}{2}]$. We describe a new and very fast algorithm for performing the group operation in $\mathbb{M}$. For an odd integer $p > 1$ let $ρ_p$ be the representation $ρ$ with matrix entries taken modulo $p$. We use a generating set $Γ$ of $\mathbb{M}$, such that the operation of a generator in $Γ$ on an element of $ρ_p$ can easily be computed. We construct a triple $(v_1, v^+, v^-)$ of elements of the module $ρ_{15}$, such that an unknown $g \in \mathbb{M}$ can be effectively computed as a word in $Γ$ from the images $(v_1 g, v^+ g, v^- g)$. Our new algorithm based on this idea multiplies two random elements of $\mathbb{M}$ in less than 30~milliseconds on a standard PC with an Intel i7-8750H CPU at 4 GHz. This is more than 100000 times faster than estimated by Wilson in 2013. |
| title | A fast implementation of the Monster group |
| topic | Group Theory 20C34, 20D08, 20C11, 20-08 |
| url | https://arxiv.org/abs/2203.04223 |