[fricas-devel] Bug in finite field generator() function?

[Paul Onions]

Hi All,

It seems that calling generator() on a field created with
FiniteFieldExtensionByPolynomial may not return a primitive element of
the field. Specifically, when the field is created using an
irreducible (but not primitive) polynomial.

Example:-

(1) -> p : UP(x,PrimeField(2)) := x^4 + x^3 + x^2 + x + 1

4 3 2
(1) x + x + x + x + 1
Type: UnivariatePolynomial(x,PrimeField(2))
(2) -> F16 := FiniteFieldExtensionByPolynomial(PrimeField(2), p)

(2) FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?^3+?^2+?+1)
Type: Type
(3) -> g := generator()$F16

(3) %A
Type: FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?^3+?^2+?+1)
(4) -> g^5

(4) 1
Type: FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?^3+?^2+?+1)

Looking at the source (ffp.spad) it looks like the implementation of
generator() assumes that the defining polynomial is primitive, but the
comments at the head of the file clearly state that the only
requirement on the defining polynomial is that it be irreducible.

Am I misunderstanding something here?
Paul

[Prof. Dr. Johannes Grabmeier privat]

no bug!

generator() does not necessarily return a primitive element, which
generates the cyclic group (F-{0},*)! It returns an element which generates
the algebra, so the result is correct.

See comment:

generator : () -> %
++ generator() returns a root of the defining polynomial.
++ This element generates the field as an algebra over the ground field.

Perhaps you want to use

primitiveElement()$F16

(84) -> w := primitiveElement()$FFP(PF 2, p)

   (84)  %E + 1
                               Type:
FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?^3+?^2+?+1)
(85) -> order w

   (85)  15
                                                                              
Type: PositiveInteger

Post by Paul Onions
Hi All,
It seems that calling generator() on a field created with
FiniteFieldExtensionByPolynomial may not return a primitive element of
the field. Specifically, when the field is created using an
irreducible (but not primitive) polynomial.
Example:-
(1) -> p : UP(x,PrimeField(2)) := x^4 + x^3 + x^2 + x + 1
4 3 2
(1) x + x + x + x + 1
Type: UnivariatePolynomial(x,PrimeField(2))
(2) -> F16 := FiniteFieldExtensionByPolynomial(PrimeField(2), p)
(2) FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?^3+?^2+?+1)
Type: Type
(3) -> g := generator()$F16
(3) %A
Type: FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?^3+?^2+?+1)
(4) -> g^5
(4) 1
Type: FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?^3+?^2+?+1)
Looking at the source (ffp.spad) it looks like the implementation of
generator() assumes that the defining polynomial is primitive, but the
comments at the head of the file clearly state that the only
requirement on the defining polynomial is that it be irreducible.
Am I misunderstanding something here?
Paul

--
Mit freundlichen Grüßen

Johannes Grabmeier

Prof. Dr. Johannes Grabmeier
Köckstraße 1, D-94469 Deggendorf
Tel. [phone], Tel. [phone]
Tel. [phone] (d), Fax: [phone]

[Paul Onions]

Okay, but is that commonly used terminology? I always thought that
the word "generator" when used in the context of finite fields meant a
generator of the group of non-zero elements of the field (i.e. a
primitive element of the field).

Paul
On Fri, 24 Aug 2018 at 00:08, Prof. Dr. Johannes Grabmeier privat

Post by Prof. Dr. Johannes Grabmeier privat
no bug!
generator() does not necessarily return a primitive element, which
generates the cyclic group (F-{0},*)! It returns an element which generates
the algebra, so the result is correct.
generator : () -> %
++ generator() returns a root of the defining polynomial.
++ This element generates the field as an algebra over the ground field.
Perhaps you want to use
primitiveElement()$F16
(84) -> w := primitiveElement()$FFP(PF 2, p)
(84) %E + 1
FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?^3+?^2+?+1)
(85) -> order w
(85) 15
Type: PositiveInteger

Post by Paul Onions
Hi All,
It seems that calling generator() on a field created with
FiniteFieldExtensionByPolynomial may not return a primitive element of
the field. Specifically, when the field is created using an
irreducible (but not primitive) polynomial.
Example:-
(1) -> p : UP(x,PrimeField(2)) := x^4 + x^3 + x^2 + x + 1
4 3 2
(1) x + x + x + x + 1
Type: UnivariatePolynomial(x,PrimeField(2))
(2) -> F16 := FiniteFieldExtensionByPolynomial(PrimeField(2), p)
(2) FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?^3+?^2+?+1)
Type: Type
(3) -> g := generator()$F16
(3) %A
Type: FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?^3+?^2+?+1)
(4) -> g^5
(4) 1
Type: FiniteFieldExtensionByPolynomial(PrimeField(2),?^4+?^3+?^2+?+1)
Looking at the source (ffp.spad) it looks like the implementation of
generator() assumes that the defining polynomial is primitive, but the
comments at the head of the file clearly state that the only
requirement on the defining polynomial is that it be irreducible.
Am I misunderstanding something here?
Paul

--
Mit freundlichen Grüßen
Johannes Grabmeier
Prof. Dr. Johannes Grabmeier
Köckstraße 1, D-94469 Deggendorf
Tel. [phone], Tel. [phone]
Tel. [phone] (d), Fax: [phone]
--
You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.