## Visualizing group structure, part 2: prime vs. composite, CRT

Some time ago I’ve generated colored addition/multiplication tables in order to visualize group structure. My idea was to compare extension fields of same order with different reduction polynomials, and to compare elliptic curve groups with groups of integers modulo a prime ($\mathbb{Z}_p$). However, as pointed out by an attentive reader, I’ve messed up claiming that the latter group is used by RSA. It is not, it’s used for e.g. DSA, while RSA uses a composite modulus: the product of two prime numbers.

So, how do $\mathbb{Z}_p^*$ and $\mathbb{Z}_n^*$ compare?

## Understanding the Montgomery reduction algorithm

The Montgomery reduction algorithm finds the remainder of a division. Many cryptographic schemes work with numbers modulo a prime. When you have to multiply two numbers with e.g. 128 bits each, first you multiply them the usual way (there are many techniques for this) to obtain a 256-bit (“double precision”) number. Then you need to reduce this result modulo the prime you’re working with, that is, compute the remainder of the division of this number over the prime.

You can compute the remainder of a division with the “schoolbook” technique everyone learns in school, but that is expensive and requires divisions, with are costly in many platforms (some microcontrollers don’t even have a division instruction). Montgomery reduction only needs a division by a powers of the integer size, which are cheap for computers.

Here I’ll try to explain how it works, in an informal approach. For detailed proofs of its correctness, check e.g. the chapter 14 of the Handbook of Applied Cryptography or the original paper.

## Understanding the extended Euclidean algorithm

The Euclidean algorithm finds the greatest common divisor of two numbers a and b. There is an extended version of it that also finds two numbers x and y such that ax + by = gcd(a,b). This is useful when searching for modular multiplicative inverses.

The algorithm is simple, but I’ve never bothered to study why and how it works (a shame, really, but sometimes you have to postpone the understanding of some basic things in order to go on…). Finally I’ve decide to put some thought on it and came up with this (this is not a proof; it’s just some intuitive thinking to grasp the inner workings of the algorithm).

## The Frobenius endomorphism with finite fields

The Frobenius endomorphism is defined as:

$\Phi(x)=x^p$

where p is the characteristic of the ring you’re working with. Simple, right?

If you’re working with a field with prime order, then Frobenius is actually the identity map. Since the order of the multiplicative subgroup is p, when you raise to the power of p you get back to x due to Fermat’s little theorem. Things get more interesting when you’re working with a extension field (i.e. a field which order is a prime power).

I’m studying pairings for my master’s degree and the Frobenius endomorphism appears all the time in their computation. For example, you need to do a “final exponentation” which can be split in multiple exponentiations, and some of them are to the power of p. This is good because powering to p is “easy” due to Frobenius, or at least all the papers I read said so. But for a while I couldn’t see why, and that’s the reason I’m posting this. It’s really easy; it’s just not that obvious to see why.

## Visualizing group structure with colored addition/multiplication tables

When working with finite fields, if the number of elements is a prime power $p^m$ with m > 1, you can represent the elements as polynomials with degree m-1 and do the field addition and multiplication modulo a irreducible polynomial with degree m.

The field GF(5) is composed by the numbers 0 to 4. We don’t need to represent its elements as polynomials since m=1. Addition is done modulo 5 and multiplication also modulo 5. So 2 + 3 = 0; 4 * 2 = 3; and so on. This is the addition table for GF(5):

The rows, top down, represent 0 to 4. The columns, right to left, represent 0 to 4. Each square is the result of the addition of the respective numbers in the row / column it belongs to. Black is 0, purple is 1, red is 2, orange is 3, yellow is 4.