Message Boards Message Boards

0
|
5985 Views
|
3 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Large Polynomials Over Galois Fields

Dave Lubbers, Zeta Associates
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 like
mycoefs = {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.
POSTED BY: Dave Lubbers
3 Replies
Sort By:
Let's for example set
In[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.

Sincerely
Udo.
POSTED BY: Udo Krause
Hi Dave,

Most of the trickery is not too bad, let's have
In[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.

Sincerely
Udo.
POSTED BY: Udo Krause
Hi Dave,

how is FromFieldElement[] implemented; did not found it in the first rate:
Needs["FiniteFields`"]

?FromFieldElement

Information::notfound: Symbol FromFieldElement not found. >>
Regards
Udo.
POSTED BY: Udo Krause
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract