论文标题
怪物组的快速实施
A fast implementation of the Monster group
论文作者
论文摘要
令$ \ mathbb {m} $为怪物组，它是最大的零星有限简单组，并首先是由Griess于1982年建造的。 1985年，康威（Conway）构建了196844-维的有理epresentation $ρ$ $ \ mathbb {m} $，其中矩阵条目在$ \ mathbb {z}中，[\ frac {1} {1} {2}] $。我们描述了一种新的快速算法，用于在$ \ mathbb {m} $中执行组操作。 对于奇数整数$ p> 1 $让$ρ_p$是表示矩阵条目的表示$ρ$ modulo $ p $。我们使用$ \ mathbb {m} $的生成套装$γ$，以便可以轻松计算$ρ_p$的元素上的发电机的操作。 我们构造了模块$ρ_{15} $元素的三重$（v_1，v^+，v^ - ）$，因此可以从图像$（v_1 g，v_1 g，v^+ g，v^^ - g）中有效地将未知的$ g \ in \ mathbb {m} $有效地计算为$γ$中的单词。 我们的新算法基于这个想法将$ \ mathbb {m} $的两个随机元素乘以标准PC上的30〜毫秒，其Intel I7-8750H CPU在4 GHz处。这比威尔逊在2013年估计的快100000倍以上。
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.
