Singular :: View topic - Polynomial division over GF(p^n)

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

> 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

> 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

Author:	redtrumpet [ Thu Jul 06, 2017 11:43 am ]
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.

Author:	gorzel [ Fri Jul 07, 2017 3:40 pm ]
Post subject:	Re: Polynomial division over GF(p^n)
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==gL[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 : 1a^2+6a^1+3a^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

Author:	redtrumpet [ Fri Jul 07, 2017 3:59 pm ]
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.

Singular https://www.singular.uni-kl.de/forum/

Polynomial division over GF(p^n) https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=2627	Page 1 of 1

Page 1 of 1	All times are UTC + 1 hour [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/