Generalised sifting in black-box groups

Details Generalised sifting in black-box groups Generalised sifting in black-box groups

2005-01-21

arxiv.org/abs/math/0501346v3

LMS J. Comput. Math. 8 (2005) 217--250

Mathematics

Group Theory

Scientific paper

We present a generalisation of the sifting procedure introduced originally by Sims for computation with finite permutation groups, and now used for many computational procedures for groups, such as membership testing and finding group orders. Our procedure is a Monte Carlo algorithm, and is presented and analysed in the context of black-box groups. It is based on a chain of subsets instead of a subgroup chain. Two general versions of the procedure are worked out in detail, and applications are given for membership tests for several of the sporadic simple groups. Our major objective was that the procedures could be proved to be Monte Carlo algorithms, and their costs computed. In addition we explicitly determined suitable subset chains for six of the sporadic groups, and we implemented the algorithms involving these chains in the {\sf GAP} computational algebra system. It turns out that sample implementations perform well in practice. The implementations will be made available publicly in the form of a {\sf GAP} package.

Affiliated with

Also associated with

No associations

Rating

Generalised sifting in black-box groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generalised sifting in black-box groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalised sifting in black-box groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-593880