Randomized BSGS algorithms

[jdbancal]

BSGS chains are a crucial tool for computing with finite groups. The deterministic construction of a BSGS chain is very resource demanding for groups acting on many points (very slow). Thankfully, a variety of (much quicker) randomized methods are known for this.

Currently, RepLAB implements one such randomized method. Since the method can fail on groups with a very large diameter, its usage is however limited to the situation in which the group order is known (provided by the user). In this case, correctness is guaranteed despite randomization. But other randomized methods have been proposed, which guarantee correctness with a given desired probability, while preserving computational advantage. Can we implement one of these methods to be our default BSGS chain construction for domain size >= 100?

References:

• https://github.com/jix/permutation_group_experiments
• http://www.math.rwth-aachen.de/~GAP/WWW2/Gap3/Manual3/C021S024.htm