Hi,
How do i perform exponentiation to a composite field element? say the element is of the field GF(((2^2)^2)^2) and constructed from the following polynomials:
x^2 + x + {1000}
x^2 + x + {10}
x^2 + x + 1
please provide me with the working as detail as possible as im very confused with composite field arithmetic
Deducing as well as I can from your unexplained notation from which I have removed the confusing braces.
Since 10 satisifies x^2+x+1=0 and the field has characterstic 2
we have 10^2+10+1=0
10^2 = 10 + 1 = 11
11^2 = (10 + 1)^2 = 10^2 +1^2 = 11 + 1 = 10 (no 2.10.1 term since characteristic is 2)
Now can you work out 100^2 etc in the same way?
Thanks for the reply. But honestly I still dont quite get it. Forgive me for my insufficient knowledge in composite filed arithmetic. Can you show me how to obtainOriginally Posted by alunw
where by
is an element of composite field
which is constructed from the following field polynomials:
,
and
and i cant work out 100^2 as well T-T
I can't work out what alpha^4 is because I don't understand your notation properly, but whatever it is you should work it out by first finding alpha^2 and then squaring that again. In all that follows I'm assuming addition is meant to be done using a bitwise XOR, whereas it might be that you actually have the elements successive powers of some generator of the cyclic group of non-zero elements, so that addition needs to be done using a table.
Note that given that 10 is a root of x^2+x+1 then we had enough information to work out 10*10. 10+1 cannot equal 10,0 or 1 so it makes sense to denote it by 11, and it will turn out we can complete the multiplication and addition tables for the field of 4 elements. 10*11 = 10*10 + 10*1 = 11 + 10 = 1, 11*11 = 10*10+1 = 11+1 = 10
Also 11*11+11+1 = 10 + 11 + 1 = 0 since characteristic is 2. In other words once we found one root of x^2+x+1 the other followed.
Next we presumably discover that the polynomial x^2+x+10 has no roots in our first splitting field. So we introduce another element 100 which is a root of this
Then we have 100^2+100 +10 = 0 so
100^2 = 100 + 10.
100+10 is certainly not equal to any of 0,1,10,11 or 100, so we are justified in denoting it by 110, and we can reason the same way to allow us to define 101 and 111 as well,
and work out what they square to:
101^2 = 100^2+1 = 111
110^2 = 100^2+10^2 = 110 +11 = 101
111^2 = 100^2+11^2 = 110+10 = 100
Incidentally we see now that 100^16=110^8=101^4=111^2=100. That means that 100^15=1. but 100^3 = 110*100 = 100*100+10*100=110+10*100 which cannot be 1
and 100^5 = 100*100^4=100*110^2 = 100*101 = 110+100 = 10. This shows that
our field must contain at least 16 elements.
So far we have 8 elements, but in fact we want at least 16, and this time we have more work to do to work out a complete multiplication table. In particular we don't yet know what 10*100 or 11*100 is. Also the other root of x^2+x+10 must be 101 since that is the only factor that could give us x^2+x+10 when we multiply the factors out and indeed 100*101 = 100*100 + 100 = 10.
Now 10*100 is not 0, or 1, or 10, or 11 (since 10*10=11) or 100, or 110 (since 100*100=110). Can it be 101 or 111?
Note that (10*100)^2 = 10^2*100^2 = 11*110 = 11*100+11*10 = 10*100+100+1. Thus 10*100 is not 101 otherwise we would have (10*100)^2 = 0.
Now if we have 10*100 = 111 then we have
100=11*111 = 10*111+111 = 10*100 + 10*11 + 111 = 111 + 10*11 + 111 = 1
Since that is certainly not the case we see that 10*100 must be a 9th element, and we may as well denote it by 10000. And we have 10000^2 = (10*100)^2 = 11*110 = 10*110+110 = 10*100 + 11 + 110 = 10*100+101=10101.
That would be enough information to complete a multiplication table. However, I made a fairly arbitrarary decision in decreeing 10*100=10000, since clearly I might just as well have assigned that value to one of the other multiplications I could not complete without adding a new element to the eight I already had. I suppose 10*100 is the logical choice to assign the value 10*100 to, as it the first entry in the multiplication table that we got stuck on.
This is clearly all very laborious but we could now complete the multiplication table for a field of 16 elements. Then we would have to (and could) show that x^2+x+1000 did no have any root in our field of 16 elements, and posit 10000 as one of its two roots, at which point we would know that 10000^2 = 11000. Then the same kind of reasoning would presumably eventually lead us to realise that 10*10000 and 100*10000 and 1000*10000 were all tricky products to calculate. Probably the best way to proceed would be to calculate all the powers of 10000 find its order (which presumably is a factor of 255 and probably is 255 though I don't know for sure - there certainly is an element of order 255 somewhere in the multiplicative group of non-zero elements in that field and very likely some structure theorem tells us that this is one of them).
In practice I'm sure one would use GAP or some similar program. I think GAP can do calculations in any finite field of reasonable order. Really all I'm doing here is some kind of mathematical equivalent of a Sudoko puzzle.
Groups, Algebra and Programming - it is a computer algebra system, and it is free to use if you want to. See here for more details, or see Wiki.
It allows you to do stuff with groups and other algebraic structures, like see if two permutation groups are isomorphic (and much nicer things too).
how do we do for cube instead of square? say 10000^3??
i do find it very difficult to calculate 10*10000 and 100*10000 and 1000*1000. say if i would like to find 100000^2, how do i justify i shd go for (100*1000)^2 or (10*10000)^2??
and you mentioned "...calculate all the powers of 10000 find its order..." what does this order means??
thanks alot!
  |
LinkBack URL
About LinkBacks