mersenneforum.org > Math On the basis of finite fields
 Register FAQ Search Today's Posts Mark Forums Read

 2007-12-07, 14:29 #1 meng_luckywolf   Dec 2007 316 Posts On the basis of finite fields I need solve this question: We know that a finite filed F_(2^2n) can be seen as the 2n-dimension linear space on F_2.If a is a primitive element in F_(2^2n), apparently,ord(a)=(2^2n)-1. And we choose an appropriate integer k, the set{1,a,a^2,...,a^(n-1);a^k,a^(k+1),a^(k+2),...,a^(k+n-1)} would be a basis of F_(2^2n) on F_2. My question is:If the integer k is choosen from 1 to ( (2^2n)-1 ),how many bases can we get? I did a test,and guess the answer is 2^(2n-1). But how can it prove?
 2007-12-07, 14:48 #2 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Moved to Math. Alex
2007-12-07, 15:17   #3
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by meng_luckywolf I need solve this question: We know that a finite filed F_(2^2n) can be seen as the 2n-dimension linear space on F_2.If a is a primitive element in F_(2^2n), apparently,ord(a)=(2^2n)-1. And we choose an appropriate integer k, the set{1,a,a^2,...,a^(n-1);a^k,a^(k+1),a^(k+2),...,a^(k+n-1)} would be a basis of F_(2^2n) on F_2. My question is:If the integer k is choosen from 1 to ( (2^2n)-1 ),how many bases can we get? I did a test,and guess the answer is 2^(2n-1). But how can it prove?

Huh? The question makes no sense to me. Any basis for GF(2^k) will be
a set of elements of size k. GF(2^k) forms (as you said) a vector space
of degree k over its ground field. Therefore any basis set has size k. Are you
perhaps asking for how many different normal bases exist? i.e. the number
of primitive elements?

 2007-12-07, 15:32 #4 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts The way I read it, he wants half of the base vectors to be 1, a, a^2, a^3, ... and the other half a^k, a^(k+1), a^(k+2), ... for a suitably chosen k. The question is how many distinct, proper bases you get if you let k vary. Alex Last fiddled with by akruppa on 2007-12-07 at 15:34 Reason: typo
2007-12-08, 04:44   #5
meng_luckywolf

Dec 2007

3 Posts

Quote:
 Originally Posted by akruppa The way I read it, he wants half of the base vectors to be 1, a, a^2, a^3, ... and the other half a^k, a^(k+1), a^(k+2), ... for a suitably chosen k. The question is how many distinct, proper bases you get if you let k vary. Alex
Thanks to akruppa, what he said is just what I wanted to express.

Who can help me solve that question?

2007-12-11, 06:08   #6
maxal

Feb 2005

25210 Posts

Quote:
 Originally Posted by meng_luckywolf I need solve this question: We know that a finite filed F_(2^2n) can be seen as the 2n-dimension linear space on F_2.If a is a primitive element in F_(2^2n), apparently,ord(a)=(2^2n)-1. And we choose an appropriate integer k, the set{1,a,a^2,...,a^(n-1);a^k,a^(k+1),a^(k+2),...,a^(k+n-1)} would be a basis of F_(2^2n) on F_2. My question is:If the integer k is choosen from 1 to ( (2^2n)-1 ),how many bases can we get? I did a test,and guess the answer is 2^(2n-1). But how can it prove?
I will use the following Lemma without a proof:

Lemma. The number of pairs of relatively prime polynomials (f,g) over GF(2) both of degree at most d equals 2^(2d+1) - 1.

Now to prove your result let us notice that any linear combination of the set {1,a,a^2,...,a^(n-1);a^k,a^(k+1),a^(k+2),...,a^(k+n-1)}
can be written as f(a) + a^k*g(a) where f(x), g(x) are some polynomials of degree at most n-1 with coefficients from GF(2).
Therefore, the elements of this set are linearly dependent over GF(2) if and only if a^k = f(a)/g(a) for some polynomials f(x), g(x) as above.
Since a^k goes over all non-zero elements of GF(2^(2n)) as k goes from 0 to 2^(2n)-2, the number of k that deliver a basis {1,a,a^2,...,a^(n-1);a^k,a^(k+1),a^(k+2),...,a^(k+n-1)} equals 2^(2n)-1 minus the number of elements of GF(2^(2n)) representable as f(a)/g(a) for some polynomials f(x), g(x) as above.

Note that if a non-zero element of GF(2^(2n)) is representable as f(a)/g(a) then f(x) and g(x) can be chosen relatively prime. Moreover, if f(a)/g(a) = u(a)/v(a) where f(x),g(x),u(x),v(x) are polynomials of degree at most n then a is a root of f(x)*v(x)-g(x)*u(x) that can be true only if f(x)*v(x)-g(x)*u(x) is the zero polynomial, i.e., f(x)*v(x)=g(x)*u(x). If in addition gcd(f(x),g(x))=1 and gcd(u(x),v(x))=1 then with necessity we have f(x)=u(x) and g(x)=v(x). Therefore, the number of elements of GF(2^(2n)) equals to the number of pairs of relatively prime polynomials f(x),g(x) with degree at most n-1. According to Lemma, this number is 2^(2(n-1)+1)-1=2^(2n-1)-1.

Finally, we have that the number of different bases of the form {1,a,a^2,...,a^(n-1);a^k,a^(k+1),a^(k+2),...,a^(k+n-1)} equals 2^(2n)-1 - (2^(2n-1)-1) = 2^(2n-1).

Last fiddled with by maxal on 2007-12-11 at 06:13

2007-12-13, 04:21   #7
meng_luckywolf

Dec 2007

112 Posts

Quote:
 Originally Posted by maxal I will use the following Lemma without a proof: Lemma. The number of pairs of relatively prime polynomials (f,g) over GF(2) both of degree at most d equals 2^(2d+1) - 1. Now to prove your result let us notice that any linear combination of the set {1,a,a^2,...,a^(n-1);a^k,a^(k+1),a^(k+2),...,a^(k+n-1)} can be written as f(a) + a^k*g(a) where f(x), g(x) are some polynomials of degree at most n-1 with coefficients from GF(2). Therefore, the elements of this set are linearly dependent over GF(2) if and only if a^k = f(a)/g(a) for some polynomials f(x), g(x) as above. Since a^k goes over all non-zero elements of GF(2^(2n)) as k goes from 0 to 2^(2n)-2, the number of k that deliver a basis {1,a,a^2,...,a^(n-1);a^k,a^(k+1),a^(k+2),...,a^(k+n-1)} equals 2^(2n)-1 minus the number of elements of GF(2^(2n)) representable as f(a)/g(a) for some polynomials f(x), g(x) as above. Note that if a non-zero element of GF(2^(2n)) is representable as f(a)/g(a) then f(x) and g(x) can be chosen relatively prime. Moreover, if f(a)/g(a) = u(a)/v(a) where f(x),g(x),u(x),v(x) are polynomials of degree at most n then a is a root of f(x)*v(x)-g(x)*u(x) that can be true only if f(x)*v(x)-g(x)*u(x) is the zero polynomial, i.e., f(x)*v(x)=g(x)*u(x). If in addition gcd(f(x),g(x))=1 and gcd(u(x),v(x))=1 then with necessity we have f(x)=u(x) and g(x)=v(x). Therefore, the number of elements of GF(2^(2n)) equals to the number of pairs of relatively prime polynomials f(x),g(x) with degree at most n-1. According to Lemma, this number is 2^(2(n-1)+1)-1=2^(2n-1)-1. Finally, we have that the number of different bases of the form {1,a,a^2,...,a^(n-1);a^k,a^(k+1),a^(k+2),...,a^(k+n-1)} equals 2^(2n)-1 - (2^(2n-1)-1) = 2^(2n-1).

"maxal",thank you!
Your method is very beautiful,I am full of gratitude for your help!

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Abstract Algebra & Algebraic Number Theory 3 2018-01-13 18:13 George M Miscellaneous Math 2 2018-01-01 21:37 devarajkandadai Number Theory Discussion Group 7 2017-12-06 01:46 paul0 Factoring 5 2015-11-18 06:16 Raman Miscellaneous Math 5 2013-06-12 13:54

All times are UTC. The time now is 15:26.

Sat Apr 10 15:26:29 UTC 2021 up 2 days, 10:07, 1 user, load averages: 2.13, 2.22, 2.17