 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 3 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 46438 Posts Moved to Math. Alex   2007-12-07, 15:17   #3
R.D. Silverman

Nov 2003

22×5×373 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

111111002 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!  Thread Tools Show Printable Version Email this Page 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 00:11.

Fri May 7 00:11:30 UTC 2021 up 28 days, 18:52, 0 users, load averages: 1.54, 1.66, 1.59