Finite Field Notes

I learned all this for cyclic keys, then I forgot it. This time I'm taking notes

Totient

The number of values k for which 1 ≤ k ≤ n and gcd(n,k) == 1. For any prime, φ(p) = p-1.

Also called a generator r^x for x in (1,n) will generate every value in (1,n), but at random (well, sort of).

There is no algorithm to find the first primitive root.

Once you have one primitive root, the other can easily be found. r₀_i % n will be a primitive root if gcd(i, φ(n)) = 1

 A^-1 * A = 1 % N

An inversion will only exist if A is coprime to N. So if N is prime, every number has an inverse. It can be found with Euclid's algorithm.