Hoe je de orde van een groep berekent zonder te tellen

In het kort

Je krijgt een handvol permutaties en de vraag hoeveel elementen de groep heeft die ze samen voortbrengen. Voor kleine gevallen tel je het uit. Voor een groep als S_100 is dat geen optie: die heeft 158 cijfers, meer dan er atomen in het waarneembare heelal zijn. Toch valt dat aantal exact te berekenen, in seconden, met een algoritme dat niets met tellen doet. Schreier-Sims rekent de orde uit als het product van de groottes van een rij banen, en slaat daarmee het enumereren volledig over. Dit artikel bouwt het van de grond af op, met de valkuilen die het in de praktijk lastig maken, een werkende implementatie van ongeveer honderddertig regels, en metingen op groepen tot S_200.

Een vraag die klein lijkt

Een permutatie van n punten is een herschikking. Geef je er een paar, dan bepaalt de groep die ze voortbrengen hoeveel verschillende herschikkingen je kan maken door ze in elke volgorde en zo vaak als je wil toe te passen. Die groep heeft een orde: het aantal elementen.

Voor twee of drie kleine permutaties voelt dat als een telprobleem. Het is er ook een, maar een waarbij het antwoord zo snel groeit dat de telmethode zelf het probleem wordt. S_20 heeft 2.432.902.008.176.640.000 elementen. S_30 heeft er 33 cijfers. S_100 heeft er 158, en dan praten we over een verzameling die je nog op een telefoon kan uitrekenen met de juiste truc.

Er bestaat geen formule voor de orde van een willekeurige permutatiegroep. Er bestaat wel een algoritme dat de groep niet meer als lijst bekijkt maar als keten van stabilisatoren, en dat is de kern van Schreier-Sims.

Waar dit opduikt

De kubus van Rubik. Het aantal mogelijke standen is 43.252.003.274.489.856.000, en dat getal is niet geteld maar berekend met precies deze groepentheorie. Wie het zelf wil narekenen heeft een groep met zes generators en een orde van 4,3 maal 10^19.

Cryptografie. De moeilijkheid van het discrete logaritme hangt af van de orde van de groep en van de factorisatie daarvan. Pohlig-Hellman maakt dat concreet: is de orde glad, dus opgebouwd uit kleine priemfactoren, dan valt het probleem uiteen in stukjes en wordt het oplosbaar. Daarom eisen cryptografische groepen een orde met een grote priemfactor. Het is dezelfde vraag, alleen anders ingezet.

Foutcorrigerende codes. Permutatiegroepen beschrijven de symmetrieën van codes, en bij permutation decoding wordt de automorfismegroep van een code gebruikt om fouten te herstellen. Die groep moet je kennen, en de orde is de eerste vraag.

Graafisomorfie en combinatoriek. Het isomorfismeprobleem voor grafen is decennialang aangepakt met precies deze technieken, en de modernste algoritmes zijn er nog steeds op gebaseerd.

De wiskunde in vier stappen

Een permutatie is een functie. Voor de implementatie is het handiger om hem als bytes op te slaan, waarbij p[i] het beeld is van punt i. De identiteit is dan bytes(range(n)).

Een groep is gesloten onder samenstelling en inverse. Samenstellen betekent: eerst de een toepassen, dan de ander. Voor bytes is dat een translatietabel, en dat is duizend keer sneller dan een lus in Python.

Stabilisatoren in plaats van elementen. Kies een punt, bijvoorbeeld 0. De baan van 0 is de verzameling punten waar 0 door de groep naartoe gestuurd kan worden. De stabilisator van 0 is de deelgroep van elementen die 0 op zijn plek laat. De stelling van de baan en de stabilisator zegt dan iets heel bruikbaars:

|G| = |baan van 0| × |stabilisator van 0|

Herhaal dat, en je hebt de orde. Kies in de stabilisator een volgend punt dat nog beweegt, en doe hetzelfde. Dat levert een rij punten op, de basis, en een rij banen. Het product van de groottes van die banen is de orde van de groep. Voor S_100 zijn dat honderd banen van 100, 99, 98 en zo verder, en hun product is precies 100 faculteit.

De vraag wordt dan: hoe vind je die stabilisatoren zonder de hele groep te kennen? Daar is het lemma van Schreier voor: als je de baan kent en de generators, dan genereren de Schreier-generatoren de stabilisator. Formeel zijn dat koppels van een baanelement en een generator, en dat zijn er veel meer dan je wil.

Waarom de naïeve versie ontploft

De formule hierboven is correct en volstrekt onbruikbaar als je hem letterlijk implementeert. Op elk niveau krijg je namelijk een aantal nieuwe generators gelijk aan de baangrootte maal het aantal generators dat je al had. Bij S_100 loopt dat in de eerste stap al op tot duizenden, en die moeten allemaal verwerkt worden.

De oplossing heet sifting, of in het Nederlands zeven. Je neemt een kandidaat-generator en probeert hem met de al gevonden baanrepresentanten af te breken. Lukt dat helemaal, dan is hij al in de groep en kan hij weg. Lukt het tot niveau j en niet verder, dan is de rest een nieuw element dat op niveau j hoort. Zo hou je per niveau alleen de generators over die echt iets toevoegen.

Wat overblijft is de vraag of je daarmee klaar bent. Nee: na het toevoegen van een generator verandert de baan, en kunnen eerder afgekeurde kandidaten alsnog een rest achterlaten. Daarom is het algoritme incrementeel: het blijft paren controleren tot er niets meer te controleren valt.

Drie valkuilen die je implementatie slopen

De generatorsets moeten genest zijn. Een strong generating set heeft per niveau de generators van dat niveau en alle diepere. Pas dan geldt dat de orde het product van de baangroottes is. Voeg je een generator alleen op zijn eigen niveau toe, dan klopt de formule niet meer en krijg je een getal dat er plausibel uitziet en fout is. Dit is de fout die je het langst niet doorhebt.

Niet elke toevoeging hoeft alle banen opnieuw te doen. Een rest die op niveau j is blijven hangen, zit per definitie in de deelgroep die bij niveau j hoort. Voor de niveaus daarboven verandert er dus niets, en die hoef je niet opnieuw te doorlopen. Zonder die beperking wordt het algoritme traag zonder ooit fout te worden, wat het lastiger maakt om te zien dat je iets mist.

De orde past niet in een getal. S_100 heeft 158 cijfers. Reken modulo een priemgetal, of gebruik big integers en accepteer dat het traag wordt. In wedstrijdverband is modulo het gebruikelijk, en dat betekent wel dat je het antwoord nooit meer kan controleren door het uit te schrijven.

De implementatie

Dit is de volledige solver, in de vorm waarin hij het snelst is: bytes in plaats van lijsten, translatietabellen in plaats van lussen, en per niveau een werkvoorraad met Schreier-paren. De commentaren geven aan waarom elke stap er staat.

def group_order(gens, n, mod=None):
    """Orde van de groep voortgebracht door gens, optioneel modulo `mod`."""
    e = bytes(range(n))
    PAD = bytes(range(n, 256))
    tabs = {}

    def tab(a):
        t = tabs.get(a)
        if t is None:
            t = bytes(a) + PAD
            tabs[a] = t
        return t

    def comp(a, b):
        # pas b toe en daarna a: resultaat[i] = a[b[i]]
        return b.translate(tab(a))

    invs = {}

    def inv(a):
        r = invs.get(a)
        if r is None:
            buf = bytearray(n)
            for i, x in enumerate(a):
                buf[x] = i
            r = bytes(buf)
            invs[a] = r
        return r

    base = []      # de basispunten, een per niveau
    S = []         # generators per niveau (genest)
    Sset = []
    T = []         # baan per niveau: punt -> element dat basispunt daarheen stuurt
    TI = []        # hetzelfde, maar dan de inverse
    pend = []      # nog te controleren Schreier-paren per niveau
    chk = []       # paren die al kloppen

    def new_level(bp):
        base.append(bp)
        S.append([])
        Sset.append(set())
        T.append({bp: e})
        TI.append({bp: e})
        pend.append(deque())
        chk.append(set())

    def extend_orbit(k):
        gensL = S[k]
        Tk, TIk, pk = T[k], TI[k], pend[k]
        q = deque(Tk)
        while q:
            p = q.popleft()
            up, iup = Tk[p], TIk[p]
            for g in gensL:
                np_ = g[p]
                if np_ not in Tk:
                    Tk[np_] = comp(g, up)
                    TIk[np_] = comp(iup, inv(g))
                    q.append(np_)
                    for h in gensL:
                        pk.append((np_, h))

    def first_moved(x):
        for j in range(n):
            if x[j] != j:
                return j
        return -1

    def add_residue(r, j, from_level):
        if j == -1:
            j = len(base)
        if j == len(base):
            new_level(first_moved(r))
        if r in Sset[j]:
            return
        for k in range(j + 1):
            S[k].append(r)
            Sset[k].add(r)
        lo = from_level + 1
        for k in range(lo, j + 1):
            extend_orbit(k)
        for k in range(lo, j + 1):
            Tk, pk = T[k], pend[k]
            for p in Tk:
                pk.append((p, r))

    def strip(x, start):
        for i in range(start, len(base)):
            b = base[i]
            t = TI[i].get(x[b])
            if t is None:
                return x, i
            x = comp(t, x)
            if x == e:
                return e, -1
        return x, -1

    # fase 1: de generators wegzeven
    seen = set()
    for g in gens:
        if g == e or g in seen:
            continue
        seen.add(g)
        r, j = strip(g, 0)
        if r != e:
            add_residue(r, j, -1)

    # fase 2: Schreier-generatoren controleren tot niets meer overblijft
    while any(pend):
        for i in range(len(base)):
            qi, ci = pend[i], chk[i]
            Ti, TIi, bi = T[i], TI[i], base[i]
            while qi:
                p, g = qi.popleft()
                key = (p, g)
                if key in ci:
                    continue
                u = Ti[p]
                h = comp(TIi[g[p]], comp(g, u))
                r, j = strip(h, i + 1)
                if r != e:
                    add_residue(r, j, i)
                    qi.append(key)
                else:
                    ci.add(key)

    order = 1
    for i in range(len(base)):
        order = order * len(T[i])
        if mod:
            order %= mod
    return order

Een paar details die het verschil maken tussen werken en niet werken.

translate met een tabel van 256 bytes is de reden dat dit in Python bruikbaar is. Samenstellen is de duurste operatie in het hele algoritme, en die gebeurt hier in C.

De baan wordt alleen uitgebreid waar een nieuwe generator hem echt kan vergroten. Dat is geen optimalisatie voor de sier: het is het verschil tussen kwadratisch en iets dat in de praktijk bruikbaar blijft.

Het residu dat uit het zeven komt, weet meteen op welk niveau het hoort. Dat is de informatie die bepaalt welke niveaus bijgewerkt moeten worden, en dus de kern van het hele incrementele ontwerp.

Wat het kost

Gemeten op een gewone laptop, één kern, in seconden. De orde wordt modulo 1.000.000.007 berekend zodra het getal te groot wordt.

De groei is ruwweg kwadratisch in n, wat precies is wat je van Schreier-Sims verwacht. Voor een wedstrijdopgave met n in de tientallen is dat ruim voldoende. Voor n in de honderden wordt het een kwestie van geduld, en dat is een eigenschap van het algoritme, niet van de implementatie.

Eén grens zit er in deze versie zelf: de bytes-representatie werkt tot 255 punten. Daarboven moet je terug naar lijsten of naar een andere opslag, en dan verdwijnt het snelheidsvoordeel van translate meteen. Dat is een eerlijke beperking, en wie hem tegenkomt heeft een groter probleem dan een byte te weinig.

Ter vergelijking, met dezelfde groepen in SymPy:

Dat is geen wedstrijd die je moet willen winnen. SymPy is gemaakt om correct en leesbaar te zijn, deze code om snel te zijn en weinig regels te hebben.

Zo controleer je of je implementatie klopt

Een algoritme als dit geeft altijd een getal. De kunst is weten of het getal klopt, en dat is de stap die mensen overslaan.

Wat ik gedaan heb: 480 willekeurig samengestelde groepen op 3 tot 6 punten, elk vergeleken met de orde die SymPy berekent. Nul afwijkingen. Daarna de klassieke families, waar de verwachte orde bekend is:

Twee dingen vallen op als je dat doet. De alternerende groep A_n is met de verkeerde generators zo te krijgen dat je een kleinere groep uitrekent dan je dacht: twee driekringen die elkaar niet raken brengen alleen de groep op de punten voort die ze samen bewegen, en dan krijg je A_5 terwijl je A_6 verwachtte. Dat is geen fout in het algoritme, dat is een fout in je aanname. En de modulo-controle tegen 100! is de goedkoopste test die er is: die vangt elke fout in de nestingslogica, want één verkeerd niveau en het antwoord wijkt af.

Zelf proberen

De code staat hierboven volledig, en als los bestand om te downloaden: groepsorde.py. De invoer is simpel: eerst het aantal punten en het aantal generators, daarna per generator een regel met de beelden van de punten, één-geïndexeerd.

100 2
2 1 3 4 5 ...
2 3 4 5 ... 1

Dat leest als: 100 punten, twee generators, de eerste is de transpositie van 0 en 1, de tweede een honderdcykel.

Wie dit zelf wil gebruiken voor een eigen programma: de functie heet group_order en accepteert een lijst bytes plus het aantal punten, met een optionele modulus. Geen afhankelijkheden buiten de standaardbibliotheek.

Verder lezen

Deze wiskunde komt bij ons vooral langs in de CTF & Labs-hoek, waar opgaven soms meer over groepen gaan dan over exploits. Gaat je opgave over een zwakke sleutel in plaats van over een groep, dan staan de vijf aannames in RSA apart uitgewerkt. Begin je net met Hack The Box, dan is de roadmap in vijf stappen het betere startpunt, en voor wie zelf een omgeving wil om te oefenen staat er het stuk over je eerste eigen hacklab.

Veelgestelde vragen

Heb ik hier een wiskundestudie voor nodig?

Nee. Je hebt nodig: het idee van een functie die punten verplaatst, het idee van een deelgroep, en de bereidheid om één formule drie keer opnieuw te lezen. De rest is boekhouden. Wat wel helpt is zelf een klein geval met de hand doorrekenen, bijvoorbeeld de symmetrieën van een vierkant.

Is dit bruikbaar om cryptografie te breken?

Nee, en dat is ook niet de bedoeling. Dit is een algoritme dat een groep beschrijft, niet dat een sleutel kraakt. Wat je ermee leert is waarom de orde van een groep ertoe doet in cryptografie, en waarom een ongelukkig gekozen orde het discrete logaritme makkelijk maakt. Dat is de kant van begrijpen om te verdedigen.

Waarom modulo rekenen en niet gewoon het echte getal?

Omdat 100 faculteit 158 cijfers heeft en de meeste omgevingen dat best aankunnen, maar een product van honderden factoren in een binnen enkele seconden aflopend programma niet. Modulo een priemgetal blijft alles snel en blijft het antwoord bruikbaar voor verificatie. Wil je het exacte getal, dan kan dat, maar dan moet je meer geduld meenemen.

Kan ik dit in een andere taal implementeren?

Ja. Het algoritme is taalneutraal; alleen de truc met translatietabellen is een Python-specifieke versnelling. In C of Rust werkt hetzelfde ontwerp, en daar is de representatie van een permutatie als array ook prima voor grotere aantallen punten dan 255.