mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-12-07, 14:29   #1
meng_luckywolf
 
Dec 2007

316 Posts
Thumbs up 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?
meng_luckywolf is offline   Reply With Quote
Old 2007-12-07, 14:48   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Moved to Math.

Alex
akruppa is offline   Reply With Quote
Old 2007-12-07, 15:17   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by meng_luckywolf View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2007-12-07, 15:32   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2007-12-08, 04:44   #5
meng_luckywolf
 
Dec 2007

3 Posts
Default

Quote:
Originally Posted by akruppa View Post
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?
meng_luckywolf is offline   Reply With Quote
Old 2007-12-11, 06:08   #6
maxal
 
maxal's Avatar
 
Feb 2005

25210 Posts
Default

Quote:
Originally Posted by meng_luckywolf View Post
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
maxal is offline   Reply With Quote
Old 2007-12-13, 04:21   #7
meng_luckywolf
 
Dec 2007

112 Posts
Default

Quote:
Originally Posted by maxal View Post
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!
meng_luckywolf is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Ideal groupings in number fields carpetpool Abstract Algebra & Algebraic Number Theory 3 2018-01-13 18:13
Finite differences for the win George M Miscellaneous Math 2 2018-01-01 21:37
Pseudoprimes in special fields devarajkandadai Number Theory Discussion Group 7 2017-12-06 01:46
Generating reduced basis for special-q paul0 Factoring 5 2015-11-18 06:16
Questions about Number Fields 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.