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

:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:
Font size:
Font colour
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
which performs the task. It is important to use a global odering dp as you do.
   ? not implemented
   ? error occurred in or before STDIN line 6: `factorize(f);`

> list L = division(f,g);
> L;
> typeof(L[1]);
> typeof(L[1][1,1]);
> typeof(L[2]);
> f==g*L[1][1,1] + L[2][1];

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

> a16;
> number(2);

(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.
> 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.
> ring ra49 = (7,a),x,dp; minpoly = a2+6a+3;
// compare with above
> a16;
> number(2);
> poly f = x2+1;
> poly g = x+1;
> f/g;
> factorize (f);
> division(f,g);
> f == (x-1)*g +2;
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:
> 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 Mon Jun 25, 2018 12:10 am
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group