Generator of Finite Field

[Oleksandr Kazymyrov]

Hello all.

I have encountered the following problem In Sage 5.0:

sage: R.<x>=ZZ[] 

sage: k=GF(2^8,name='a',modulus=x^8+x^4+x^3+x+1)

sage: k(ZZ(3).digits(2))

a + 1

sage: k.gen()^ZZ(k(ZZ(3).digits(2)).log_repr())

a

sage:  k.gen()^ZZ(k(ZZ(3).digits(2)).log_repr()) == k(ZZ(3).digits(2))

False

sage: k("a+1")^ZZ(k(ZZ(3).digits(2)).log_repr()) == k(ZZ(3).digits(2))

True

It easy see that k.gen() or k.multiplicative_generator() is not a generator of the finite field:

sage: k.multiplicative_generator()

a^4 + a + 1

sage: k.gen()

a

sage: k.list()

[0, a + 1, a^2 + 1, a^3 + a^2 + a + 1, a^4 + 1, a^5 + a^4 + a + 1, a^6 + a^4 + a^2 + 1, ... ]

Generator is "a+1"!

How to get generator of Finite Field? It was fine in Sage 4.8.

Ubuntu 12.04

Linux hamsin 3.2.0-24-generic #37-Ubuntu SMP Wed Apr 25 08:43:52 UTC 2012 i686 i686 i386 GNU/Linux

Best regards,

Oleksandr

[Oleksandr Kazymyrov]

Hi again,

A try to use log function and got error:

sage: R.<x>=ZZ[]

sage: k.<a>=GF(2^8,modulus=x^8+x^4+x^3+x+1)

sage: b=k.random_element()                 

sage: b.log(a)                             

---------------------------------------------------------------------------

ValueError                                Traceback (most recent call last)

/home/hamsin/<ipython console> in <module>()

/home/hamsin/bin/sage/local/lib/python2.7/site-packages/sage/rings/finite_rings/element_givaro.so in sage.rings.finite_rings.element_givaro.FiniteField_givaroElement.log (sage/rings/finite_rings/element_givaro.cpp:11248)()

/home/hamsin/bin/sage/local/lib/python2.7/site-packages/sage/groups/generic.pyc in discrete_log(a, base, ord, bounds, operation, identity, inverse, op)

    814         return  CRT_list(l,[pi**ri for pi,ri in f])

    815     except ValueError:

--> 816         raise ValueError, "No discrete log of %s found to base %s"%(a,base)

    817 

    818 def discrete_log_generic(a, base, ord=None, bounds=None, operation='*', identity=None, inverse=None, op=None):

ValueError: No discrete log of a^7 + a^6 + a^5 + a^4 + a^2 + 1 found to base a

I also found some strangeness:

sage: m=[a^i for i in xrange(255)]

sage: m.append(0)

sage: len(set(m))

52

But last value must be 256, if a is a generator. So k.gens() returns wrong value.

P.S.

sage: version()

'Sage Version 5.0, Release Date: 2012-05-14'

[P Purkayastha]

I think what you are looking for is k.multiplicative_generator(). 

sage: c = k.multiplicative_generator()
sage: log(a, c)
20

[Martin Albrecht]

Hi,

it seems I was wrong about this yesterday (Olexandr and I discussed in person
yesterday):

sage: K.gen?

Return a generator of self. All elements x of self are expressed as
log_{self.gen()}(p) internally.

This generator might differ between different runs or different
architectures.

WARNING: The generator is not guaranteed to be a generator for
the multiplicative group. To obtain the latter, use
multiplicative_generator().

So, indeed, K.gen() may be != K.multiplicative_generator()


Olexandr, does your code work if you switch to multiplicative_generator() or
does that present problems for you?

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

[Alex Ghitza]

Hi,

On Mon, May 21, 2012 at 9:29 AM, Oleksandr Kazymyrov
<vrona.ak...@gmail.com> wrote:
> I have encountered the following problem In Sage 5.0:
> sage: R.<x>=ZZ[]
> sage: k=GF(2^8,name='a',modulus=x^8+x^4+x^3+x+1)
> sage: k(ZZ(3).digits(2))
> a + 1
> sage: k.gen()^ZZ(k(ZZ(3).digits(2)).log_repr())
> a
> sage:  k.gen()^ZZ(k(ZZ(3).digits(2)).log_repr()) == k(ZZ(3).digits(2))
> False
> sage: k("a+1")^ZZ(k(ZZ(3).digits(2)).log_repr()) == k(ZZ(3).digits(2))
> True
>
> It easy see that k.gen() or k.multiplicative_generator() is not a generator
> of the finite field:
> sage: k.multiplicative_generator()
> a^4 + a + 1

Why is it clear that a^4+a+1 is not a multiplicative generator? I think it is:

sage: k.<a> = GF(2^8, names='a', name='a', modulus=x^8+x^4+x^3+x+1)
sage: (a^4+a+1).multiplicative_order()
255

Indeed, so is a+1:
sage: (a+1).multiplicative_order()
255

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."


--
Best,
Alex

--
Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne
http://aghitza.org

[Oleksandr Kazymyrov]

I have used log_repr() and expect that it return y of equation x^y = z. I also believed  hat k.gen() return generator of the field.

Now I must use following construction for solving my problem

sage: R.<x>=ZZ[]
sage: k=GF(2^8,name='a',modulus=x^8+x^4+x^3+x+1)

sage: a = k.multiplicative_generator()
sage: a^ZZ(k(ZZ(3).digits(2)).log(a)) == k(ZZ(3).digits(2))

By the way, any of next functions don't return the value y of equation x^y=z

sage: b=K(ZZ(3).digits(2))
sage: b
a + 1
sage: b.log_repr()
'1'
sage: b.log_to_int()
3

I think that log_repr() should has the same logic as int_repr() or integer_representation(), i.e.

sage: a=K.multiplicative_generator()
sage: ZZ(K(ZZ(3).digits(2)).log(a))
164

What do you think?

Kind regards,

Oleksandr

[Martin Albrecht]

Hi,

K.gen() returns the thing we represent field elements in, but not necessarily
the field generator.


1) However, the documentation is wrong:

"""
Return a generator of self. All elements x of self are expressed as
log_{self.gen()}(p) internally
"""

This should be fixed and a reference to multiplicative_generator() added.

2) K.multiplicative_generator() currently returns a random generator, but for
the GivaroGFq implementation we should simply return the generator which has
internal representation '1', i.e., the guy we actually use to represent the
elements. Once this done log_repr() will also start to make sense again.

Olexandr, would those fixes solves your confusion/problem?

[Oleksandr Kazymyrov]

Hi,

Yes, I hope that 2) will fix it.

Cheers.

Oleksandr

[Jeroen Demeyer]

On 2012-06-03 12:14, Martin Albrecht wrote:
> 2) K.multiplicative_generator() currently returns a random generator, but for
> the GivaroGFq implementation we should simply return the generator which has
> internal representation '1', i.e., the guy we actually use to represent the
> elements. Once this done log_repr() will also start to make sense again.

On the other hand, doing this for the Givaro interface but not for the
PARI interface (where logs are never used) is also confusing. I would
say: leave things as they are. Note that the generator is not "random",
it is deterministic.

[Martin Albrecht]

PARI doesn't have a log_repr() to begin with, so I don't see how that's
relevant.

[Jeroen Demeyer]

On 2012-06-03 22:37, Martin Albrecht wrote:
> PARI doesn't have a log_repr() to begin with, so I don't see how that's
> relevant.

Yes, never mind my comment.