Efficient algorithms for order basis computation (Q420746)

The authors focus on the efficient computation of an order basis. Two algorithms are presented to compute an entire order basis with a reasonable cost of field operations. The new transformation provides a way to extend the results from one transformed problem to another transformed problem of a higher degree and leads to an efficient computation. The first algorithm is used to efficiently compute the elements of an order basis whose shifted degree is a specified parameter. This results in a new problem of smaller dimension and higher degree. The same process is repeated again on this new problem in order to compute the elements with the next highest shifted degree.