Search

We present a complete algorithm that computes all hypergeometric solutions of homogeneous linear difference equations and rational solutions of parameterized linear difference equations in the setting of Π Σ ⁎ -fields. More generally, we provide a flexible framework for a big class of difference fields that are built by a tower of Π Σ ⁎ -field extensions over a difference field that enjoys certain algorithmic properties. As a consequence one can compute all solutions in terms of indefinite nested sums and products that arise within the components of a parameterized linear difference equation, and one can find all hypergeometric solutions of a homogeneous linear difference equation that are defined over the arising sums and products.

For a finite separable field extension K/k, all subfields can be obtained by intersecting so-called principal subfields of K/k. In this work we present a way to quickly compute these intersections. If the number of subfields is high, then this leads to faster run times and an improved complexity., Comment: Slides available at: http://www.math.fsu.edu/~hoeij/2017/Presentation.pdf

We present algorithmic, complexity and implementation results for the problem of isolating the real roots of a univariate polynomial in B α ∈ L [ y ] , where L = Q ( α ) is a simple algebraic extension of the rational numbers. We revisit two approaches for the problem. In the first approach, using resultant computations, we perform a reduction to a polynomial with integer coefficients and we deduce a bound of O ˜ B ( N 8 ) for isolating the real roots of B α , where N is an upper bound on all the quantities (degree and bitsize) of the input polynomials. The bound becomes O ˜ B ( N 7 ) if we use Pan's algorithm for isolating the real roots. In the second approach we isolate the real roots working directly on the polynomial of the input. We compute improved separation bounds for the roots and we prove that they are optimal, under mild assumptions. For isolating the real roots we consider a modified Sturm algorithm, and a modified version of descartes ' algorithm. For the former we prove a Boolean complexity bound of O ˜ B ( N 12 ) and for the latter a bound of O ˜ B ( N 5 ) . We present aggregate separation bounds and complexity results for isolating the real roots of all polynomials B α k , when α k runs over all the real conjugates of α. We show that we can isolate the real roots of all polynomials in O ˜ B ( N 5 ) . Finally, we implemented the algorithms in C as part of the core library of MATHEMATICA and we illustrate their efficiency over various data sets.

This paper considers fast algorithms for operations on linearized polynomials. We propose a new multiplication algorithm for skew polynomials (a generalization of linearized polynomials) which has sub-quadratic complexity in the polynomial degree $s$, independent of the underlying field extension degree~$m$. We show that our multiplication algorithm is faster than all known ones when $s \leq m$. Using a result by Caruso and Le Borgne (2017), this immediately implies a sub-quadratic division algorithm for linearized polynomials for arbitrary polynomial degree $s$. Also, we propose algorithms with sub-quadratic complexity for the $q$-transform, multi-point evaluation, computing minimal subspace polynomials, and interpolation, whose implementations were at least quadratic before. Using the new fast algorithm for the $q$-transform, we show how matrix multiplication over a finite field can be implemented by multiplying linearized polynomials of degrees at most $s=m$ if an elliptic normal basis of extension degree $m$ exists, providing a lower bound on the cost of the latter problem. Finally, it is shown how the new fast operations on linearized polynomials lead to the first error and erasure decoding algorithm for Gabidulin codes with sub-quadratic complexity., Comment: 25 pages, submitted to Journal of Symbolic Computation

Given a field extension K/k of degree n we are interested in finding the subfields of K containing k. There can be more than polynomially many subfields. We introduce the notion of generating subfields, a set of up to n subfields whose intersections give the rest. We provide an efficient algorithm which uses linear algebra in k or lattice reduction along with factorization in any extension of K. Implementations show that previously difficult cases can now be handled.

We define a class of algebras over finite fields, called polynomially cyclic algebras, which extend the class of abelian field extensions. We study the structure of these algebras; furthermore, we define and investigate properties of Lagrange resolvents and Gauss and Jacobi sums.Natural examples of polynomially cyclic algebras are for instance algebras of the form Fp[X]/(Fq(X)) where p,q are distinct odd primes and Fq is the q-th cyclotomic polynomial. Further examples occur similarly on replacing the cyclotomic polynomials with factors of division polynomials of elliptic curves. Finally, Gauss and Jacobi sums over polynomially cyclic algebras are applied for improving current algorithms for counting the number of points of elliptic curves over finite fields.

One of the main contributions which Volker Weispfenning made to mathematics is related to Groebner bases theory. In this paper we present an algorithm for computing all algebraic intermediate subfields in a separably generated unirational field extension (which in particular includes the zero characteristic case). One of the main tools is Groebner bases theory. Our algorithm also requires computing primitive elements and factoring over algebraic extensions. Moreover, the method can be extended to finitely generated K-algebras., Comment: 28 pages

Let A be a discrete valuation ring. We give a new approach to the round4 algorithm which permits the computation of the integral closure of A in a finite separable field extension of its field of fractions.

Using a constructive field-ideal correspondence it is shown how to compute the transcendence degree and a (separating) transcendence basis of finitely generated field extensionsk (x)/k(g), resp. how to determine the (separable) degree if k(x)/k(g) is algebraic. Moreover, this correspondence is used to derive a method for computing minimal polynomials and deciding field membership. Finally, a connection between certain intermediate fields of k(x)/k(g) and a minimal primary decomposition of a suitable ideal is described. For Galois extensions the field-ideal correspondence can also be used to determine the elements of the Galois group.

An extension of composite degree over a finite field may be implemented in one or more steps, involving the implementation of zero or more intermediate fields. A comparison of the expected efficiency of different field extensions is made, using a known probabilistic algorithm to form each extension. A new algorithm is described which provides a different method for forming single extensions of composite degree. It is shown that this method is expected to be more efficient than the previously used algorithm. Results of test runs of implementations of these algorithms are presented which support the theoretical claims.

With the exception of a finite set of finite differential Galois groups, if an irreducible linear differential equation L(y) = 0 of prime order with unimodular differential Galois group has a Liouvillian solution, then all algebraic solutions of smallest degree of the associated Riccati equation are solutions of a unique minimal polynomial. If the coefficients of L (y) = 0 are in Q (α)(x) ⊂ Q(x) this unique minimal polynomial is also defined over Q(α)(x). In the finite number of exceptions all solutions of L(y) = 0 are algebraic and in each case one can apriori give an extension Q(β)(x) over which the minimal polynomial of an algebraic solution of L(y) = 0 can be computed.

In this paper an efficient algorithm for curve parametrization is presented. This new approach allows much more than the commonly used algorithm. Consequently, the computations can be accelerated, and the degree of the field extension that must be made during the computation can be minimized. This generalizes an old result of Noether, telling when it is possible to compute a parametrization within the ground field. The choice of the pencil is done with purely diophantine considerations.

International audience; Based on a criterion due to Kneser, we present new results for the degree of field extensions generated by finitely many radicals. We also improve an algorithm given by Zippel for computing a basis for such an extension field. This algorithm may be effectively used by computer algebra systems to normalize expressions involving radicals.

A practical computational system is described for computing with an algebraic closure of a field. The system avoids factorization of polynomials over extension fields, but gives the illusion of a genuine field to the user. All roots of an arbitrary polynomial defined over such an algebraically closed field can be constructed and are easily distinguished within the system. The difficult case of inseparable extensions of function fields of positive characteristic is also handled properly by the system. A technique of modular evaluation into a finite field critically ensures that a unique genuine field is simulated by the system but also provides fast optimizations for some fundamental operations. Fast matrix techniques are also used for several non-trivial operations. The system has been successfully implemented within the Magma Computer Algebra System, and several examples are presented, using this implementation.

An Artin-Schreier tower over the finite field F_p is a tower of field extensions generated by polynomials of the form X^p - X - a. Following Cantor and Couveignes, we give algorithms with quasi-linear time complexity for arithmetic operations in such towers. As an application, we present an implementation of Couveignes' algorithm for computing isogenies between elliptic curves using the p-torsion., Comment: 28 pages, 4 figures, 3 tables, uses mathdots.sty, yjsco.sty Submitted to J. Symb. Comput

Algebraic function fields of positive characteristic are non-perfect fields, and many standard algorithms for solving some fundamental problems in commutative algebra simply do not work over these fields. This paper presents practical algorithms for the first time for (1) computing the primary decomposition of ideals of polynomial rings defined over such fields and (2) factoring arbitrary multivariate polynomials over such fields. Difficulties involving inseparability and the situation where the transcendence degree is greater than one are completely overcome, while the algorithms avoid explicit construction of any extension of the input base field. As a corollary, the problem of computing the primary decomposition of a positive-dimensional ideal over a finite field is also solved. The algorithms perform very effectively in an implementation within the Magma Computer Algebra System, and an analysis of their practical performance is given.

Gröbner bases can be used to solve various algorithmic problems in the context of finitely generated field extensions. One key idea is the computation of a certain kind of restriction of an ideal to a subring. With this restricted ideal many problems concerning function fields reduce to ideal theoretic problems which can be solved by means of Buchberger’s algorithm. In this contribution this approach is generalized to allow the computation of the restriction of an arbitrary ideal to a subring.