The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Revisiting a problem with finite fields and polynomials
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 3 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options May 13 2012, 6:19 pm
From: Paul Onions <paul.david.oni...@gmail.com>
Date: Sun, 13 May 2012 23:19:11 +0100
Local: Sun, May 13 2012 6:19 pm
Subject: Revisiting a problem with finite fields and polynomials
Hello,

In August last year I started a thread called 'Another problem with finite fields and polynomials' where I posted a problem I was having with FriCAS and finite fields. Ralf Hemmecke was very kind in responding to me, but we left the problem not quite resolved, with me promising to look further into it.

Well, only 9 months later, I am now looking further into it! :-)

In order to isolate the problem I have written a small SPAD file containing two definitions of finite field constructors, modelled on those that I found in the distribution. The first constructs a field directly, the second constructs a field as an extension of a given base field. The file is:

)abbrev domain MYFF MyFiniteField
MyFiniteField(p:PositiveInteger, n:PositiveInteger): FiniteAlgebraicExtensionField(PrimeField p) ==_
FiniteFieldExtensionByPolynomial(PrimeField p, createIrreduciblePoly(n)\$FiniteFieldPolynomialPackage(PrimeField p))

)abbrev domain MYFFX MyFiniteFieldExtension
MyFiniteFieldExtension(GF : FiniteFieldCategory, n : PositiveInteger): FiniteAlgebraicExtensionField(GF) ==_
FiniteFieldExtensionByPolynomial(GF, createIrreduciblePoly(n)\$FiniteFieldPolynomialPackage(GF))

then I have a small input file to construct two polynomials over a field, and compute the remainder of one modulo the other:

MyGF16 := MyFiniteField(2,4)
a := primitiveElement()\$MyGF16
p : POLY MyGF16 := a*x + 1
q : POLY MyGF16 := a*x
p rem q

which works and returns the answer 1 as expected. The problem arises when I change the first line to:

MyGF16 := MyFiniteFieldExtension(PrimeField(2),4)

because then I get the error message:

Error detected within library code:
coerce: element doesn't belong to smaller field

Now, I'm not asking anyone to dig around and tell me what the problem is, because that is something I promised to do (and which I think will gain me a better understanding of FriCAS), but I *am* asking for advice on how to look into this. Specifically, is there a way to get FriCAS to tell me what it is doing? That is, debug information such as what coercions are being applied and which functions in which domains are being called?

Paul

To post a message you must first join this group.
You do not have the permission required to post.
More options May 14 2012, 10:50 am
From: "Prof. Dr. Johannes Grabmeier" <johan...@grabmeier.net>
Date: Mon, 14 May 2012 16:50:07 +0200
Local: Mon, May 14 2012 10:50 am
Subject: Re: [fricas-devel] Revisiting a problem with finite fields and polynomials
Hallo Paul,

this is not a problem of the Finite Field code (which I contributed to very long ago) and to find the error, it is also not neccessary to encapsulate in new domains as your MYFF etc.

It is indeed a problem of function selection of the interpreter. Use:

)set mess sel on

The reason is the following: rem and quo are defined for Euclidean Domains, which Polynomial of a Field is not.
Therefore, if you change your variable definition to e.g.

p : UP(x. MYFFX) := a*x+1

etc. it will work! The interpreter has no extra work todo.

This also works if you define the polynomals of POLY MYFF or if you simply drop this domain in the definition of p and q.

Then the interpreter selects (by coercion facilities) as follows (using the fact that there is only one variable around):

Function Selection for rem
Arguments: (POLY(FF(2,4)),POLY(FF(2,4)))
-> no function rem found for arguments (POLY(FF(2,4)),POLY(FF(2,4)))

Function Selection for rem
Arguments: (UP(x,FF(2,4)),UP(x,FF(2,4)))

[1]  signature:   (UP(x,FF(2,4)),UP(x,FF(2,4))) -> UP(x,FF(2,4))
implemented: slot \$\$\$ from UP(x,FF(2,4))

However, for strange reason: THIS PROBLEM MUST BE HANDED TO EXPERTS OF THE INTERPRETER FUNCTION SELECTION FACILITIES AND COERCION FACILITIES,
the interpreter - in case of FFX(PF 2, 4) finds a coefficent coercion/retraction to transfer to POLY(PF 2) using a retraction (partial function) to the prime field, which is
here explicitly exhibited in FFX contrary to FF, where this is hidden for the interpreter I guess. For some strange reason, the heurisitic seems to think that transfer the problem to POLY PF 2, it will solve it from there. Actually this is not the case, as the transfer to the Polynomials over the prime field must fail (your observed error message).

(15) -> p' rem q'

Function Selection for rem
Arguments: (POLY(FFX(PF(2),4)),POLY(FFX(PF(2),4)))
-> no function rem found for arguments (POLY(FFX(PF(2),4)),POLY(FFX(PF(2),4)))

Function Selection for map by coercion facility (map)
Arguments: ((FFX(PF(2),4) -> PF(2)),POLY(FFX(PF(2),4)))
Target type: POLY(PF(2))

[1]  signature:   ((FFX(PF(2),4) -> PF(2)),POLY(FFX(PF(2),4))) -> POLY(PF(2))
implemented: slot (Polynomial (PrimeField 2))(Mapping (PrimeField 2) (FiniteFieldExtension (PrimeField 2) 4))(Polynomial (FiniteFieldExtension (PrimeField 2) 4)) from POLY2(FFX(PF(2),4),PF(2))

>> Error detected within library code:
coerce: element doesn't belong to smaller field

Am 14.05.2012 um 00:19 schrieb Paul Onions:

Mit freundlichen Grüßen

Johannes Grabmeier

Prof. Dr. Johannes Grabmeier
Köckstraße 1, D-94469 Deggendorf
Tel. +49-(0)-991-2979584, Tel. +49-(0)-171-5503789
Tel. +49-(0)-991-3615-100 (d),  Fax: +49-(0)-1803-5518-17745

To post a message you must first join this group.
You do not have the permission required to post.
More options May 14 2012, 3:51 pm
From: Paul Onions <paul.david.oni...@gmail.com>
Date: Mon, 14 May 2012 12:51:29 -0700 (PDT)
Local: Mon, May 14 2012 3:51 pm
Subject: Re: [fricas-devel] Revisiting a problem with finite fields and polynomials

On Monday, 14 May 2012 15:50:07 UTC+1, jg wrote:

> Hallo Paul,

> this is not a problem of the Finite Field code (which I contributed to
> very long ago) and to find the error, it is also not neccessary to
> encapsulate in new domains as your MYFF etc.

I created the MYFF and MYFFX domains so that I could control exactly how
they differ. When called from my input file, the only difference really was
where the PrimeField(2) constructor was called: for MYFF it is called in
the MYFF constructor, for MYFFX it is called by the interpreter and the
result passed to the MYFFX constructor.

It is indeed a problem of function selection of the interpreter. Use:

> )set mess sel on

Ahh, so that's the magic incantation I needed, thanks.

> The reason is the following: rem and quo are defined for Euclidean
> Domains, which Polynomial of a Field is not.
> Therefore, if you change your variable definition to e.g.

> p : UP(x. MYFFX) := a*x+1

> etc. it will work! The interpreter has no extra work todo.

Yes, that's what I ended up doing to get things working 9 months ago.

< ... >

> However, for strange reason: THIS PROBLEM MUST BE HANDED TO EXPERTS OF THE
> INTERPRETER FUNCTION SELECTION FACILITIES AND COERCION FACILITIES,
> the interpreter - in case of FFX(PF 2, 4) finds a coefficent
> coercion/retraction to transfer to POLY(PF 2) using a retraction (partial
> function) to the prime field, which is
> here explicitly exhibited in FFX contrary to FF, where this is hidden for
> the interpreter I guess. For some strange reason, the heurisitic seems to
> think that transfer the problem to POLY PF 2, it will solve it from there.
> Actually this is not the case, as the transfer to the Polynomials over the
> prime field must fail (your observed error message).

Okay, I wonder how difficult it is to understand the interpreter... :-o

Thanks very much for your help,
Paul