Enriched categories

Posted on 5 October 2023 by John

We begin with a couple examples.

First, the set of linear transformations from one vector space to another is itself a vector space.

Second, the set of continuous linear operators from one Banach space to another is itself a Banach space. Or maybe better, this set can be made into a Banach space.

In the first example, it’s pretty obvious how to add linear transformations and how to multiply a linear transformation by a scalar.

The second is a little more involved. Banach spaces are vector spaces, but with more structure. They have a norm, and the space is complete with respect to the topology defined by that norm. So while it’s obvious that the set of continuous linear operators between two Banach spaces is a vector space, it’s not quite obvious that it is in fact a Banach space. The latter requires that we define a norm on this space of continuous operators, and that we prove that this new space is complete. That’s why I said the set “can be made into” a Banach space because some construction is required.

The fancy way to describe these examples is to say that they are both examples of a category enriched over itself. A category is “enriched” if the set of morphisms [1] between two objects can be given the structure of a category itself, a category with more structure than the category of sets. This new category need not be the same as the one you started out with, but it can be.

If the morphisms between objects in a category C have the structure of category D, then we say C is enriched over D. If C = D, then we say the category is enriched over itself. The category of vector spaces with linear transformations is enriched over itself, as is the category of Banach spaces with continuous linear operators.

This post was motivated by a recent comment that said

Another categorical difference between working with groups and working with abelian groups is that “the category of abelian groups is enriched over itself” — in plainer language, between two groups G and H there’s a *set* of homomorphisms from G to H, but if G and H are abelian then this set of homomorphisms has the structure of an *abelian group* as well!

The proof that the homomorphisms between two Abelian groups forms an Abelian group is very simple. We show that if we define the addition of homomorphisms f and g element-wise, the result is a homomorphism.

$\begin{align*} (f + g)(x + y) &\equiv f(x + y) + g(x + y) \\ &= f(x) + f(y) + g(x) + g(y) \\ &= f(x) + g(x) + f(y) + g(y) \\ &\equiv (f + g)(x) + (f + g)(y) \end{align*}$

The critical step is the third line where we swap the order of f(y) and g(x). That’s where we use the fact that we’re working with Abelian groups.

Denoting the group operation + implies by convention that we’re working with Abelian groups; it goes against convention to use + to denote anything that isn’t commutative. But if our group operation were not commutative, the proof above would be invalid. And not only would the proof be invalid, the theorem would be false. There’s no way to salvage the theorem with a different proof. The set of homomorphisms between two general groups may not be a group.

[1] Think of morphisms as structure-preserving functions. Linear transformations preserve the structure of vector spaces. When our objects have more structure, the morphisms are more restrictive. We wouldn’t want to just consider linear maps between Banach spaces because arbitrary linear maps don’t preserve the topology of the spaces. Instead we look at continuous linear maps. In general morphisms don’t have to be functions, they just have to behave like them, i.e. satisfy the axioms that were motivated by structure-preserving functions.

Analogy between prime numbers and simple groups

Posted on 26 September 2023 by John

Simple groups are the building blocks of groups similar to the way prime numbers are the building blocks of integers. This post will unpack this analogy in two ways:

How do simple groups compare to prime numbers?
How does the composition of simple groups compare to the composition of prime numbers?

The former analogy is stronger than the latter.

Primes and simple groups

A simple group has no nontrivial subgroups, just a prime number has no nontrivial factors. Except that’s not quite right. A simple group is defined as having no nontrivial normal subgroups. The previous post compares normal and non-normal subgroups. Normal subgroups have nice properties which are necessary for decomposition and composition. You can’t define quotients for non-normal groups.

Every subgroup of an Abelian group is normal, so in the context of Abelian groups it is true that simple groups have no nontrivial subgroups, i.e. the only subgroups of a simple Abelian group G are the identity and G itself. It follows from Sylow’s theorems that the order of a finite Abelian group with no nontrivial factors must be an integer with no nontrivial factors, i.e. a prime number. Every Abelian finite simple group must be isomoprphic to the integers mod p for some prime p.

Non-Abelian finite simple groups do not have prime order, but they not decomposable in the sense described below.

Composition and decomposition

Prime numbers compose to form other numbers by products. You can also compose groups by taking products, though you need more than that. It is not the case that all finite groups are products of finite simple groups.

Let ℤ_n denote the cyclic group of order n and let ⊕ denote direct sum. The group ℤ₄ is not isomorphic to ℤ₂ ⊕ ℤ₂. Even in the case of Abelian groups, not all Abelian groups are the direct sum or direct product of simple groups. [1]

Finite groups can be decomposed into smaller finite simple groups, but we can’t easily or uniquely rebuild a group from this decomposition.

The Jordan-Hölder theorem says that a finite group G has a composition series

1 = H₀ ⊲ H₁ ⊲ … ⊲ H_n = G

where each H is a maximal normal subgroup of the next, the quotients H_i+1 / H_i of consecutive are simple groups. The composition series is not unique, but all such series are equivalent in a sense that the Jordan-Hölder theorem makes precise.

It seems to me that the composition series ought to be called a decomposition series in that you can start with G and find the H‘s, but it’s a difficult problem, known as “the extension problem,” to reconstruct G from the H‘s, and in general there are multiple solutions.

The analogy to prime numbers would be if there was an essentially unique way to factor a number, but not a unique way to multiply the factors back together.

Reductionism

Some people thought that the classification of finite simple groups would be the end group theory. That has not been the case. Some also thought sequencing of the human genome would lead to cures for a huge range of diseases. That has not been the case either. Reductionism often produces disappointing results.

[1] In the context of Abelian groups, (direct) products and coproducts (i.e. direct sums) are isomorphic.

Normal and non-normal subgroups

Posted on 26 September 2023 by John

The word “normal” in mathematical nomenclature does not always means “usual” or “customary” as it does in colloquial English. Instead, it might that something has a convenient property. That is the case for normal subgroups.

We can do things with normal subgroups that we cannot do with other subgroups, such as take quotients, and so once normal subgroups are introduced in an algebra class, non-normal subgroups disappear from the discussion. A student might be left with the impression that non-normal subgroups don’t exist.

This post will give a very simple example of a group with a non-normal subgroup, and show how we can’t do operations with this group that we can with normal subgroups.

Definition of normal subgroup

A normal subgroup of a group G is a subgroup N such gN = Ng for any element g in G. That is, if I multiply everything in N by g on the left or I multiply everything in N by g on the right, I get the same set of elements.

This does not mean that gn = ng for every n in N. It means that for every n in N, there is some element m in N such that gn = mg. The elements n and m might be the same, but they might not.

In an Abelian (commutative) group, gn always equals ng, and so all subgroups are normal. But most groups are not Abelian.

Structure-preserving functions

Along with every algebraic structure there are functions that preserve aspects of that structure. In the category of groups, these structure-preserving functions are called homomorphisms, coming from the Greek words for “same” and “shape.”

A homomorphism between groups gives you a sort of picture of the first group inside the second group in a way that is consistent with the structure of groups. Specifically, if f is a homomorphism from a groups G to a group H, then

f(xy) = f(x) f(y).

Here we denote the group operation by writing two things next to each other. So “xy” means the group operation in G applied to x and y. This operation may or may not be multiplication. The same is true on the right-hand side: f(x) f(y) means the group operation in H applied to f(x) and f(y).

For example, if we let G be the real numbers with the group operation being addition, and we let H be the positive real numbers with the group operation being multiplication, then the exponential function is a homomorphism between these groups:

exp(x + y) = exp(x) exp(y).

Kernels

The kernel of a homomorphism between G and H is the subset of things in G that get sent to the identity element in H. In the example above, the identity element in H is 1, and the only element in G that gets mapped to 1 is the number 0. It’s not a coincidence that 0 is the identity element in G: homomorphisms always send the identify element of one group to the identity element of the other group. The kernel of a homomorphism always includes the identity, but it may also include more.

Normal subgroups are subgroups that can be kernels. A subgroup of G is normal if and only if there is some homomorphism from G to another group that has that subgroup as its kernel.

A non-normal subgroup

Let G be the group of permutations on three elements. The group operation is composition, i.e. do one permutation then do the other.

The identity element is the permutation that leaves everything alone. Denote this by 1. Another element of G is the permutation that swaps the first two elements. We’ll denote this by (12).

So if our three elements are a, b, and c, then the permutation 1 takes (a, b, c) to (a, b, c). And the permutation (12) takes (a, b, c) to (b, a, c).

The two elements 1 and (12) form a subgroup of G. But we will show that a homomorphism from G to a group H cannot take these two elements, and only these two elements, to the identity on H. It won’t matter what group H is, but we’ll need a name for the identity element in H. Let’s call it e.

Let f be a homomorphism from G to H. () By definition

f(xy) = f(x) f(y)

and by applying this to (xy)z we have

f(xyz) = f(x) f(y) f(z)

If we let z be the inverse of x and y is in the kernel of f, we have

f(xyx^-1) = f(x) f(y) f(x^-1) = f(x) e f(x)^-1 = e.

This says that if y is in the kernel of f, xyx^-1 must also be in the kernel of f for every x.

The permutation that swaps the second and third elements, (23), is its own inverse: swap the second and third elements twice and you’re back where you started. So if (12) is in the kernel of f then so is (23)(12)(23). You can work out that (23)(12)(23) reverses three elements. This shows that if the subgroup consisting of 1 and (12) is in the kernel of f, so is the reverse permutation, which is not part of our subgroup. So our subgroup alone cannot be a kernel of a homomorphism.

Elliptic curve Diffie-Hellman key exchange

Posted on 15 September 2023 by John

I concluded the previous post by saying elliptic curve Diffie-Hellman key exchange (ECDHE) requires smaller keys than finite field Diffie-Hellman (FFDHE) to obtain the same level of security.

How much smaller are we talking about? According to NIST recommendations, a 256-bit elliptic curve provides about the same security as working over a 3072-bit finite field. Not only are elliptic curves smaller, they scale better. A 512-bit elliptic curve is believed to be about as secure as a 15360-bit finite field: a factor of 2x for elliptic curves and a factor of 5x for finite fields.

The core idea of Diffie-Hellman is to pick a group G, an element g, and a large number of x. If y is the result of starting with x and applying the group operation x times, it is difficult to recover x from knowing y. This is called the discrete logarithm problem, taking its name from the case of the group operation being multiplication. But the inverse problem is still called the discrete logarithm problem when the group is additive.

In FFDHE the group G is the multiplicative group of a generator g modulo a large prime p. Applying the group operation (i.e. multiplication) to g a number of times x is computing

y = g^x

and x is rightly called a discrete logarithm; the process is directly analogous to taking the logarithm of a real number.

In ECDHE the group is given by addition on an elliptic curve. Applying the group operation x times to g, adding g to itself x times, is written xg. The problem of recovering x from xg is still called the discrete logarithm problem, though you could call it the discrete “division” problem.

Some groups are unsuited for Diffie-Hellman cryptography because the discrete logarithm problem is easy. If we let G be the additive group modulo a prime (not the multiplicative group) then it is easy to recover x from xg.

Note that when we talk about applying the group operation a large number of times, we mean a really large number of times, in theory, though not in practice. If you’re working over an elliptic curve with on the order of 2²⁵⁶ elements, and x is on the order of 2²⁵⁶, then xg is the result of adding x to itself on the order of 2²⁵⁶ times. But in practice you’d double g on the order of 256 times. See fast exponentiation.

In the post on FFDHE we said that you have to be careful that your choice of prime and generator doesn’t give the group structure that a cryptanalysist could exploit. This is also true for the elliptic curves used in ECDHE, and even more so because elliptic curves are more subtle than finite fields.

If large-scale quantum computing ever becomes practical, Diffie-Hellman encryption will be broken because a quantum computer can solve discrete logarithm problems efficiently via Schor’s algorithm. This applies equally to finite fields and elliptic curves.

Group theory and RSA encryption

Posted on 14 September 2023 by John

RSA encryption a map from numbers mod n to numbers mod n where n is a public key. A message is represented as an integer m and is encrypted by computing

c = m^e mod n

where e is part of the public key. In practice, e is usually 65537 though it does not have to be.

Multiplicative group

As we discussed in the previous post, not all messages m can be decrypted unless we require m to be relatively prime to n. In practice this is almost certainly the case: discovering a message m not relatively prime to n is equivalent to finding a factor of n and breaking the encryption.

If we limit ourselves to messages which can be encrypted and decrypted, our messages come not from the integers mod n but from the multiplicative group of integers mod n: the integers less than and relatively prime to n form a group G under multiplication.

The encryption function that maps m to m^e is an invertible function on G. Its inverse is the function that maps c to c^d where d is the private key. Encryption is an automorphism of G because

(m₁ m₂) ^e = m₁^e m₂^e mod n.

Totient functions

Euler’s theorem tells us that

m^φ(n) = 1 mod n

for all m in G. Here φ is Euler’s totient function. There are φ(n) elements in G, and so we could see this as a consequence of Lagrange’s theorem: the order of an element divides the order of a group.

Now the order of a particular m might be less than φ(n). That is, we know that if we raise m to the exponent φ(n) we will get 1, but maybe a smaller exponent would do. In fact, maybe a smaller exponent would do for all m.

Carmichael’s totient function λ(n) is the smallest exponent k such that

m^k = 1 mod n

for all m. For some values of n the two totient functions are the same, i.e. λ(n) = φ(n). But sometimes λ(n) is strictly less than φ(n). And going back to Lagrange’s theorem, λ(n) always divides φ(n).

For example, there are 4 positive integers less than and relatively prime to 8: 1, 3, 5, and 7. Since φ(8) = 4, Euler’s theorem says that the 4th power of any of these numbers will be congruent to 1 mod 8. That is true, but its also true that the square of any of these numbers is congruent to 1 mod 8. That is, λ(8) = 2.

Back to RSA

Now for RSA encryption, n = pq where p and q are large primes and p ≠ q. It follows that

φ(pq) = φ(p) φ(q) = (p − 1)(q − 1).

On the other hand,

λ(pq) = lcm( λ(p), λ(q) ) = lcm(p − 1, q − 1).

Since p − 1 and q − 1 at least share a factor of 2,

λ(n) ≤ φ(n)/2.

Example

It’s possible that λ(n) is smaller than φ(n) by more than a factor of 2. For example,

φ(7 × 13) = 6 × 12 = 72

but

λ(7 × 13) = lcm(6, 12) = 12.

You could verify this last calculation with the following Python code:

>>> from sympy import gcd
>>> G = set(n for n in range(1, 91) if gcd(n, 91) == 1)
>>> set(n**12 % 91 for n in s)

This returns {1}.

Implementation

The significance of Carmichael’s totient to RSA is that φ(n) can be replaced with λ(n) when finding private keys. Given a public exponent e, we can find d by solving

ed = 1 mod λ(n)

rather than

ed = 1 mod φ(n).

This gives us a smaller private key d which might lead to faster decryption.

OpenSSL example

I generated an RSA key with openssl as in this post

    openssl genpkey -out fd.key -algorithm RSA \
      -pkeyopt rsa_keygen_bits:2048 -aes-128-cbc

and read it using

    openssl pkey -in  fd.key -text -noout

The public exponent was 65537 as noted above. I then brought the numbers in the key over to Python.

    from sympy import lcm

    modulus = xf227d5...a9
    prime1 = 0xf33514...d9
    prime2 = 0xfee496...51
    assert(prime1*prime2 == modulus)

    publicExponent = 65537
    privateExponent = 0x03896d...91

    phi = (prime1 - 1)*(prime2 - 1)
    lamb = lcm(prime1 - 1, prime2 - 1)
    assert(publicExponent*privateExponent % lamb == 1)
    assert(publicExponent*privateExponent % phi != 1)

This confirms that the private key d is the inverse of e = 65537 using modulo λ(pq) and not modulo φ(pq).

Möbius transformations over a finite field

Posted on 8 August 2023 by John

A Möbius transformation is a function of the form

$g(z) = \frac{az + b}{cz + d}$

where ad – bc = 1.

We usually think of z as a complex number, but it doesn’t have to be. We could define Möbius transformations in any context where we can multiply, add, and divide, i.e. over any field. In particular, we could work over a finite field such as the integers modulo a prime. The plot above represents a Möbius transformation over a finite field which we will describe below.

There is a subtle point, however. In the context of the complex numbers, the transformation above doesn’t quite map the complex plane onto the complex plane. It maps the complex plane minus one point to the complex plane minus one point. The domain is missing the point z = −d/c because that value makes the denominator zero. It’s also missing a point in the range, namely a/c.

The holes in the domain and range are a minor irritant, analogous to the pea in The Princess and the Pea. You can work around the holes, though the formalism is a little complicated. But over a finite field, the holes are a big deal. If you’re working over the integers mod 7, for example, then 1/7th of your domain is missing.

In the case of the complex numbers, the usual fix is to replace the complex numbers ℂ with the extended complex numbers ℂ ∪ ∞ and say that g(−d/c) = ∞ and g(∞) = a/c. There are a couple ways to make this more rigorous/elegant. The topological approach is to think of ℂ ∪ ∞ as the Riemann sphere. The algebraic approach is to think of it as a projective space.

Now let’s turn to finite fields, say the integers mod 17, which we will write as ℤ₁₇. For a concrete example, let’s set a = 3, b = 8, c = 6, and d = 5. Then ad – bc = 1 mod 17. The multiplicative inverse of 6 mod 17 is 3, so we have a hole in the domain when

z = −d/c = −5/6 = −5 × 3 = − 15 = 2 mod 17.

Following the patch used with complex numbers, we define g(2) to be ∞, and we define

g(∞) = a/c = 3/6 = 3 × 3 = 9 mod 17.

That’s all fine, except now we’re not actually working over ℤ₁₇ but rather ℤ₁₇ ∪ ∞. We could formalize this by saying we’re working in a projective space over ℤ₁₇. For this post let’s just say we’re working over set G with 18 elements that mostly follows the rules of ℤ₁₇ but has a couple additional rules.

Now our function g maps G onto G. No holes.

Here’s how we might implement g in Python.

    def g(n):
        if n == 2:
            return 17
        if n == 17:
            return 9
        a, b, c, d = 3, 8, 6, 5
        denom = c*n + d
        denom_inverse = pow(denom, -1, 17)
        return (a*n + b)*denom_inverse % 17

The plot at the top of the post arranges 18 points uniformly around a circle and connects n to g(n).

    from numpy import pi, linspace, sin, cos
    import matplotlib.pyplot as plt

    θ = 2*pi/18
    t = linspace(0, 2*pi)
    plt.plot(cos(t), sin(t), 'b-')

    for n in range(18):
        plt.plot(cos(n*θ), sin(n*θ), 'bo')
        plt.plot([cos(n*θ), cos(g(n)*θ)],
                 [sin(n*θ), sin(g(n)*θ)], 'g-')
    plt.gca().set_aspect("equal")
    plt.show()

Application to cryptography

What use is this? Möbius transformations over finite fields [1] are “higgledy-piggledy” in the words of George Marsaglia, and so they can be used to create random-like permutations. In particular, Möbius transformations over finite fields are used to design S-boxes for use in symmetric encryption algorithms.

[1] Technically, finite fields plus an element at infinity.

[2] “If the [pseudorandom] numbers are not random, they are at least higgledy-piggledy.” — RNG researcher George Marsaglia

Primes and simple groups

Composition and decomposition

Reductionism

Related posts

Definition of normal subgroup

Structure-preserving functions

Kernels

A non-normal subgroup

Related posts

Related posts

Multiplicative group

Totient functions

Back to RSA

Example

Implementation

OpenSSL example

Related posts

Application to cryptography

Related posts