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?

Moved to Math.

Alex

[QUOTE=meng_luckywolf;120139]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?[/QUOTE]


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?

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

[quote=akruppa;120149]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[/quote]

Thanks to akruppa, what he said is just what I wanted to express. :smile:

Who can help me solve that question?

[QUOTE=meng_luckywolf;120139]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?[/QUOTE]

I will use the following Lemma without a proof:

[b]Lemma.[/b] 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).

:smile:[quote=maxal;120410]I will use the following Lemma without a proof:

[B]Lemma.[/B] 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).[/quote]


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