The Frobenius endomorphism is defined as:
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 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 . Working modulo this polynomial is the same thing as working in a “world” where . (You could of course work with a polynomial in the form but that would complicate things.)
So every element of can be written as . What happens when you apply the Frobenius endomorphism? Let’s see:
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 has many terms, but only the first and the last survive because all others are multiples of p. Since we’re working with coefficients modulo p, they are all zero.
Let’s continue. Since , then raising to the power of p won’t change them (yep, that’s Frobenius again). So we have:
There’s only left to bother us. If p is odd (not 2), then you can rearrange this as:
Now remember that we’re working in a “world” where . Then we get:
That’s why Frobenius is easy: “a” stays the same, all you need to do is multiply “b” with . But according to Euler’s criterion, since is not a square (if it were, wouldn’t be irreducible), we have . Then the formula gets much simpler:
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 .
sage: KR.<X> = GF(7)[]
This creates a polynomial ring with the X variable and coefficients in , 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 field using the variable X (I’m overwriting the X used in the ring, you could use other name) and modulus (so ). Let’s take an arbitrary element to the power of 7:
sage: (3*X + 2)^7 4*X + 2
Remeber when then . 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 , you can represent it as a quadratic extension of , which can be represented as a cubic extension of , which can be represented as a quadratic extension of .
For example, for built this way, with , 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.
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
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 🙂 )
Your blog helps a lot. I’ve been confused with Frobenius endomorphism with quadratic extension for two days.
Thank you!(from China)
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
This helped me greatly in understanding field extensions:
http://everything2.com/node/1674246
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.
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]]]
another question is can i implement pairing using sage, which tool is best for implementing pairing to see result at each step..
You can — I’ve done it myself, it’s very helpful.
There is a few workarounds required for using field towers, check this:
https://groups.google.com/d/msg/sage-support/0CEExpCEZmQ/qLicLWV2alIJ
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
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 ?
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? 🙂
It’s a nice piece.
Thank you for your article.