Finite Field Notes: Difference between revisions

Revision as of 04:32, 17 January 2016

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

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

@@ Line 3: / Line 3: @@
 == Totient ==
 The number of values k for which 1 &le; k &le; n and gcd(n,k) == 1. For any prime, &phi;(p) = p-1.
+== Primitive Root ==
+Also called a generator r<sup>x</sup> 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<sub>0</sub><sub>i</sub> % n will be a primitive root if gcd(i, &phi;(n)) = 1