(what is) a multiplicative order of a finite field?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

(what is) a multiplicative order of a finite field?

Postby >-) » Wed Jul 23, 2014 10:57 pm UTC

https://en.wikipedia.org/wiki/Trigonome ... lois_field
According to this page, zeta is an element in the multiplicative order GI(q), the gaussian integers over a given galois field. However, the multiplicative order page
https://en.wikipedia.org/wiki/Multiplicative_order
says k is the multiplicative order where a^k = 1 (mod n) for given a and n. it doesn't explain how to find the order of a field.

Since finite fields are cyclic and elements can be found by repeatedly taking the product of an generator, i thought a might be the generator and n the irreducible polynomial. but then isn't k just 0? And that can't be since zeta is an element of N so the order must be a set of some sort.

So how do you find the multiplicative order of some field?

also, as a tangentially related question, this answer on stackoverflow claims there are 8 possible generators for a finite field. does this apply to all finite fields or just F9?
http://math.stackexchange.com/a/373296

User avatar
Dopefish
Posts: 855
Joined: Sun Sep 20, 2009 5:46 am UTC
Location: The Well of Wishes

Re: (what is) a multiplicative order of a finite field?

Postby Dopefish » Thu Jul 24, 2014 1:30 am UTC

Just skimming the wiki page for multiplicative order you have there, k is the smallest positive integer k, such that a^k = 1 mod n. Since it needs to be positive, k can't be 0, so just trying increasingly large integers starting at k=1 should work to find it.

I don't actually know anything about this outside of my wiki skim though, so there might be smarter ways to figure out the smallest such k and hence determine the multiplicative order.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: (what is) a multiplicative order of a finite field?

Postby Qaanol » Thu Jul 24, 2014 1:39 am UTC

>-) wrote:https://en.wikipedia.org/wiki/Trigonometry_in_Galois_fields#Trigonometry_over_a_Galois_field
According to this page, zeta is an element in the multiplicative order GI(q), the gaussian integers over a given galois field.

It says ζ is an element of multiplicative order N, in the specified field.

That means N is the least positive integer such that ζN=1.

Lagrange’s theorem guarantees that the order of an element divides the order of the group. Note that for any field, the set of nonzero elements forms a group under multiplication.
wee free kings

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: (what is) a multiplicative order of a finite field?

Postby z4lis » Thu Jul 24, 2014 1:52 am UTC

If F is any field for which x^2 + 1 = 0 has no solution, then we can form a new field by adjoining that root, just like we do with real/complex numbers. We can do this with any field, not just the finite ones, but if we started with an order N field, then the new field consists of things like a + bi where a,b live in the original field (just like with complex numbers). So the new field has N^2 elements.

The stackexchange answer only applies to F9. If you start with F3, the field with 3 elements, then you find that nothing squares to -1 = 2, and so you can adjoin the solution to x^2 + 1 to get a new field, which happens to have 9 elements, and so must be the field with 9 elements. Now, many of those elements are not generators. For example,

x^2 = -1
x^3 = -x
x^4 = 1
x^5 = -1

etc. Since taking powers of x doesn't cycle through everything in the field that's not zero, x is not a generator. We see it has multiplicative order 4 from our computation. Now, look at

(x+1)^2 = x^2 + 2x + 1 = 2x = -x
(x+1)^3 = -x(x+1) = -x^2 - x = 1 - x
(x+1)^4 = (x+1)(1-x) = 1 - x^2 = 2 = -1
(x+1)^5 = -(x+1) = -1 - x
(x+1)^6 = -(x+1)(x+1) = x
(x+1)^7 = x(1+x) = x - 1
(x+1)^8 = (x-1)(x+1) = x^2 -1 = -2 = 1

and so taking repeated powers of x+1 cycles all the way through the nonzero things in the field. Note that since there are NINE things in the field, we want our generator be order 8 under MULTIPLICATION, and they're all up there in that list.

Note that the multiplicative order is always a number, never a set. It's the smallest number of times you can multiply something with itself to get 1, the identity under multiplication.

Compare this to the additive order, which is how many times you have to add something to itself to get 0, the identity for addition. For a finite field of order p^r, this is always p. For this reason, I'd say that when someone is talking about the order of an element in a field, they typically mean the multiplicative order.

The neat trick that is mentioned in the thread is the Frobenius automorphism. It's an important symmetry of a finite field of order p, which is just taking x to x^p. This preserves addition and multiplication (since we're working mod p) and so if a has order 4, then a^3 does, too. You can see this in the above example. x^3 = -x in that example, and so you can check that -x has order 4, just like x does. Similarly, (1+x)^3 = 1^3 + x^3 = 1-x is also a generator, since it has order 8.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: (what is) a multiplicative order of a finite field?

Postby >-) » Thu Jul 24, 2014 2:27 am UTC

Qaanol wrote:That means N is the least positive integer such that ζN=1.


So is ζ the value in GI for which N is smallest in ζ^N=1?
For example, if QI = {1, i, -1}, then ζ = 1 because 1^1 = 1, i^4 = 1, (-1)^2 = 1
does that sound right?

----

z4lis wrote:Now, look at

(x+1)^2 = x^2 + 2x + 1 = 2x = -x
(x+1)^3 = -x(x+1) = -x^2 - x = 1 - x
(x+1)^4 = (x+1)(1-x) = 1 - x^2 = 2 = -1
(x+1)^5 = -(x+1) = -1 - x
(x+1)^6 = -(x+1)(x+1) = x
(x+1)^7 = x(1+x) = x - 1
(x+1)^8 = (x-1)(x+1) = x^2 -1 = -2 = 1

and so taking repeated powers of x+1 cycles all the way through the nonzero things in the field. Note that since there are NINE things in the field, we want our generator be order 8 under MULTIPLICATION, and they're all up there in that list.


if x+1 is a generator for F9 with irreducible polynomial x^2+1, then we can have

E0 = 0
E1 = 1
E2 = (x+1)*E1 = x+1
E3 = (x+1)*E2 = x^2+2x+1 = 2x
E4 = (x+1)*E3 = 2x^2+2x = 2x-2 = 2x+1
E5 = (x+1)*E4 = 2x^2+3x+1 = 2x^2+1 = -1 = 2
E6 = (x+1)*E5 = 2x+2
E7 = (x+1)*E6 = 2x^2+4x+2 = 4x = x
E8 = (x+1)*E7 = x^2+x = x-1 = x+2

Where En is the nth element of F9

E8 + E1 = 1 + x+2 = x+3 = x = E7

but according to the table on the wikipedia page https://en.wikipedia.org/wiki/Finite_field#F9_2
E8 + E1 = E2 which is x+1

so what am i doing wrong.

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: (what is) a multiplicative order of a finite field?

Postby Nitrodon » Thu Jul 24, 2014 7:21 am UTC

You're doing nothing wrong. There are two different tables you can make like that for F9, depending on the choice of generator. The generator x+1 corresponds to either E6 or E8 in the table on the Wikipedia page, while E2 in that table corresponds to either x+2 or 2x+2.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: (what is) a multiplicative order of a finite field?

Postby Qaanol » Thu Jul 24, 2014 10:35 pm UTC

>-) wrote:
Qaanol wrote:That means N is the least positive integer such that ζN=1.


So is ζ the value in GI for which N is smallest in ζ^N=1?
For example, if QI = {1, i, -1}, then ζ = 1 because 1^1 = 1, i^4 = 1, (-1)^2 = 1
does that sound right?

Not quite.

ζ is *a* value in the group, with the property that ζN=1, and for any positive exponent n<N, then ζn≠1. There could be many elements of the set that have the same property, and ζ is one of them.

For example, consider the field of integers mod 5. There are 4 non-zero elements, which form a group under multiplication.
The order of 1 in that group is 1
The order of 2 in that group is 4
The order of 3 in that group is 4
The order of 4 in that group is 2

It is probably worth noting that, for any finite field, its multiplicative subgroup is cyclic, which means it has a generator. The Wikipedia article you linked does not expressly require that ζ be a generator (no restrictions are placed on N), but taking ζ as a generator lets you define the trig functions for all elements.

What do you mean by ‘QI’? If you are just using it as an example of a set, then it does not make sense to talk about the order of an element without having some group structure. If you include -i as well then you have a multiplicative group and:
The order of 1 is 1
The order of -1 is 2
The order of i is 4
The order of -i is 4

You could set ζ equal to any of {1, -1, i, -1}, and that would tell you the corresponding value of N. Alternatively, if you want ζ to generate the group, then you would have to pick either ζ=i or ζ=-i.
wee free kings

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: (what is) a multiplicative order of a finite field?

Postby mike-l » Fri Jul 25, 2014 2:04 am UTC

Qaanol wrote:ζ is *a* value in the group, with the property that ζN=1, and for any positive exponent n<N, then ζn≠1. There could be many elements of the set that have the same property, and ζ is one of them.

In fact, unless N = 1 or 2, there will always be others. If 1<p<N is coprime to N, then ζp also has order N. Such a p exists for all N > 2.

What do you mean by ‘QI’?

Fairly sure he meant GI.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
Plasma_Wolf
Posts: 148
Joined: Mon Aug 22, 2011 8:11 pm UTC

Re: (what is) a multiplicative order of a finite field?

Postby Plasma_Wolf » Tue Jul 29, 2014 4:18 pm UTC

Zeta is (in in the case of algebraic topics) reserved for this kind of operation. It's named a root of unity, precisely because raising it to a certain power gives 1. My algebra lecturer usually writes "root of 1".

Zeta_n (I'll use z as zeta from now on) is the n-th root of unity. This is how they're usually being shown, if you are looking for a specific multiplicative order. So by definition, if z is an n-th root of unity, then z^n=1. In the complex field, but also in the algebraic closure of Q, these roots of 1 are the roots of the co called "cyclotomic polynomials". Ask for a cyclotomic polynomial in wolframalpha, and you should get a nice image of the roots in the complex plane. They are on the unit circle, as expected. From there, it's also easy to understand how multiplying z for some times gets you along in the list of roots of unity. It's just moving along the circle bit by bit. Taking any of the roots you see on the circle to the power n, and you'll get back to 1 on the real line again. So here you can see that the element of a certain order in a galois field and an element of a certain order in a finite multiplicative field (like mod 11*), are very much alike

The cyclotomic polynomials and the roots of unity are much used in Galois theory. I have been working with a Galois extension for my master thesis. I had to find 13 generators of the Mordell-Weil group of an elliptic curve (that is defined with a t parameter over a function field). The generators themselves can (currently at least) not be given explicitly, but by showing that there is a galois group acting on E(Q(t)), I did manage to show that the generators were closely related.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests