Fast computation of Grobner basis of homogenous ideals of F [x, y]

摘要

This paper provides a fast algorithm for Grobner bases of homogenous ideals of F[x, 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 ofa 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(N~22), 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.