# Singular

 Page 1 of 1 [ 3 posts ]
 Print view | E-mail friend Previous topic | Next topic
Author Message
 Post subject: Polynomial division over GF(p^n)Posted: Thu Jul 06, 2017 11:43 am
Why is it not possible to divide polynomials over GF(p^n), if n >= 2? I get the following error:
Code:
> ring r = (7^2,a),x,dp;
> poly f = x2+1;
> poly g = x+1;
> f/g;
? not implemented
? error occurred in or before STDIN line 14: `f/g;`

Any help would be appreciated.

Top

 Post subject: Re: Polynomial division over GF(p^n)Posted: Fri Jul 07, 2017 3:40 pm

Joined: Wed Mar 03, 2010 5:08 pm
Posts: 104
Location: Germany,
Without going into detail, this is due to the fact that the polynomials have another presentation
over Galoisfields and different algorithms / implementations are involved. Also factorize is not at

Note that in general f/g only gives the quotient without remainder. Most likely that is not what
you want, but you are not lost here.
There is the command division
http://www.singular.uni-kl.de/Manual/latest/sing_226.htm#SEC266
which performs the task. It is important to use a global odering dp as you do.
Code:
factorize(f);
? not implemented
? error occurred in or before STDIN line 6: `factorize(f);`

> list L = division(f,g);
> L;
[1]:
_[1,1]=x-1
[2]:
_[1]=a16
[3]:
_[1,1]=1
> typeof(L[1]);
matrix
> typeof(L[1][1,1]);
poly
> typeof(L[2]);
ideal
> f==g*L[1][1,1] + L[2][1];
1

> (x-1)*(x+1) + 2;
x2+1

> a16;
a16
> number(2);
a16

(The third value L[3] is a unit matrix in global ordering, but the result is different
if you would work in ring rads = (49a,),x,ds;Try it!)

You may also define this finite field as an quadratic extension of Z_7 by the
minimal polynomial displayed from the ring itself.
Code:
> setring r;
> basering;
// coefficients: ZZ/49[a]
//   minpoly        : 1*a^2+6*a^1+3*a^0
// number of vars : 1
//        block   1 : ordering dp
//                  : names    x
//        block   2 : ordering C

With this approach, the elements are not represented as a power of the primitive
element a, but now f/g and factorize work.
Code:
> ring ra49 = (7,a),x,dp; minpoly = a2+6a+3;
// compare with above
> a16;
2
> number(2);
2
> poly f = x2+1;
> poly g = x+1;
> f/g;
x-1
> factorize (f);
[1]:
_[1]=1
_[2]=x+(-a-3)
_[3]=x+(a+3)
[2]:
1,1,1
> division(f,g);
[1]:
_[1,1]=x-1
[2]:
_[1]=2
[3]:
_[1,1]=1
> f == (x-1)*g +2;
1

Last edited by gorzel on Fri Jul 07, 2017 4:10 pm, edited 1 time in total.

Top

 Post subject: Re: Polynomial division over GF(p^n)Posted: Fri Jul 07, 2017 3:59 pm

But is this kind of pitfall anywhere documented? I tried to find something, but using google to find problems with Singular is kind of hard.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 3 posts ]

 You can post new topics in this forumYou can reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

 It is currently Tue Feb 20, 2018 8:05 am