20071207, 14:29  #1 
Dec 2007
3_{16} 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 2ndimension 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^(n1);a^k,a^(k+1),a^(k+2),...,a^(k+n1)} 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^(2n1). But how can it prove? 
20071207, 14:48  #2 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Moved to Math.
Alex 
20071207, 15:17  #3  
Nov 2003
1110100100100_{2} Posts 
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? 

20071207, 15:32  #4 
"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 20071207 at 15:34 Reason: typo 
20071208, 04:44  #5  
Dec 2007
3 Posts 
Quote:
Who can help me solve that question? 

20071211, 06:08  #6  
Feb 2005
252_{10} Posts 
Quote:
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^(n1);a^k,a^(k+1),a^(k+2),...,a^(k+n1)} can be written as f(a) + a^k*g(a) where f(x), g(x) are some polynomials of degree at most n1 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 nonzero 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^(n1);a^k,a^(k+1),a^(k+2),...,a^(k+n1)} 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 nonzero 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 n1. According to Lemma, this number is 2^(2(n1)+1)1=2^(2n1)1. Finally, we have that the number of different bases of the form {1,a,a^2,...,a^(n1);a^k,a^(k+1),a^(k+2),...,a^(k+n1)} equals 2^(2n)1  (2^(2n1)1) = 2^(2n1). Last fiddled with by maxal on 20071211 at 06:13 

20071213, 04:21  #7  
Dec 2007
11_{2} Posts 
Quote:
"maxal",thank you! Your method is very beautiful,I am full of gratitude for your help! 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Ideal groupings in number fields  carpetpool  Abstract Algebra & Algebraic Number Theory  3  20180113 18:13 
Finite differences for the win  George M  Miscellaneous Math  2  20180101 21:37 
Pseudoprimes in special fields  devarajkandadai  Number Theory Discussion Group  7  20171206 01:46 
Generating reduced basis for specialq  paul0  Factoring  5  20151118 06:16 
Questions about Number Fields  Raman  Miscellaneous Math  5  20130612 13:54 