Fast computation of Grbner basis of homogenous ideals of F[x,y]

This paper provides a fast algorithm for Grobner bases of homogenous ideals of Fx, y] over a finite field F. We show that only the S-polynomials of neighbor pairs of a strictly ordered finite homogenours generating set are needed in the computing of a Grobner base of the homogenous ideal. It reduces dramatically the number of unnecessary S-polynomials that are processed. We also show that the computational complexity of our new algorithm is O(N2), where N is the maximum degree of the input generating polynomials. The new algorithm can be used to solve a problem of blind recognition of convolutional codes. This problem is a new generalization of the important problem of synthesis of a linear recurring sequence.