0
|
6255 Views
|
3 Replies
|
2 Total Likes
View groups...
Share
GROUPS:

Large Polynomials Over Galois Fields

Posted 11 years ago
 The computer time required to create  polynomials of degree 50 or larger over GF(2^8) are prohibitive.  Is there an efficient way to create these polynomials. I have an array of polynomial coefficients in the form of GF(2^8)  indexes. Something likemycoefs = {1,34,12,157,..,87}I try to form a polynomial as a sum:mypoly = Sum[x^n FromFieldElement[field,mycoefs[[n+1]],{n,0,50}]Mathematica takes a very long time on this Sum.  I was hoping somebody had a better way.
3 Replies
Sort By:
Posted 11 years ago
 Hi Dave,how is FromFieldElement[] implemented; did not found it in the first rate:Needs["FiniteFields`"]?FromFieldElementInformation::notfound: Symbol FromFieldElement not found. >>RegardsUdo.
Posted 11 years ago
 Let's for example setIn[94]:= Remove[cfs]cfs = RandomInteger[{0, 2^8 - 1}, 50]Out[95]= {129, 168, 28, 120, 139, 157, 173, 28, 101, 8, 219, 134, \108, 43, 189, 10, 23, 186, 67, 232, 15, 15, 173, 144, 238, 115, 9, \211, 122, 114, 0, 22, 95, 161, 52, 163, 139, 7, 170, 172, 51, 185, \191, 12, 194, 59, 123, 211, 146, 227}up to 20 or 21 summands it works pretty well In[106]:= Sum[  x^n FromElementCode[GF[2, 8], cfs[[n + 1]]], {n, 0,(*Length[cfs]-1 *)    21}]  Out[106]=  x^9 Subscript[{0, 0, 0, 1, 0, 0, 0, 0}, 2] +   x Subscript[{0, 0, 0, 1, 0, 1, 0, 1}, 2] +   x^19 Subscript[{0, 0, 0, 1, 0, 1, 1, 1}, 2] +   x^3 Subscript[{0, 0, 0, 1, 1, 1, 1, 0}, 2] + x^12 Subscript[{0, 0, 1, 1, 0, 1, 1, 0}, 2] + x^2 Subscript[{0, 0, 1, 1, 1, 0, 0, 0}, 2] + x^7 Subscript[{0, 0, 1, 1, 1, 0, 0, 0}, 2] + x^15 Subscript[{0, 1, 0, 1, 0, 0, 0, 0}, 2] + x^17 Subscript[{0, 1, 0, 1, 1, 1, 0, 1}, 2] + x^11 Subscript[{0, 1, 1, 0, 0, 0, 0, 1}, 2] + Subscript[{1, 0, 0, 0,   0, 0, 0, 1}, 2] + x^8 Subscript[{1, 0, 1, 0, 0, 1, 1, 0}, 2] + x^6 Subscript[{1, 0, 1, 1, 0, 1, 0, 1}, 2] + x^5 Subscript[{1, 0, 1, 1, 1, 0, 0, 1}, 2] + x^14 Subscript[{1, 0, 1, 1, 1, 1, 0, 1}, 2] + x^18 Subscript[{1, 1, 0, 0, 0, 0, 1, 0}, 2] + x^4 Subscript[{1, 1, 0, 1, 0, 0, 0, 1}, 2] + x^13 Subscript[{1, 1, 0, 1, 0, 1, 0, 0}, 2] + x^10 Subscript[{1, 1, 0, 1, 1, 0, 1, 1}, 2] + x^16 Subscript[{1, 1, 1, 0, 1, 0, 0, 0}, 2] + x^20 Subscript[{1, 1, 1, 1, 0, 0, 0, 0}, 2] + x^21 Subscript[{1, 1, 1, 1, 0, 0, 0, 0}, 2]more summands slow down significantly.  Really fast is In[93]:= Sum[   x^n ElementToPolynomial[FromElementCode[GF[2, 8], cfs[[n + 1]]],      y], {n, 0, Length[cfs] - 1}] /. ElementToPolynomial[0, y] -> 0  Out[93]= 1 + x^37 + x^44 + x^32 y + x^5 y^2 + x^27 y^2 +   x^14 (1 + y) + x^22 (1 + y) + x^10 (1 + y + y^2) + x^21 (1 + y^3) +   x^28 (1 + y^3) + x^2 (y^2 + y^3) + x^24 (y^2 + y^3) +   x^50 (1 + y^2 + y^3) + x^13 (1 + y^3 + y^4) +   x^6 (1 + y + y^2 + y^3 + y^4) + x^36 (1 + y + y^2 + y^3 + y^4) + x^26 (1 + y^5) + x (y + y^5) + x^11 (1 + y^2 + y^5) + x^31 (y + y^2 + y^5) + x^45 (y^3 + y^5) + x^48 (y + y^3 + y^4 + y^5) + x^41 (1 + y + y^2 + y^3 + y^4 + y^5) + x^47 (1 + y + y^6) + x^25 (y + y^3 + y^6) + x^46 (y^2 + y^3 + y^6) + x^42 (1 + y^2 + y^3 + y^6) + x^19 (y + y^2 + y^3 + y^6) + x^40 (1 + y + y^4 + y^6) + x^43 (1 + y^2 + y^4 + y^6) + x^20 (1 + y + y^3 + y^4 + y^6) + x^49 (1 + y + y^2 + y^3 + y^4 + y^6) + x^29 (1 + y + y^5 + y^6) + x^30 (y + y^2 + y^5 + y^6) + x^7 (1 + y^2 + y^7) + x^34 (y^4 + y^7) +  x^35 (y^4 + y^7) + x^3 (1 + y^2 + y^3 + y^4 + y^7) + x^18 (y^2 + y^3 + y^5 + y^7) + x^33 (1 + y + y^3 + y^5 + y^6 + y^7)of course, never simplify that! Instead, turn back, e.g.In[118]:= x^33 PolynomialToElement[GF[2, 8], (1 + y + y^3 + y^5 + y^6 + y^7)]Out[118]= x^33 Subscript[{1, 1, 0, 1, 0, 1, 1, 1}, 2]whith some pattern matching trickery you can do that automatically.SincerelyUdo.
Posted 11 years ago
 Hi Dave,Most of the trickery is not too bad, let's haveIn[73]:= Remove[cfs]cfs = RandomInteger[{0, 2^8 - 1}, 50]Out[74]= {118, 123, 55, 190, 90, 83, 146, 249, 202, 186, 130, 180, \156, 74, 142, 190, 33, 180, 161, 136, 21, 20, 97, 182, 7, 187, 206, \37, 96, 124, 48, 15, 170, 158, 89, 182, 153, 66, 86, 251, 83, 251, \15, 83, 61, 39, 152, 162, 138, 188}and then get In[75]:= Plus @@ (Table[        x^n ElementToPolynomial[          FromElementCode[GF[2, 8], cfs[[n + 1]]], y], {n, 0,          Length[cfs] - 1}] /. ElementToPolynomial[0, y] -> 0)  /.   Times[Power[x, n_: 1],      z_] :> (x^n PolynomialToElement[GF[2, 8], z] /;       FreeQ[z, x]) // Timing  Out[75]= {0.015600, (y + y^2 + y^4 + y^5 + y^6 +     x^28 Subscript[{0, 0, 0, 0, 0, 1, 1, 0}, 2] +     x^30 Subscript[{0, 0, 0, 0, 1, 1, 0, 0}, 2] +     x^19 Subscript[{0, 0, 0, 1, 0, 0, 0, 1}, 2] +     x^46 Subscript[{0, 0, 0, 1, 1, 0, 0, 1}, 2] +     x^21 Subscript[{0, 0, 1, 0, 1, 0, 0, 0}, 2] +     x^11 Subscript[{0, 0, 1, 0, 1, 1, 0, 1}, 2] +     x^17 Subscript[{0, 0, 1, 0, 1, 1, 0, 1}, 2] +     x^12 Subscript[{0, 0, 1, 1, 1, 0, 0, 1}, 2] +     x^49 Subscript[{0, 0, 1, 1, 1, 1, 0, 1}, 2] +     x^29 Subscript[{0, 0, 1, 1, 1, 1, 1, 0}, 2] +     x^10 Subscript[{0, 1, 0, 0, 0, 0, 0, 1}, 2] +     x^37 Subscript[{0, 1, 0, 0, 0, 0, 1, 0}, 2] +     x^47 Subscript[{0, 1, 0, 0, 0, 1, 0, 1}, 2] +     x^6 Subscript[{0, 1, 0, 0, 1, 0, 0, 1}, 2] +     x^48 Subscript[{0, 1, 0, 1, 0, 0, 0, 1}, 2] +     x^13 Subscript[{0, 1, 0, 1, 0, 0, 1, 0}, 2] +     x^8 Subscript[{0, 1, 0, 1, 0, 0, 1, 1}, 2] +     x^32 Subscript[{0, 1, 0, 1, 0, 1, 0, 1}, 2] +     x^4 Subscript[{0, 1, 0, 1, 1, 0, 1, 0}, 2] +     x^9 Subscript[{0, 1, 0, 1, 1, 1, 0, 1}, 2] +     x^38 Subscript[{0, 1, 1, 0, 1, 0, 1, 0}, 2] +     x^23 Subscript[{0, 1, 1, 0, 1, 1, 0, 1}, 2] +     x^35 Subscript[{0, 1, 1, 0, 1, 1, 0, 1}, 2] +     x^14 Subscript[{0, 1, 1, 1, 0, 0, 0, 1}, 2] +     x^26 Subscript[{0, 1, 1, 1, 0, 0, 1, 1}, 2] +     x^33 Subscript[{0, 1, 1, 1, 1, 0, 0, 1}, 2] +     x^3 Subscript[{0, 1, 1, 1, 1, 1, 0, 1}, 2] +     x^15 Subscript[{0, 1, 1, 1, 1, 1, 0, 1}, 2] +     x^16 Subscript[{1, 0, 0, 0, 0, 1, 0, 0}, 2] +     x^18 Subscript[{1, 0, 0, 0, 0, 1, 0, 1}, 2] +     x^22 Subscript[{1, 0, 0, 0, 0, 1, 1, 0}, 2] +     x^36 Subscript[{1, 0, 0, 1, 1, 0, 0, 1}, 2] +     x^34 Subscript[{1, 0, 0, 1, 1, 0, 1, 0}, 2] +     x^7 Subscript[{1, 0, 0, 1, 1, 1, 1, 1}, 2] +     x^27 Subscript[{1, 0, 1, 0, 0, 1, 0, 0}, 2] +     x^20 Subscript[{1, 0, 1, 0, 1, 0, 0, 0}, 2] +     x^44 Subscript[{1, 0, 1, 1, 1, 1, 0, 0}, 2] +     x^5 Subscript[{1, 1, 0, 0, 1, 0, 1, 0}, 2] +     x^40 Subscript[{1, 1, 0, 0, 1, 0, 1, 0}, 2] +     x^43 Subscript[{1, 1, 0, 0, 1, 0, 1, 0}, 2] +     x^25 Subscript[{1, 1, 0, 1, 1, 1, 0, 1}, 2] +     x Subscript[{1, 1, 0, 1, 1, 1, 1, 0}, 2] +     x^39 Subscript[{1, 1, 0, 1, 1, 1, 1, 1}, 2] +     x^41 Subscript[{1, 1, 0, 1, 1, 1, 1, 1}, 2] +     x^24 Subscript[{1, 1, 1, 0, 0, 0, 0, 0}, 2] +     x^45 Subscript[{1, 1, 1, 0, 0, 1, 0, 0}, 2] +     x^2 Subscript[{1, 1, 1, 0, 1, 1, 0, 0}, 2] +     x^31 Subscript[{1, 1, 1, 1, 0, 0, 0, 0}, 2] +     x^42 Subscript[{1, 1, 1, 1, 0, 0, 0, 0}, 2])}I'missed only the x-free polynomial in y to transform back.SincerelyUdo.
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.