Polynomial representation over GF(2^n)

[Oleksandr Kazymyrov]

Hi all,

Continuing the question...

Input data:

sage: K=GF(2^8,'a',modulus=ZZ['x']("x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + 1"))

sage: K.multiplicative_generator()

a^4 + a^3 + a

sage: P=PolynomialRing(K,'x')

sage: pol=P.random_element(5)

sage: pol

(a^7 + a^5 + a^3 + 1)*x^5 + (a^5 + a^4 + a^3 + a^2 + a + 1)*x^4 + (a^7 + a^3 + a^2 + a)*x^3 + (a^5 + a^2)*x^2 + (a^6 + a^5 + a^4 + 1)*x + a^3

1. How to represent pol using multiplicative generator? The output must be b^(i1)*x^5 + b^(i2)*x^4 + b^(i3)*x^3 + b^(i4)*x^2 + b^(i5)*x + a^3, where b = K.multiplicative_generator(), i1-i5 logarithmic representation of (a^7 + a^5 + a^3 + 1), (a^5 + a^4 + a^3 + a^2 + a + 1)...

I have a correct function:

sage: b=K.multiplicative_generator()
sage: P(["({0})^{1}".format(b,i.log(b)) for i in pol.coeffs()]) == pol
True

sage: ["({0})^{1}".format(b,i.log(b)) for i in pol.coeffs()]

['(a^4 + a^3 + a)^27', '(a^4 + a^3 + a)^234', '(a^4 + a^3 + a)^195', '(a^4 + a^3 + a)^134', '(a^4 + a^3 + a)^79', '(a^4 + a^3 + a)^101']

If I have one program then the above method suits me. But if two, i.e. one program represents polynomial in the form b^(i1)*x^5 ... and returns b and another program tries to restore it, then I worry about the phrase

The docs for multiplicative_generator() say: "return a generator of 
the multiplicative group", then add "Warning: This generator might 
change from one version of Sage to another." 

2. So the question is how to uniquely reconstruct the original pol, if I have modulus, multiplicative generator and representation of pol as b^(i1)*x^5...?

Regards,

Oleksandr

[Oleksandr Kazymyrov]

And one more.

The following is quite strange:

sage: K=GF(2^8,'a',modulus=ZZ['x']("x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + 1"))

sage: b=K.multiplicative_generator()

sage: c=K(0)

sage: c.log(b)

0

sage: c=K(1)

sage: c.log(b)

0

How to determine when c is 0 and when 1? Perhaps log should return -1 for finite fields when c=0?

Kind regards,

Oleksandr

[Martin Albrecht]

On Wednesday 13 Jun 2012, Oleksandr Kazymyrov wrote:
> And one more.
>
> The following is quite strange:
> sage: K=GF(2^8,'a',modulus=ZZ['x']("x^8 + x^7 + x^6 + x^4 + x^3 + x^2 +
> 1")) sage: b=K.multiplicative_generator()
> sage: c=K(0)
> sage: c.log(b)
> 0
> sage: c=K(1)
> sage: c.log(b)
> 0
>
> How to determine when c is 0 and when 1? Perhaps log should return
> -1 for finite fields when c=0?

Yep, this looks like a bug. Can you open a ticket and perhaps provide a patch?

> Kind regards,
> Oleksandr
>
> On Wednesday, June 13, 2012 3:02:46 PM UTC+2, Oleksandr Kazymyrov wrote:
> > Hi all,
> >
> > Continuing the

> > question<https://groups.google.com/forum/?fromgroups#!topic/sage-support
> > /cvtz4Zh-WYQ> ...

> >
> > Input data:
> > sage: K=GF(2^8,'a',modulus=ZZ['x']("x^8 + x^7 + x^6 + x^4 + x^3 + x^2 +
> > 1"))
> > sage: K.multiplicative_generator()
> > a^4 + a^3 + a
> > sage: P=PolynomialRing(K,'x')
> > sage: pol=P.random_element(5)
> > sage: pol
> > (a^7 + a^5 + a^3 + 1)*x^5 + (a^5 + a^4 + a^3 + a^2 + a + 1)*x^4 + (a^7 +
> > a^3 + a^2 + a)*x^3 + (a^5 + a^2)*x^2 + (a^6 + a^5 + a^4 + 1)*x + a^3
> >

> > 1. How to represent *pol *using multiplicative generator? The output must

> > be b^(i1)*x^5 + b^(i2)*x^4 + b^(i3)*x^3 + b^(i4)*x^2 + b^(i5)*x + a^3,
> > where b = K.multiplicative_generator(), i1-i5 logarithmic representation
> > of (a^7 + a^5 + a^3 + 1), (a^5 + a^4 + a^3 + a^2 + a + 1)...
> >
> > I have a correct function:
> > sage: b=K.multiplicative_generator()
> > sage: P(["({0})^{1}".format(b,i.log(b)) for i in pol.coeffs()]) == pol
> > True
> > sage: ["({0})^{1}".format(b,i.log(b)) for i in pol.coeffs()]
> > ['(a^4 + a^3 + a)^27', '(a^4 + a^3 + a)^234', '(a^4 + a^3 + a)^195',
> > '(a^4 + a^3 + a)^134', '(a^4 + a^3 + a)^79', '(a^4 + a^3 + a)^101']
> >
> > If I have one program then the above method suits me. But if two, i.e.
> > one program represents polynomial in the form b^(i1)*x^5 ... and returns
> > b and another program tries to restore it, then I worry about the phrase
> > The docs for multiplicative_generator() say: "return a generator of the
> > multiplicative group", then add "Warning: This generator might change
> > from one version of Sage to another."
> >

> > 2. So the question is how to uniquely reconstruct the original *pol*, if
> > I have *modulus*, *multiplicative generator *and* representation of pol
> > as *b^(i1)*x^5...?
> >
> > Regards,
> > Oleksandr

Cheers,
Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinr...@jabber.ccc.de