Finite Field Notes: Difference between revisions
Jump to navigation
Jump to search
Adamcolton (talk | contribs) No edit summary |
Adamcolton (talk | contribs) No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 3: | Line 3: | ||
== Totient == | == Totient == | ||
The number of values k for which 1 ≤ k ≤ n and gcd(n,k) == 1. For any prime, φ(p) = p-1. | The number of values k for which 1 ≤ k ≤ n and gcd(n,k) == 1. For any prime, φ(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, φ(n)) = 1 | |||
== Modular Inverse == | |||
A<sup>-1</sup> * 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. | |||
Latest revision as of 18:12, 17 January 2016
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.
Primitive Root
Also called a generator rx 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. r0i % n will be a primitive root if gcd(i, φ(n)) = 1
Modular Inverse
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.