Finite Field Notes: Difference between revisions
Jump to navigation
Jump to search
Adamcolton (talk | contribs) Created page with "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 <e; k <e; n and gcd(n,k) == 1. For any prim..." |
Adamcolton (talk | contribs) No edit summary |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
I learned all this for cyclic keys, then I forgot it. This time I'm taking 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 & | 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.