| Singular https://www.singular.uni-kl.de/forum/ |
|
| groebner basis over GF(2^k) https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=1860 |
Page 1 of 1 |
| Author: | gepo [ Sun Sep 26, 2010 1:56 am ] |
| Post subject: | groebner basis over GF(2^k) |
When we compute GB over GF(2^k), if root of minpoly becomes greater than k, the modulo operation will be triggered. My doubt is whether this happens on other variable rather than root of minpoly? For example, ring r=(2,X),(a0,b0,a1,b1,a2,b2,a3,b3, a_0_0_,b_0_0_,a_0_1_,b_0_1_, a_1_0_,b_1_0_,a_1_1_,b_1_1_, A0,B0,A1,B1, AA,BB,CC),lp; minpoly=1+X^3+X^4; ideal I= a_0_0_+a0+a3, a_0_1_+a2+a3, a_1_0_+a1+a3, a_1_1_+a2, b_0_0_+b0+b3, b_0_1_+b2+b3, b_1_0_+b1+b3, b_1_1_+b2, A0+a_0_0_+a_0_1_*(X^5), A1+a_1_0_+a_1_1_*(X^5), B0+b_0_0_+b_0_1_*(X^5), B1+b_1_0_+b_1_1_*(X^5), AA+A0*X^0+A1*X^1, BB+B0*X^0+B1*X^1, CC+AA*BB,; groebner(I); I want to know what happens when all the variables' degrees become greater than 4 (except "X"'s degree)? Is there a modulo operation triggered? Like "a_0_0_^4" will be reduced by "minpoly=1+X^3+X^4"? By the way, is there a command to dump all the results of internal procedures, like results of s-poly, reducetion procedure? Thanks a lot Gepo |
|
| Author: | gorzel [ Mon Sep 27, 2010 7:56 pm ] |
| Post subject: | Re: groebner basis over GF(2^k) |
gepo wrote: When we compute GB over GF(2^k), if root of minpoly becomes greater than k, the modulo operation will be triggered. My doubt is whether this happens on other variable rather than root of minpoly? For example, ring r=(2,X),(a0,b0,a1,b1,a2,b2,a3,b3, a_0_0_,b_0_0_,a_0_1_,b_0_1_, a_1_0_,b_1_0_,a_1_1_,b_1_1_, A0,B0,A1,B1, AA,BB,CC),lp; minpoly=1+X^3+X^4; I want to know what happens when all the variables' degrees become greater than 4 (except "X"'s degree)? Is there a modulo operation triggered? Like "a_0_0_^4" will be reduced by "minpoly=1+X^3+X^4"? By the way, is there a command to dump all the results of internal procedures, like results of s-poly, reducetion procedure? The minpoly reduces only the expressions in X, and this reduction is polynomial division. The resulting remainder of polynomial division by X^4+X^3+1 is a polynomial of degree less than 4. Thus, if the input has degree less than 4 the output will be the input. There is no trigger but the mechanism is always applied. Did you see: 5.1.22 dump http://www.singular.uni-kl.de/Manual/la ... htm#SEC229 |
|
| Author: | gepo [ Mon Sep 27, 2010 8:34 pm ] |
| Post subject: | Re: groebner basis over GF(2^k) |
Yes, it is right for X's degree. The problem is for other varaibles. Will they be reduced by division algorithm? For example, will "a_0_0_^4" be reduced by division algorithm? Thanks a lot. Gepo |
|
| Author: | gorzel [ Tue Sep 28, 2010 8:01 pm ] |
| Post subject: | Re: groebner basis over GF(2^k) |
If you want to reduce the polynomials in the variables a_0_ etc then use 5.1.111 reduce http://www.singular.uni-kl.de/Manual/la ... htm#SEC318 reduce(I,J); generalizes the polynomial division, where you put in J the polynomials which should do the reduction. Example: Code: > ring R=0,a,dp;
> poly f = 2a4+a2+1; > poly g = a3+2a2+1; > reduce(f,g); // It gives the remainder by polynomial division // ** _ is no standard basis // This is only a warning 9a2-2a+5 > reduce(f,std(g)); 9a2-2a+5 > division (f,g); [1]: _[1,1]=2a-4 [2]: _[1]=9a2-2a+5 [3]: _[1,1]=1 > f == (2a-4)*g + 9a2-2a+5; // representation of f= q*g +r 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/ |
|