# Singular

 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
 Font size: Tiny Small Normal Large Huge Font colour [quote="gorzel"]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 [i]f/g[/i] only gives the quotient without remainder. Most likely that is not what you want, but you are not lost here. There is the command [b]division[/b] [url]http://www.singular.uni-kl.de/Manual/latest/sing_226.htm#SEC266[/url] which performs the task. It is important to use a global odering [b]dp[/b] 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 [/code] (The third value [i]L[3][/i] is a unit matrix in global ordering, but the result is different if you would work in [b]ring rads = (49a,),x,ds;[/b]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 [/code] With this approach, the elements are not represented as a power of the primitive element [i]a[/i], 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 [/code][/quote]
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
 redtrumpet
 Post subject: Re: Polynomial division over GF(p^n)
 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. 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.
 Posted: Fri Jul 07, 2017 3:59 pm
 gorzel
 Post subject: Re: Polynomial division over GF(p^n)
 Without going into detail, this is due to the fact that the polynomials have another presentationover 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#SEC266which 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 differentif 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 CWith this approach, the elements are not represented as a power of the primitiveelement 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 Without going into detail, this is due to the fact that the polynomials have another presentationover Galoisfields and different algorithms / implementations are involved. Also factorize is not at your disposal. Note that in general [i]f/g[/i] only gives the quotient without remainder. Most likely that is not what you want, but you are not lost here. There is the command [b]division[/b] [url]http://www.singular.uni-kl.de/Manual/latest/sing_226.htm#SEC266[/url]which performs the task. It is important to use a global odering [b]dp[/b] 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[/code](The third value [i]L[3][/i] is a unit matrix in global ordering, but the result is differentif you would work in [b]ring rads = (49a,),x,ds;[/b]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[/code]With this approach, the elements are not represented as a power of the primitiveelement [i]a[/i], 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[/code]
 Posted: Fri Jul 07, 2017 3:40 pm
 redtrumpet
 Post subject: Polynomial division over GF(p^n)
 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. 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;`[/code]Any help would be appreciated.
 Posted: Thu Jul 06, 2017 11:43 am

 It is currently Fri Oct 19, 2018 2:49 am