libecc: Elliptic Curve Cryptography C++ Library

Main Page Reference Manual Compound List File List

Let $\mathbb{F}$ and $\mathbb{K}$ be fields. A field homomorphism is a function $\psi$ : $\mathbb{F}$ $\rightarrow$ $\mathbb{K}$ such that:

$\psi$ (a + b) = $\psi$ (a) + $\psi$ (b) for all a, b $\in$ $\mathbb{F}$
$\psi$ (a $\cdot$ b) = $\psi$ (a) $\cdot$ $\psi$ (b) for all a, b $\in$ $\mathbb{F}$
$\psi$ (1) = 1, $\psi$ (0) = 0

It can be proven that a homomorphism is injective. If $\psi$ is also surjective then the map is obviously a bijection and $\psi$ is in fact an automorphism. An automorphism is just an isomorphism of a system of objects onto itself.

In our case, the Frobenius map of the elements of $\mathbb{F}_{2^m}$ onto itself will turn out to be surjective and therefore be an automorphism: an isomorphism of the field onto itself.

The Frobenius homomorphism is a map named after the mathematician Frobenius, and its just 'cause he was born first that it has his name because all he did was realize that for a field with characteristic p we have (a + b)^p = a^p + b^p. I am not going to spill any more words on that, except that in our case p = 2 and if by now you can't even dream that (a + b)² = a² + b² then don't you think it will be easier for you start reading at the beginning of all of this?

Indeed, the Frobenius homomorphism for our field is defined as:

$\begin{matrix}\phi\colon \mathbb{F}_{2^m} &\to& \mathbb{F}_{2^m} \\ a &\mapsto& a^2 \end{matrix}$

This is clearly a field homomorphism because the three points listed above are fullfilled:

(a + b)² = a² + b² for all a, b $\in$ $\mathbb{F}$
(a $\cdot$ b)² = a² $\cdot$ b² for all a, b $\in$ $\mathbb{F}$
1² = 1, 0² = 0

Do I hear you say "yawn" yet? Ok, it gets worse. It is also clearly injective because every different value of a gives a different result when you square it (otherwise we wouldn't have a field) and if that alone isn't enough to convince you that it is bijective, then I could repeat for the third time that the reverse, the square root, also has just one (and unique) solution, so the map is surjective as well.

In other words, they don't come more automorphistic than this. But, this wasn't written for newbies (like myself, I just have more time to study, say) if we wouldn't provide an example anyway:

Consider the nice little field $\mathbb{F}$ _2³ with reduction polynomial t³ + t + 1 which has eight elements {0, 1, t, t+1, t², t²+1, t²+t, t²+t+1}. and lets make a table with those elements in the left column and the square of them in the right column:

a	a²
0	0
1	1
t	t²
t + 1	t² + 1
t²	t² + t
t² + 1	t² + t + 1
t² + t	t
t² + t + 1	t + 1

And magically every possible value appears in both columns. And the algebraic relationships are maintained too! For example, in the left column we have (t²) + (t² + t) = (t) then in the right column we have the corresponding equation (t² + t) + (t) = (t²).

Theory: The Frobenius map