[sage-devel] Re: generator inconsistencies in finite fields
On Jan 23, 2008 4:08 PM, Jonathan Bober <[EMAIL PROTECTED]> wrote:
>
> I just realized a source of my confusion. The docstring that I quoted
> was not actually wrong in the way that I thought is was, but was
> apparently deceptive (to me). Perhaps some people are already aware of
> this, but GF(5), GF(25), and GF(5^100) are all different types, and so
> have different docstrings, some of which have errors.
>
> sage: F = GF(5)
> sage: K = GF(5^2,'x')
> sage: L = GF(5^100,'x')
>
> sage: type(F)
>
> sage: type(K)
>
> sage: type(L)
>
>
> I earlier quoted the docstring for
> sage.rings.finite_field_givaro.FiniteField_givaro. Assuming that 'small'
> means 'implemented using givaro', I guess (from Martin's email) that for
> fields F implemented using givaro F.gen() is always a multiplicative
> generator. But for prime fields constructed with GF(), F.gen() is always
> 1, and for large fields, F.gen() is 'just' a root of the defining
> polynomial, whatever that happens to be.
>
> In fact, if I force the construction of a givaro-implemented prime
> field, then the generator is not 1.
>
> sage: H = sage.rings.finite_field_givaro.FiniteField_givaro(5)
> sage: H.gen()
> 2
>
> So the state of the docstrings is
>
> sage: sage.rings.finite_field.FiniteField_prime_modn.gen?
> [...]
> Docstring:
>
> Return generator of this finite field.
> (Nothing wrong here I suppose, but I think that it is always going to
> return 1.)
>
>
> sage: sage.rings.finite_field_givaro.FiniteField_givaro.gen?
> [...]
> Docstring:
>
> Return a generator of self. All elements x of self are
> expressed as log_{self.gen()}(p) internally. If self is
> a prime field this method returns 1.
>
> (The sentence "If self is a prime field..." is wrong, but the first
> sentence is correct.)
This is now trac #1902:
http://trac.sagemath.org/sage_trac/ticket/1902
>
> sage: sage.rings.finite_field_ext_pari.FiniteField_ext_pari.gen?
> [...]
> Docstring:
>
> Return chosen generator of the finite field. This generator
> is a root of the defining polynomial of the finite field, and
> is guaranteed to be a generator for the multiplicative group.
>
> (This is wrong because in this case the generator is not guaranteed to
> be a generator for the multiplicative group.)
I've made this trac #1901:
http://trac.sagemath.org/sage_trac/ticket/1901
>
> I think that the ultimate source of my confusion is that GF is not a
> class, but is actually a function that returns a instance of any one of
> at least 3 different classes. I feel that if it's somehow possible I
> would much prefer if FiniteField was a type all its own, and if all
> finite fields were of type FiniteField, and the difference in
> implementations was completely invisible. (I'm pretty sure that there
> are other instances of this type of thing in sage.)
>
That's not going to happen. It used to be the case that there was
only 1 finite field class, but it was very slow. Now there are
three -- written by three different people (at least) -- but (some of them at
least) are vastly faster. The solution in this case should to clean up
and unify the documentation and the actual definitions of the functions
so they are consistent. This just takes actual thought and work.
> At the very least, there should probably be some sort of uniformity in
> the docstrings, but I'm not sure exactly how this should work.
>
> (Additionally, I was just thinking that it might be nice to have a
> standard "SEE ALSO:" section in the documentation. For example
>
> SEE ALSO: multiplicative_generator()
>
> The online documentation could even automatically generate links for
> this.)
>
> Anyway, that was quite a long email. Congratulations and apologies if
> you read it all.
>
> -bober
>
>
> On Tue, 2008-01-22 at 00:16 +, Martin Albrecht wrote:
> > > In this case, the docstring needs to be corrected, because the statement
> > > that "All elements x of self are expressed as log_{self.gen()}(p)
> > > internally" is not true, right? (Extrapolating from this sentence and my
> > > two examples led me to make my previous statements.) Probably it is true
> > > that all elements are expressible as polynomials in x, and perhaps this
> > > is also the internal representation.
> >
> > Hi,
> >
> > It is not. For small extension fields of order < 2^16 the elements are
> > represented using Zech logs internally, so for these finite fields the
> > docstring "all elements x of self are expressed as log_{self.gen()}(p)
> > internally" is true.
> >
> > Martin
> >
> >
>
>
>
> >
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemat
[sage-devel] Re: generator inconsistencies in finite fields
I just realized a source of my confusion. The docstring that I quoted
was not actually wrong in the way that I thought is was, but was
apparently deceptive (to me). Perhaps some people are already aware of
this, but GF(5), GF(25), and GF(5^100) are all different types, and so
have different docstrings, some of which have errors.
sage: F = GF(5)
sage: K = GF(5^2,'x')
sage: L = GF(5^100,'x')
sage: type(F)
sage: type(K)
sage: type(L)
I earlier quoted the docstring for
sage.rings.finite_field_givaro.FiniteField_givaro. Assuming that 'small'
means 'implemented using givaro', I guess (from Martin's email) that for
fields F implemented using givaro F.gen() is always a multiplicative
generator. But for prime fields constructed with GF(), F.gen() is always
1, and for large fields, F.gen() is 'just' a root of the defining
polynomial, whatever that happens to be.
In fact, if I force the construction of a givaro-implemented prime
field, then the generator is not 1.
sage: H = sage.rings.finite_field_givaro.FiniteField_givaro(5)
sage: H.gen()
2
So the state of the docstrings is
sage: sage.rings.finite_field.FiniteField_prime_modn.gen?
[...]
Docstring:
Return generator of this finite field.
(Nothing wrong here I suppose, but I think that it is always going to
return 1.)
sage: sage.rings.finite_field_givaro.FiniteField_givaro.gen?
[...]
Docstring:
Return a generator of self. All elements x of self are
expressed as log_{self.gen()}(p) internally. If self is
a prime field this method returns 1.
(The sentence "If self is a prime field..." is wrong, but the first
sentence is correct.)
sage: sage.rings.finite_field_ext_pari.FiniteField_ext_pari.gen?
[...]
Docstring:
Return chosen generator of the finite field. This generator
is a root of the defining polynomial of the finite field, and
is guaranteed to be a generator for the multiplicative group.
(This is wrong because in this case the generator is not guaranteed to
be a generator for the multiplicative group.)
I think that the ultimate source of my confusion is that GF is not a
class, but is actually a function that returns a instance of any one of
at least 3 different classes. I feel that if it's somehow possible I
would much prefer if FiniteField was a type all its own, and if all
finite fields were of type FiniteField, and the difference in
implementations was completely invisible. (I'm pretty sure that there
are other instances of this type of thing in sage.)
At the very least, there should probably be some sort of uniformity in
the docstrings, but I'm not sure exactly how this should work.
(Additionally, I was just thinking that it might be nice to have a
standard "SEE ALSO:" section in the documentation. For example
SEE ALSO: multiplicative_generator()
The online documentation could even automatically generate links for
this.)
Anyway, that was quite a long email. Congratulations and apologies if
you read it all.
-bober
On Tue, 2008-01-22 at 00:16 +, Martin Albrecht wrote:
> > In this case, the docstring needs to be corrected, because the statement
> > that "All elements x of self are expressed as log_{self.gen()}(p)
> > internally" is not true, right? (Extrapolating from this sentence and my
> > two examples led me to make my previous statements.) Probably it is true
> > that all elements are expressible as polynomials in x, and perhaps this
> > is also the internal representation.
>
> Hi,
>
> It is not. For small extension fields of order < 2^16 the elements are
> represented using Zech logs internally, so for these finite fields the
> docstring "all elements x of self are expressed as log_{self.gen()}(p)
> internally" is true.
>
> Martin
>
>
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-devel] Re: generator inconsistencies in finite fields
Hi All, Just a few comments: there are three possible concepts for generator[s]: 1) As a field over its prime field or base field (function gen(), category Field or Algebra); 2) As a vector space over its base field (function additive_generators(), category Module) 3) As a group, restricted to the set of nonzero elements, which is the original source of confusion (function primitive_element() or group_generator(), category Group). It has been noted that 3) can be difficult to compute for large fields. Finite fields should be first and foremorst Fields, hence gen() should remain as it is, and functions like additive_generators() and primitive_element() or group_generator() could be added. The term primitive_element() is very standard terminology for a group_element() when talking specifically of finite fields, but unfortunately this can be confusing with a primitive element of an arbitrary finite algebraic extension field, where it is defined to be a generator of the field extension. --David --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: generator inconsistencies in finite fields
Sorry, I was confused. You and William are right. Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _www: http://www.informatik.uni-bremen.de/~malb _jab: [EMAIL PROTECTED] --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: generator inconsistencies in finite fields
On Jan 23, 2008 4:06 AM, Martin Albrecht <[EMAIL PROTECTED]> wrote: > > > > By contrast F.multiplicative_gen() does make sense for all finite > > > fields so should be provided, though not necessarily computed until > > > requested for the reasons given by Martin. (It seems that with the > > > current implementation of non-prime fiinite fields this comes for > > > free, but that might change.) > > > > Only for the Givaro ones, i.e., up to 2^16. For general fields it is not > > for free, unfortunately (I think). > > I think it is 'free' for all extension fields because we either represent the > field elements as powers of the generators or as polynomials in the > generator. In the latter case, i.e., "as polynomials in the generator", there is no guarantee that the generator is a generator for the multiplicative group in general. Here is an example that might clarify things, in case I'm misunderstanding: sage: k. = GF(3)[] sage: F. = GF(9, modulus = x^2 + 1) sage: a.multiplicative_order() 4 William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: generator inconsistencies in finite fields
On 23/01/2008, Martin Albrecht <[EMAIL PROTECTED]> wrote: > > > > By contrast F.multiplicative_gen() does make sense for all finite > > > fields so should be provided, though not necessarily computed until > > > requested for the reasons given by Martin. (It seems that with the > > > current implementation of non-prime fiinite fields this comes for > > > free, but that might change.) > > > > Only for the Givaro ones, i.e., up to 2^16. For general fields it is not > > for free, unfortunately (I think). > > I think it is 'free' for all extension fields because we either represent the > field elements as powers of the generators or as polynomials in the > generator. I don't see this. If GF(p^n) is represented as GF(p)[X]/(f(X)) where f(X) is an arbitrary degree n irreducible in GF(p)[X], then finding the multiplicative generator will take some work even though that generator will, of course, be represented as a polynomial in the generator a (= root of f). I am not familiar with the best algorithms for finding the (multiplicative) generator for large fields, but I'm sure they are well documented. Of course a standard baby-step-giant-step would work if p^n-1 was small enough (to be factored, for a start). John > > Martin > > > -- > name: Martin Albrecht > _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 > _www: http://www.informatik.uni-bremen.de/~malb > _jab: [EMAIL PROTECTED] > > > > > -- John Cremona --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: generator inconsistencies in finite fields
> > By contrast F.multiplicative_gen() does make sense for all finite > > fields so should be provided, though not necessarily computed until > > requested for the reasons given by Martin. (It seems that with the > > current implementation of non-prime fiinite fields this comes for > > free, but that might change.) > > Only for the Givaro ones, i.e., up to 2^16. For general fields it is not > for free, unfortunately (I think). I think it is 'free' for all extension fields because we either represent the field elements as powers of the generators or as polynomials in the generator. Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _www: http://www.informatik.uni-bremen.de/~malb _jab: [EMAIL PROTECTED] --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: generator inconsistencies in finite fields
Thanks for taking the time to read and respond to my lengthy
contribution. I agree with everything you say!
Sorry to those who don't like the more mathematical discussions on
sage-devel -- personally I find them more interesting than the
notebook interface! but one of Sage's strengths is surely that
between us we cover lots of different areas of interest, all of which
are important.
John
On 23/01/2008, William Stein <[EMAIL PROTECTED]> wrote:
>
> On Jan 22, 2008 3:46 AM, John Cremona <[EMAIL PROTECTED]> wrote:
> >
> > Thoughts on this thread:
> >
> > For finite fields (or any other fields) the concept of additive
> > generator makes no sense -- only finite prime fields have one and it
> > is hardly a useful concept then since every nonzero element is one.
> > It's different if talking about generators (plural!) which I think is
> > what David Kohel meant, but here we are talking about what F.gen()
> > should be.
>
> Agreed. Also, I agree with David that additive_generators() (plural)
> could be useful.
> Though much more useful is an explicit isomorphism with a vector
> space (which we have already).
>
> > By contrast F.multiplicative_gen() does make sense for all finite
> > fields so should be provided, though not necessarily computed until
> > requested for the reasons given by Martin. (It seems that with the
> > current implementation of non-prime fiinite fields this comes for
> > free, but that might change.)
>
> Only for the Givaro ones, i.e., up to 2^16. For general fields it is not
> for free, unfortunately (I think).
>
> > As for F.gen() it might be worth thinking more generally about what
> > one means by "*the* generator" of a field.
>
> It's a *choice* of generator which is part of the
> structure of the object. In Sage -- like in Magma -- pretty much
> every structure is generated by some explicit list of objects (possibly
> modulo relations) over some canonical base, and that list of objects
> is part of the definition of the structure -- e.g., there are vector spaces
> with basis, not abstract vector spaces. That's the key idea
> in the design of Magma, and Sage really benefits from taking the
> same approach.
>
> > Again the concept only
> > makes sense for some fields: those which are generated by a single
> > element over their prime field (so: any number field, any finite
> > field, or the function fields in one variable over QQ or GF(p)); or,
> > more generally for fields constructed as relative extensions of other
> > fields, we could include finite (algebraic) extensions of any field at
> > all, and function fields in one variable over any field.
>
> Actually multiple generators make sense. That's why there
> is a gens() method on objects. Vector spaces, e.g., have multiple
> generators.
>
> >
> > Arguably, neither QQ nor GF(p) require any generators at all, but for
> > consistency with general number fields and finite fields it would be
> > reasonbly to have F.gen() return any nonzero element, and why not fix
> > it as F(1).
>
> It is incredibly useful if (1) things are consistent, so one can write
> generic code, and (2) if it is easy to remember what the choices
> are, which is possibly an argument for F(1) being the generator
> for GF(p). In fact, I chose 1 as the generator for GF(p), for
> consistency with other prime fields and the integers, which I
> also had no choice but to choose 1. I also chose 1 since
> it's what Magma does:
>
> sage: magma.eval('GF(19).1')
> '1'
>
> In general, when implementing objects that are very similar
> to things in Magma, I see no reason to radically
> change the design of Sage from the
> design of Magma, unless there is a compelling reason to do so.
> Frankly, there is a lot I really like about the design
> of Magma.
>
> > There should certainly be no expectation that F.gen() be a
> > multiplicative generator, even if it often is -- so perhaps a warning
> > in the documentation should tell users to use F.multiplicative_gen()
> > if that's what they really need.
>
> +1
>
> Warnings in the documentation with examples are a good idea
> in this case.
>
> > As for order(), I would be happy for it not to be implemented at all
> > for elements of a field! For additive order it is completely
> > redundant since all nonzero elements have the same order depending
> > only on the characteristic.
>
> I'm not sure that it is all bad that it is redundant. At least right now
> I can write generic code that I might not be able to write were that
> method removed. Say I write a function that does "blah blah" in an
> additive group.
> I can just toss it field elements and it will work. If I ban the
> additive_order()
> command then it breaks for no good reason.
>
> Also the order and additive_order commands are automatically there because
> there is a class hierarchy and they are defined in class higher up the
> hierarchy.
>
> > For multiplicative order it is useful
> > (for nonzero elements of course), but would it not be better, if you
>
[sage-devel] Re: generator inconsistencies in finite fields
On Jan 22, 2008 3:46 AM, John Cremona <[EMAIL PROTECTED]> wrote:
>
> Thoughts on this thread:
>
> For finite fields (or any other fields) the concept of additive
> generator makes no sense -- only finite prime fields have one and it
> is hardly a useful concept then since every nonzero element is one.
> It's different if talking about generators (plural!) which I think is
> what David Kohel meant, but here we are talking about what F.gen()
> should be.
Agreed. Also, I agree with David that additive_generators() (plural)
could be useful.
Though much more useful is an explicit isomorphism with a vector
space (which we have already).
> By contrast F.multiplicative_gen() does make sense for all finite
> fields so should be provided, though not necessarily computed until
> requested for the reasons given by Martin. (It seems that with the
> current implementation of non-prime fiinite fields this comes for
> free, but that might change.)
Only for the Givaro ones, i.e., up to 2^16. For general fields it is not
for free, unfortunately (I think).
> As for F.gen() it might be worth thinking more generally about what
> one means by "*the* generator" of a field.
It's a *choice* of generator which is part of the
structure of the object. In Sage -- like in Magma -- pretty much
every structure is generated by some explicit list of objects (possibly
modulo relations) over some canonical base, and that list of objects
is part of the definition of the structure -- e.g., there are vector spaces
with basis, not abstract vector spaces. That's the key idea
in the design of Magma, and Sage really benefits from taking the
same approach.
> Again the concept only
> makes sense for some fields: those which are generated by a single
> element over their prime field (so: any number field, any finite
> field, or the function fields in one variable over QQ or GF(p)); or,
> more generally for fields constructed as relative extensions of other
> fields, we could include finite (algebraic) extensions of any field at
> all, and function fields in one variable over any field.
Actually multiple generators make sense. That's why there
is a gens() method on objects. Vector spaces, e.g., have multiple
generators.
>
> Arguably, neither QQ nor GF(p) require any generators at all, but for
> consistency with general number fields and finite fields it would be
> reasonbly to have F.gen() return any nonzero element, and why not fix
> it as F(1).
It is incredibly useful if (1) things are consistent, so one can write
generic code, and (2) if it is easy to remember what the choices
are, which is possibly an argument for F(1) being the generator
for GF(p). In fact, I chose 1 as the generator for GF(p), for
consistency with other prime fields and the integers, which I
also had no choice but to choose 1. I also chose 1 since
it's what Magma does:
sage: magma.eval('GF(19).1')
'1'
In general, when implementing objects that are very similar
to things in Magma, I see no reason to radically
change the design of Sage from the
design of Magma, unless there is a compelling reason to do so.
Frankly, there is a lot I really like about the design
of Magma.
> There should certainly be no expectation that F.gen() be a
> multiplicative generator, even if it often is -- so perhaps a warning
> in the documentation should tell users to use F.multiplicative_gen()
> if that's what they really need.
+1
Warnings in the documentation with examples are a good idea
in this case.
> As for order(), I would be happy for it not to be implemented at all
> for elements of a field! For additive order it is completely
> redundant since all nonzero elements have the same order depending
> only on the characteristic.
I'm not sure that it is all bad that it is redundant. At least right now
I can write generic code that I might not be able to write were that
method removed. Say I write a function that does "blah blah" in an
additive group.
I can just toss it field elements and it will work. If I ban the
additive_order()
command then it breaks for no good reason.
Also the order and additive_order commands are automatically there because
there is a class hierarchy and they are defined in class higher up the
hierarchy.
> For multiplicative order it is useful
> (for nonzero elements of course), but would it not be better, if you
> needed mutiplicative orders, to create the multiplicative group of the
> field as an abelian group and ask for the order of an element in that
> context?
That's what you do in Magma right? And it's your only option, right?
I definitely think that functionality should be supported in Sage. But
I can't at all understand why that should be the only option.
On the other hand, maybe I'm wrong. Here is a cautionary tail that
is perhaps pointless, but I'll tell it.
I remember once thinking that was the natural way to do things in Magma.
So I wanted to demo discrete logs in finite fields for my students in
class once (in 2002), and did
[sage-devel] Re: generator inconsistencies in finite fields
Thoughts on this thread:
For finite fields (or any other fields) the concept of additive
generator makes no sense -- only finite prime fields have one and it
is hardly a useful concept then since every nonzero element is one.
It's different if talking about generators (plural!) which I think is
what David Kohel meant, but here we are talking about what F.gen()
should be.
By contrast F.multiplicative_gen() does make sense for all finite
fields so should be provided, though not necessarily computed until
requested for the reasons given by Martin. (It seems that with the
current implementation of non-prime fiinite fields this comes for
free, but that might change.)
As for F.gen() it might be worth thinking more generally about what
one means by "*the* generator" of a field. Again the concept only
makes sense for some fields: those which are generated by a single
element over their prime field (so: any number field, any finite
field, or the function fields in one variable over QQ or GF(p)); or,
more generally for fields constructed as relative extensions of other
fields, we could include finite (algebraic) extensions of any field at
all, and function fields in one variable over any field.
Arguably, neither QQ nor GF(p) require any generators at all, but for
consistency with general number fields and finite fields it would be
reasonbly to have F.gen() return any nonzero element, and why not fix
it as F(1).
There should certainly be no expectation that F.gen() be a
multiplicative generator, even if it often is -- so perhaps a warning
in the documentation should tell users to use F.multiplicative_gen()
if that's what they really need.
As for order(), I would be happy for it not to be implemented at all
for elements of a field! For additive order it is completely
redundant since all nonzero elements have the same order depending
only on the characteristic. For multiplicative order it is useful
(for nonzero elements of course), but would it not be better, if you
needed mutiplicative orders, to create the multiplicative group of the
field as an abelian group and ask for the order of an element in that
context?
This links in with something I needed to be able to do: given an
element a of GF(q) qith q a non-prime prime power, to return the
degree of a, meaning the smallest n such that a is in GF(p^n). One
could work this out from the (mutiplicative) order of a, which might
be efficient if GF(q)'s multiplicative generator was already known
together with the factorization of q-1. Or it's the degree of the
minimal polynomial of a over GF(p).
More generally, given a field F which is an extension of some base
field k and an element a of F it would be nice to be able to construct
the subfield k(a) of F together with a suitable embedding into F and
an element in it which maps to a. But this is getting too far afield
;), so I'll shut up.
John
On 22/01/2008, Martin Albrecht <[EMAIL PROTECTED]> wrote:
>
> > In this case, the docstring needs to be corrected, because the statement
> > that "All elements x of self are expressed as log_{self.gen()}(p)
> > internally" is not true, right? (Extrapolating from this sentence and my
> > two examples led me to make my previous statements.) Probably it is true
> > that all elements are expressible as polynomials in x, and perhaps this
> > is also the internal representation.
>
> Hi,
>
> It is not. For small extension fields of order < 2^16 the elements are
> represented using Zech logs internally, so for these finite fields the
> docstring "all elements x of self are expressed as log_{self.gen()}(p)
> internally" is true.
>
> Martin
>
>
> --
> name: Martin Albrecht
> _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
> _www: http://www.informatik.uni-bremen.de/~malb
> _jab: [EMAIL PROTECTED]
>
>
> >
>
--
John Cremona
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-devel] Re: generator inconsistencies in finite fields
> In this case, the docstring needs to be corrected, because the statement
> that "All elements x of self are expressed as log_{self.gen()}(p)
> internally" is not true, right? (Extrapolating from this sentence and my
> two examples led me to make my previous statements.) Probably it is true
> that all elements are expressible as polynomials in x, and perhaps this
> is also the internal representation.
Hi,
It is not. For small extension fields of order < 2^16 the elements are
represented using Zech logs internally, so for these finite fields the
docstring "all elements x of self are expressed as log_{self.gen()}(p)
internally" is true.
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_jab: [EMAIL PROTECTED]
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-devel] Re: generator inconsistencies in finite fields
Ok, I was wrong. I'm convinced that sage has the correct behavior, which
I think is:
GF(q).gen() returns an element x of GF(q) such that the smallest
subfield of GF(q) containing x is GF(q).
In this case, the docstring needs to be corrected, because the statement
that "All elements x of self are expressed as log_{self.gen()}(p)
internally" is not true, right? (Extrapolating from this sentence and my
two examples led me to make my previous statements.) Probably it is true
that all elements are expressible as polynomials in x, and perhaps this
is also the internal representation.
On Mon, 2008-01-21 at 00:32 -0800, David Kohel wrote:
> Hi,
>
> It is probably a bias of the choice of (additive) generators for
> finite field
> extensions which results in the primitive field element also being a
> generator for the multiplicative group (confusingly called a
> "primitive
> element of the finite field").
>
> It is not possible to set GF(q).gen() to always be a generator for
> the
> multiplicative group, since it is not always computationally feasible
> to
> determine it. In particular requires a factorization of q-1. The
> finite
> field constructor for non-prime fields would then also have to be
> changed to ONLY use primitive elements (since GF(q).gen() must
> certainly return the generator with respect the the defining
> polynomial).
> This would conflict with the desire to allow user-chosen polynomials
> or polynomials of SAGE's choice which are selected for sparseness
> (hence speed) rather than as generator of the multiplicative group.
> Moreover, any such definition for convenience of the user would
> have to be turned off for q > [some arbitrary bound] and could not
> be reliable. Thus I don't see how it would be possible to make the
> definition that GF(q).gen() is a generator for the multiplicative
> group.
>
> For small finite fields, one could set GF(q).gen() to be such a
> generator. This could either be convenient, or confuse users into
> thinking that this is more generally True.
>
> --David
>
> P.S. On the other hand, I find (additive) order confusing and there
> should
> be some checking of the index for FF.i below (i.e. give an error if i !
> = 0).
>
> sage: FF. = GF(7^100);
> sage: x.order()
> 7
> sage: x
> x
> sage: x.multiplicative_order()
> 323447650962475799134464776910021681085720319890462540093389533139169145963692806000
> sage: FF.0
> x
> sage: FF.1
> x
> sage: FF.2
> x
> sage: FF.100
> x
> sage: FF.101
> x
> >
>
>
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
[sage-devel] Re: generator inconsistencies in finite fields
Hi, It is probably a bias of the choice of (additive) generators for finite field extensions which results in the primitive field element also being a generator for the multiplicative group (confusingly called a "primitive element of the finite field"). It is not possible to set GF(q).gen() to always be a generator for the multiplicative group, since it is not always computationally feasible to determine it. In particular requires a factorization of q-1. The finite field constructor for non-prime fields would then also have to be changed to ONLY use primitive elements (since GF(q).gen() must certainly return the generator with respect the the defining polynomial). This would conflict with the desire to allow user-chosen polynomials or polynomials of SAGE's choice which are selected for sparseness (hence speed) rather than as generator of the multiplicative group. Moreover, any such definition for convenience of the user would have to be turned off for q > [some arbitrary bound] and could not be reliable. Thus I don't see how it would be possible to make the definition that GF(q).gen() is a generator for the multiplicative group. For small finite fields, one could set GF(q).gen() to be such a generator. This could either be convenient, or confuse users into thinking that this is more generally True. --David P.S. On the other hand, I find (additive) order confusing and there should be some checking of the index for FF.i below (i.e. give an error if i ! = 0). sage: FF. = GF(7^100); sage: x.order() 7 sage: x x sage: x.multiplicative_order() 323447650962475799134464776910021681085720319890462540093389533139169145963692806000 sage: FF.0 x sage: FF.1 x sage: FF.2 x sage: FF.100 x sage: FF.101 x --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: generator inconsistencies in finite fields
On Jan 20, 2008 10:54 PM, Jonathan Bober <[EMAIL PROTECTED]> wrote:
>
> I don't like the behavior illustrated below. Briefly, my problem is that
> GF(p).gen() gives a generator for the additive group of GF(5), while
> GF(p^n).gen() gives a generator for for multiplicative group of GF(p^n)
> (n > 1).
>
> I would file this 'complaint' directly as a trac bug report, but the
> documentation is somewhat clear that this is what is _supposed_ to
> happen - i.e., it says
>
> sage: F.gen?
> Type: builtin_function_or_method
> Base Class:
> String Form: sage.rings.finite_field_givaro.FiniteField_givaro object at 0x9c22324>
> Namespace: Interactive
> Docstring:
>
> Return a generator of self. All elements x of self are
> expressed as log_{self.gen()}(p) internally. If self is
> a prime field this method returns 1.
>
> [...]
>
> I also know that there is multiplicative_generator() method which always
> does the right thing, but I still don't like this inconsistency.
>
> Anyway, perhaps I'll turn my 'complaint' into a trac ticket, but I won't
> bother if others don't consider this to be a bug.
I'm not opposed to changing GF(p).gen() to return a multiplicative
generator.Martin Albrecht, what do you think?
-- William
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~--~~~~--~~--~--~---
