Re: method int_repr only works for small finite fields

[Alec Mihailovs]

On Mar 20, 10:11 pm, Minh Nguyen <nguyenmi...@gmail.com> wrote:
> On Sun, Mar 21, 2010 at 10:19 AM, Alasdair McAndrew <amc...@gmail.com> wrote:

> > def intr(z):
> >     C=z.polynomial().coeffs()
> >     fc=parent(z).characteristic()
> >     tmp=0
> >     for i in range(len(C),0,-1):
> >         tmp=fc*tmp+int(C[i-1])
> >     return tmp

That can be also written short, but working slightly slower as

sage: def intr1(z):
....: return
ZZ(z.polynomial().coeffs(),parent(z).characteristic())

And using functional programming, which works slightly faster than
intr, as

sage: def int4(z):
....: C=reversed(map(int,z.polynomial().coeffs()))
....: fc=parent(z).characteristic()
....: return reduce(lambda x,y:fc*x+y,C)

Alec Mihailovs

[Martin Albrecht]

I wrote the small finite field class and added the int_repr() and forgot to
add something equivalent for bigger fields. I would suggest to add a new
function to both called integer_representation() (or so) and deprecate the
shorthand int_repr(). In all cases it should return a Sage Integer not a
Python int.

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://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de

[Alec Mihailovs]

On Mar 21, 10:03 am, Martin Albrecht <m...@informatik.uni-bremen.de>
wrote:

> In all cases it should return a Sage Integer not a
> Python int.

All of the functions intr, intr1, and int4 return a Sage integer, not
a Python int.

Also, for small fields, log_to_int operates the same way,

sage: F.<X>=GF(2^6)
sage: r=F.random_element(); r

X^5 + X^2 + X + 1

sage: int4(r)

39

sage: r.log_to_int()

39

However, for large fields, say GF(7^100), log_to_int is not
implemented. Perhaps, either that name can be used instead of
integer_representation, or something similar, say poly_to_int.

Also, if there is a conversion from polynomials to integers, it would
have sense to have a backward conversion from integers to polynomials.
It can be done similarly as

def poly_repr(n,f):
C=reversed(n.digits(f.characteristic()))
return reduce(lambda x,y:f.gen()*x+y,C)

For example,

sage: poly_repr(int4(r),F)

X^5 + X^2 + X + 1

sage: _==r

True

The name for it can be chosen correspondingly to the name of the first
conversion, say int_to_poly.

The corresponding functions in the Maple's implementation of GF are
called input and output. They work in Maple as

F:=GF(7,100):
F:-input(101);
2
3 + 2 T

F:-output(%);

101

Alec Mihailovs

[Martin Albrecht]

> However, for large fields, say GF(7^100), log_to_int is not
> implemented. Perhaps, either that name can be used instead of
> integer_representation, or something similar, say poly_to_int.

log_to_int is only available for Givaro fields because it represents finite
field elements as their logarithms internally, e.g. a^10 is stored as 10
internally.

> Also, if there is a conversion from polynomials to integers, it would
> have sense to have a backward conversion from integers to polynomials.
> It can be done similarly as

sage: K.<a> = GF(3^10)
sage: K.fetch_int(10)
a^2 + 1

I don't claim the name is fitting or anything :)

[Alec Mihailovs]

On Mar 21, 5:01 pm, Martin Albrecht <m...@informatik.uni-bremen.de>
wrote:

> sage: K.fetch_int(10)
> a^2 + 1

It's also working only for small fields.

Meanwhile, I found out that int4 returns python int in some cases. In
particular,

sage: type(int4(F.one()))

<type 'int'>

Also, neither int4, nor poly_repr work with 0,

sage: int4(F.zero())

TypeError: reduce() of empty sequence with no initial value

sage: poly_repr(0,F)

TypeError: reduce() of empty sequence with no initial value

So both of them should be corrected by dealing with 0 separately and
converting python int to Sage integers in int4.

Alec Mihailovs

[Alec Mihailovs]

On Mar 21, 5:34 pm, Alec Mihailovs <alec.mihail...@gmail.com> wrote:
> So both of them should be corrected by dealing with 0 separately and
> converting python int to Sage integers in int4.

Here are the corrected versions of int4 and poly_repr,

sage: def int4(z):
....: C=reversed(map(int,z.polynomial().coeffs()))
....: fc=parent(z).characteristic()

....: return reduce(lambda x,y:fc*x+y,C,0)

def poly_repr(n,f):
C=reversed(n.digits(f.characteristic()))
return reduce(lambda x,y:f.gen()*x+y,C,f.zero())

sage: type(int4(F.one()))

<type 'sage.rings.integer.Integer'>

sage: poly_repr(0,F)

0

sage: type(_)

<class
'sage.rings.finite_field_element.FiniteField_ext_pariElement'>

sage: int4(F.zero())

0

sage: type(_)

<type 'sage.rings.integer.Integer'>

Alec Mihailovs

[Alec Mihailovs]

By the way, I looked at the help page for digits,

sage: base=7
sage: x=12345654321234565432123456543212345654321234565432123456
sage: x.digits?

and it is said there (at the end) that

" Using ``sum()`` and ``enumerate()`` to do the same thing is
slightly faster in many cases (and ``balanced_sum()`` may be
faster
yet). Of course it gives the same result:

sage: base = 4
sage: sum(digit * base^i for i, digit in
enumerate(x.digits(base))) == ZZ(x.digits(base), base)
True
"

However, timing shows that ZZ is faster than sum with enumerate, and
reduce is faster than both of them,

sage: L=x.digits(base)
sage: timeit('sum(digit * base^i for i, digit in enumerate(L))')
625 loops, best of 3: 59.2 ��s per loop
sage: timeit('ZZ(L,base)')
625 loops, best of 3: 57.3 ��s per loop
sage: timeit('reduce(lambda x,y:base*x+y,reversed(L),0)')
625 loops, best of 3: 29.2 ��s per loop

Alec Mihailovs