# Monthly Archives: June 2018

## Free Groups and Tiling

Introduction Consider the following simple problem. Prove that the shape on the left cannot be completely tiled by 20 polygons of the types shown on the right. The solution is rather simple: colour the shape in the following manner. This … Continue reading

## Solving Permutation-Based Puzzles

Introduction In the previous article, we described the Schreier-Sims algorithm. Given a small subset which generates the permutation group G, the algorithm constructs a sequence such that for: we have a small generating set for each Specifically, via the Sims … Continue reading

Posted in Uncategorized | | 2 Comments

## Schreier-Sims Algorithm

Introduction Throughout this article, we let G be a subgroup of generated by a subset  We wish to consider the following questions. Given A, how do we compute the order of G? How do we determine if an element lies in G? Assuming , how … Continue reading

## Primality Tests III

Solovay-Strassen Test This is an enhancement of the Euler test. Be forewarned that it is in fact weaker than the Rabin-Miller test so it may not be of much practical interest. Nevertheless, it’s included here for completeness. Recall that to … Continue reading