# The Frobenius endomorphism with finite fields

The Frobenius endomorphism is defined as:

$\Phi(x)=x^p$

where p is the characteristic of the ring you’re working with. Simple, right?

If you’re working with a field with prime order, then Frobenius is actually the identity map. Since the order of the multiplicative subgroup is p, when you raise to the power of p you get back to x due to Fermat’s little theorem. Things get more interesting when you’re working with a extension field (i.e. a field which order is a prime power).

I’m studying pairings for my master’s degree and the Frobenius endomorphism appears all the time in their computation. For example, you need to do a “final exponentation” which can be split in multiple exponentiations, and some of them are to the power of p. This is good because powering to p is “easy” due to Frobenius, or at least all the papers I read said so. But for a while I couldn’t see why, and that’s the reason I’m posting this. It’s really easy; it’s just not that obvious to see why.

### Why Frobenius is easy?

Say you’re working with a quadratic extension, that is, with a field $GF(p^2)$ where p is a prime. You can represent this group with polynomials of degree 1 which can be added the usual way and multiplied taking the result modulo a irreducible polynomial of degree 2. To understand why this makes sense, I recommend this excellent write-up at Everything2. Assume that you pick a irreducible polynomial in the form $X^2-\beta$. Working modulo this polynomial is the same thing as working in a “world” where $X^2 = \beta$. (You could of course work with a polynomial in the form $X^2 + aX + b$ but that would complicate things.)

So every element of $GF(p^2)$ can be written as $a + bX$. What happens when you apply the Frobenius endomorphism? Let’s see:

$(a + bX)^p = (a^p + b^pX^p)$

Why is that so? That’s a known fact about the Frobenius, check the explanation at Wikipedia for more details. But basically, the expansion of $(a + bX)^p$ has many terms, but only the first $(a^p)$ and the last $(b^pX^p)$ survive because all others are multiples of p. Since we’re working with coefficients modulo p, they are all zero.

Let’s continue. Since $a, b \in GF(p)$, then raising to the power of p won’t change them (yep, that’s Frobenius again). So we have:

$(a + bX)^p = (a^p + b^pX^p) = (a + bX^p)$

There’s only $X^p$ left to bother us. If p is odd (not 2), then you can rearrange this as:

$(a + bX)^p = (a + bX^p) = (a + b(X^2)^{(p-1)/2}X)$

Now remember that we’re working in a “world” where $X^2 = \beta$. Then we get:

$(a + bX)^p = (a + b(X^2)^{(p-1)/2}X^p) = (a + b\beta^{(p-1)/2}X)$

That’s why Frobenius is easy: “a” stays the same, all you need to do is multiply “b” with $\beta^{(p-1)/2}$. But according to Euler’s criterion, since $\beta$ is not a square (if it were, $X^2-\beta$ wouldn’t be irreducible), we have $\beta^{(p-1)/2} \equiv -1 \pmod{p}$. Then the formula gets much simpler:

$(a + bX)^p = (a-bX)$

### A concrete example

Just for the sake of concreteness, let’s work out an example. I’ll use Sage for that, but I’ll explain what each command does.

sage: K = GF(7)

We create a field with 7 elements (that’s actually integers modulo 7).

sage: K(5)^7
5

We take the element 5 and power to 7. We get 5 again. If you don’t believe it works for all elements:

sage: [(x,x^7) for x in K]
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]

Let’s create $GF(7^2)$.

sage: KR.<X> = GF(7)[]

This creates a polynomial ring with the X variable and coefficients in $GF(7)$, just to allow us to specify the modulus in the next step:

sage: K2.<X> = GF(7^2, modulus=X^2+1)

We create the $GF(7^2)$ field using the variable X (I’m overwriting the X used in the ring, you could use other name) and modulus $X^2+1$ (so $\beta = -1$). Let’s take an arbitrary element to the power of 7:

sage: (3*X + 2)^7
4*X + 2

Remeber when $\beta = -1$ then $(a + bX)^p = (a-bX)$. And modulo 7, -3 is actually 4, so the result is correct (of course!). Again, if you don’t believe it works for all elements:

sage: all(x^7 == (x.vector()[0] - x.vector()[1]*X) for x in K2)
True

This checks, for all elements in the field K2, if the element raised to the power of 7 is equal to the element built with our special formula. The method vector() returns the coefficients of the polynomial as a list. The all function is a relatively unknown function of Python that returns True if all the elements of the iterable passed to it evaluate to True (there’s any(iter) too).

### Extensions of higher degree

The trick to calculate the Frobenius endomorphism also works for extensions of higher degree. When implementing them, usually using a tower of extensions is more efficient then using a direct extension. For example, when working with $GF(p^{12})$, you can represent it as a quadratic extension of $GF(p^6)$, which can be represented as a cubic extension of $GF(p^2)$, which can be represented as a quadratic extension of $GF(p)$.

For example, for $(a + bX) \in GF(p^{12})$ built this way, with $a, b \in GF(p^6)$, you just apply the same trick explained above. The only difference is that a and b to the power of p aren’t a and b themselves, but that’s not a problem, you just apply the same trick recursively.

## 16 thoughts on “The Frobenius endomorphism with finite fields”

1. emmett sisk says:

Hi,

This is rather a question I guess…If you could help me understand this:
I know that the Frobenius map is an isomorphism when we consider the finite field F_{p} to itself, but how about the map \bar{F_{p}} that is the map from the closure of the finite field to itself. Why is that map an isomorphism? What is the actual map, what is sent to what? I thank you for your time

2. Hi Emmett.

Wikipedia shows why it’s an homomorphism:
http://en.wikipedia.org/wiki/Frobenius_endomorphism#Definition
Notice that the proof applies to any field with characteristic p, including the closure of F_p.

To prove it’s an isomorphism, prove that its inverse is also an homomorphism in the same way. The map is f(x) = x^p, it’s inverse being f^{-1}(x) = (x^{-1})^p. It sends any element in the closure of F_p to another element in the closure of F_p.

Sorry for lack of rigour here… I would suggest you to ask the folks at http://mathoverflow.com if you have further questions (I’d be glad to help you, it’s just that I’m not a mathematician 🙂 )

3. Yang Li says:

Your blog helps a lot. I’ve been confused with Frobenius endomorphism with quadratic extension for two days.
Thank you!(from China)

4. khalid says:

Hi,
I am new to pairing field, right now i am working on F(p^12) field constructed by towering (F(p)^2)^2)^3), i am confused how to build this field, could you please help me with some examples. thnaks

1. khalid says:

i have already read it but still some confusion i ask you by simple example like: i have a prime field F(p){p= 0,1,2,3,4} if i want to extend it to F(p^2) than how??? if you have time kindly reply

First, you need an irreducible quadratic polynomial, e.g. f(x) = x^2 – t, for some t in F(p). If t is a quadratic non-residue (there is no square root for it in F(p), then x^2 + t is guaranteed to be irreducible.

In particular, in F(5), 3 and 4 are non-residues. Let’s pick f(x) = x^2 – 3 as irreducible polynomial.

In this case, F(5^2) is composed of all polynomials with degree at most 1: {0 + 0x, 0 + 1x, 0 + 2x, …, 1 + 0x, 1 + 1x, …}. There are 25 elements.

To add or multiply, you do the operation as a regular polynomial over F(5), then reduce the result modulo f(x), which is x^2 + 3 in our case.
To reduce, not that reducing modulo f(x) means that f(x) is equal to 0. Therefore, x^2 – 3 = 0, which implies that x^2 = 3. This means that, to reduce modulo f(x), just replace any x^2 by 3.

5. khalid says:

Thanks for your help, but i want to put it this way
if i need to represent any number like ‘4’ from Fp to Fp^12 by using towering technique (F(p)^2)^2)^3),,
For F(p)^2 it will become [4 0]using(a+ib), what would be the result in F(p)^4 and F(p)^12(here i am using complex numbers).

Using your notation, it would be [[[4 0] [0 0]] [[0 0] [0 0]] [[0 0] [0 0]]]

6. khalid says:

another question is can i implement pairing using sage, which tool is best for implementing pairing to see result at each step..

7. curious says:

I am getting this error in sage:
sage: K2. = GF(7^2, modulus=X^2+1)
File “”, line 1
K2. = GF(Integer(7)**Integer(2), modulus=X**Integer(2)+Integer(1))
^
SyntaxError: invalid syntax

Sorry, somehow any content between brackets in the post was cut. I’ve fixed it. It’s supposed to be

K2.<X> = ...
8. sherif says:

F = GF(next_primt(2^80))
x = F[‘x’].gen()
f = x^5 + x^3 + 1
H = HyperellipticCurve(f, 0)
J = H.jacobian()(F)
P = H.lift_x(F(3))
D = J(P)

is D the divisor? and we can be multiplied to random integer to generate a secure parameters like the one used with elliptic curve ?

9. Christopher says:

Hey,
this introduction is realy nice written. But there is a state left, I would like to see, just to be sure.

If we consider F_q^4 (for any prime order q), then we are able to apply the given theory as well. The Frobenius still holds (a+b)^q=a^q +b^q, since q is just a multiple of p, and we have a prime characteristic p. So lets build F_q^4 upon F_q^2[X]/(X^2-r), then we Take an Element of that parametrisation: A+BX with A,B in F_q^2. Lets write those like the upper given part:
A=a+bX, B=c+dX. There is the first problem for any lower kind of reader: Is that X the same X as above? So we take the isomorphism F_q^2 = F_q[X]/(X^2-t), as given above.

Lets guess, those X are the same, what do we get then, by appending the Frobenius?
(a+bX + (c+dX)X)^q = ( a + dX^2 + (b+c)X )^q

Now we have some trouble. There is a X^2 and we have two relations: X^2=r and X^2=t, but r in F_q^2 and t in F_q. What shall we take then? 🙂

Well the whole theory says: F_q^4 is isomorphic to F_q / (f), where deg(f)=4 and f is irreducible. If we use (X^2-r)(X^2-t)=X^4- (r+t)X^2 +rt

This would be a native way, but this won’t end up well. Any recommendations? 🙂

10. Joseph says:

It’s a nice piece.