THE GARDEN

Groups (Group Theory Basics)

Updated 13 Sep 2026

• •

  What it is

  • •

    A group is a set of elements paired with a single binary operation (often written as multiplication or addition) satisfying four properties: closure (combining two elements stays in the set), associativity, an identity element, and every element having an inverse. Cryptography almost always works inside a specific, well-understood group — most commonly $\mathbb{F}_p^\times$ (the nonzero integers mod a prime $p$, under multiplication) or an elliptic curve's point set (under a geometrically-defined "addition"). A group is cyclic if some single element $g$ (a generator) can produce every element of the group by repeated application of the operation — $\{g, g^2, g^3, \dots\}$ for a multiplicative group. The order of an element $g$ is the smallest positive integer $n$ such that applying the operation to $g$ with itself $n$ times returns the identity ($g^n = 1$ in multiplicative notation); the order of the whole group is simply the number of elements it contains. Lagrange's theorem guarantees the order of any element always divides the order of the group — this single fact underlies an enormous amount of cryptographic reasoning (Fermat's little theorem, Euler's theorem, and Pohlig-Hellman's whole strategy all follow from it).

• •

  When to apply

  • •

    Whenever a scheme is described as operating "in a group" — anytime you see modular exponentiation, elliptic curve point multiplication, or language like "generator," "order," "subgroup" — this is the vocabulary and structural intuition everything else in that scheme builds on.

• •

  Symbols and assumptions

  • •

    $G$ is a set with one operation; $|G|$ counts its elements. The identity is 1 in multiplicative notation or 0 in additive notation. $\operatorname{ord}(g)$ is the number of repetitions needed to return to the identity.

• •

  Math — step by step

  • •
    1. Check closure, associativity, an identity, and inverses. Commutativity is an extra property (abelian); it is not required of every group.
  • •
    2. The subgroup generated by $g$ is $\langle g\rangle=\{1,g,g^2,\ldots\}$. If its size equals $|G|$, then $g$ generates the whole group; otherwise it only generates a subgroup.
  • •
    3. Powers repeat modulo the element order: if $g^n=1$, then $g^{x+n}=g^x$. A discrete log therefore identifies $x$ modulo $\operatorname{ord}(g)$, not necessarily modulo the ambient group size.
  • •
    4. Lagrange’s theorem gives $\operatorname{ord}(g)\mid|G|$. In $\mathbb F_p^\times$, $|G|=p-1$. Distinguish the prime modulus $p$ from this group order $p-1$.
• •

  Worked example

  • •

    In $\mathbb F_{11}^\times$, powers of 3 from exponent 0 are $1,3,9,5,4,1$. The first return to 1 occurs at exponent 5, so its subgroup has order 5.

  • •

    The whole group has 10 elements. Powers of 2 are $1,2,4,8,5,10,9,7,3,6,1$, so 2 has order 10 and generates the whole group.

  • •

    For example, $3^7=3^{5+2}\equiv3^2=9$. Knowing $3^x=9$ gives $x\equiv2\pmod5$; it does not identify a unique unbounded integer.

• •

  Python

  • •

    def order(g, p):
            n = 1
            x = g % p
            while x != 1:
                x = (x * g) % p
                n += 1
            return n
    

• •

  SageMath

  • •

    F = GF(p)
    F(g).multiplicative_order()   # order of g in F_p^*
    F.multiplicative_generator()  # a generator of the whole group
    

• •

  Related

  • •

    Finite Fields (Galois Fields: GF(p) and GF(2^n))

  • •

    Discrete Logarithm Problem (DLP)

  • •

    Fermat's Little Theorem

• •

  Cards

  • •

    What four properties define a group?

    • •

      Closure, associativity, an identity element, and inverses for every element.

  • •

    What does Lagrange's theorem guarantee about the order of an element?

    • •

      The order of any element always divides the order of the whole group.

  • •

    What's the difference between an element's order and the group's order?

    • •

      An element's order is the smallest n making g^n the identity; the group's order is the total number of elements — Lagrange's theorem says the former always divides the latter.

◌ Explore connections in Graph view