Post a reply
Username:
Note:If not registered, provide any username. For more comfort, register here.
Subject:
Message body:
Enter your message here, it may contain no more than 60000 characters. 

Smilies
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:
Font size:
Font colour
Options:
BBCode is ON
[img] is ON
[flash] is OFF
[url] is ON
Smilies are ON
Disable BBCode
Disable smilies
Do not automatically parse URLs
Confirmation of post
To prevent automated posts the board requires you to enter a confirmation code. The code is displayed in the image you should see below. If you are visually impaired or cannot otherwise read this code please contact the %sBoard Administrator%s.
Confirmation code:
Enter the code exactly as it appears. All letters are case insensitive, there is no zero.
   

Topic review - Polynomial division over GF(p^n)
Author Message
  Post subject:  Re: Polynomial division over GF(p^n)  Reply with quote
Thank you for your answer, this definitely solves my problem :)

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.
Post Posted: Fri Jul 07, 2017 3:59 pm
  Post subject:  Re: Polynomial division over GF(p^n)  Reply with quote
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
your disposal.

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
Post Posted: Fri Jul 07, 2017 3:40 pm
  Post subject:  Polynomial division over GF(p^n)  Reply with quote
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.
Post Posted: Thu Jul 06, 2017 11:43 am


It is currently Tue Dec 18, 2018 7:33 pm
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group