International audience

Modular algorithms based on the Chinese Remainder Theorem (CRT) control intermediate expression growth by performing computations modulo small primes. Some primes, that we call "unlucky," produce incorrect results, or no result; their number can be bounded by finding a nonzero \(U \in \mathbb {Z}\) with the property that all unlucky primes divide U.

A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by n , the algorithm uses O ( n 1.43 ) field operations, breaking through the 3/2 barrier in the exponent for the first time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978, require O ( n 1.63 ) field operations in general, and n 3/2+ o (1) field operations in the special case of power series over a field of large enough characteristic. If cubic-time matrix multiplication is used, the new algorithm runs in n 5/3+ o (1) operations, while previous ones run in O ( n 2 ) operations. Our approach relies on the computation of a matrix of algebraic relations that is typically of small size. Randomization is used to reduce arbitrary input to this favorable situation.

In this paper, we consider the problem of deciding the existence of real solutions to a system of polynomial equations having real coefficients, and which are invariant under the action of the symmetric group. We construct and analyze a Monte Carlo probabilistic algorithm which solves this problem, under some regularity assumptions on the input, by taking advantage of the symmetry invariance property.

We present a new algorithm for computing the characteristic polynomial of an arbitrary endomorphism of a finite Drinfeld module using its associated crystalline cohomology. Our approach takes inspiration from Kedlaya’s p-adic algorithm for computing the characteristic polynomial of the Frobenius endomorphism on a hyperelliptic curve using Monsky-Washnitzer cohomology. The method is specialized using a baby-step giant-step algorithm for the particular case of the Frobenius endomorphism, and in this case we include a complexity analysis that demonstrates asymptotic gains over previously existing approaches.

We present a p-adic algorithm to recover the lexicographic Gröbner basis of an ideal in with a generating set in , with a complexity that is less than cubic in terms of the dimension of and softly linear in the height of its coefficients. We observe that previous results of Lazard’s that use Hermite normal forms to compute Gröbner bases for ideals with two generators can be generalized to a set of generators. We use this result to obtain a bound on the height of the coefficients of , and to control the probability of choosing a good prime p to build the p-adic expansion of .

We propose a randomized algorithm for multiplication in the ring of non-commutative polynomials Κ [x1,…,xn]{#948;1,…,δn}, where δ i=xi∂over∂ xi, dedicated to sparse inputs. The complexity of our algorithm is polynomial in the input size and on an a priori sparsity bound for the output.

Linear recurrent sequences are those whose elements are defined as linear combinations of preceding elements, and finding recurrence relations is a fundamental problem in computer algebra. In this paper, we focus on sequences whose elements are vectors over the ring 𝔸=𝕂[x] /{xd} of truncated polynomials. Finding the ideal of their recurrence relations has applications such as the computation of minimal polynomials and determinants of sparse matrices over 𝔸. We present three methods for finding this ideal: a Berlekamp-Massey-like approach due to Kurakin, one which computes the kernel of some block-Hankel matrix over 𝔸 via a minimal approximant basis, and one based on bivariate Padé approximation. We propose complexity improvements for the first two methods, respectively by avoiding the computation of redundant relations and by exploiting the Hankel structure to compress the approximation problem. Then we confirm these improvements empirically through a C++ implementation, and we discuss the above-mentioned applications.

We present a full analysis of the bit complexity of an efficient algorithm for the computation of at least one point in each connected component of a smooth real hypersurface. This is a basic and important operation in semi-algebraic geometry: it gives an upper bound on the number of connected components of a real hypersurface, and is also used in many higher level algorithms.

Consider the skew polynomial ring L[x; σ], where L is a field and σ is an automorphism of L of order r. We present two randomized algorithms for the multiplication of sparse skew polynomials in L[x;σ].

For any finite Galois field extension K/F, with Galois group G = Gal(K/F), there exists an element K whose orbit G · forms an F-basis of K. Such an is called a normal element and G · is a normal basis. We introduce a probabilistic algorithm for finding a normal element when G is either a finite abelian or a metacyclic group. The algorithm is based on the fact that deciding whether a random element K is normal can be reduced to deciding whether () K[G] is invertible (where ranges over all of G). Our algorithm requires a quadratic number of operations in the size of G for metacyclic G, and a slightly subquadratic number of operations for abelian G.

Following recent work by van der Hoeven and Lecerf (ISSAC 2017), we discuss the complexity of linear mappings, called untangling and \emphtangling by those authors, that arise in the context of computations with univariate polynomials. We give a slightly faster tangling algorithm and discuss new applications of these techniques. We show how to extend these ideas to bivariate settings, and use them to give bounds on the arithmetic complexity of certain algebras.

Complexity bounds for many problems on matrices with univariate polynomial entries have been improved in the last few years. Still, for most related algorithms, efficient implementations are not available, which leaves open the question of the practical impact of these algorithms, e.g. on applications such as decoding some error-correcting codes and solving polynomial systems or structured linear systems. In this paper, we discuss implementation aspects for most fundamental operations: multiplication, truncated inversion, approximants, interpolants, kernels, linear system solving, determinant, and basis reduction. We focus on prime fields with a word-size modulus, relying on Shoup's C++ library NTL. Combining these new tools to implement variants of Villard's algorithm for the resultant of generic bivariate polynomials (ISSAC 2018), we get better performance than the state of the art for large parameters.

Motivated by finding analogues of elliptic curve point counting techniques, we introduce one deterministic and two new Monte Carlo randomized algorithms to compute the characteristic polynomial of a finite rank-two Drinfeld module. We compare their asymptotic complexity to that of previous algorithms given by Gekeler, Narayanan and Garai-Papikian and discuss their practical behavior. In particular, we find that all three approaches represent either an improvement in complexity or an expansion of the parameter space over which the algorithm may be applied. Some experimental results are also presented.

We present an algorithm for simultaneous conversions between a given set of integers and their Residue Number System representations based on linear algebra. We provide a highly optimized implementation of the algorithm that exploits the computational features of modern processors. The main application of our algorithm is matrix multiplication over integers. Our speed-up of the conversions to and from the Residue Number System significantly improves the overall running time of matrix multiplication.

There exists a vast literature dedicated to algorithms for structured matrices, but relatively few descriptions of actual implementations and their practical performance in symbolic computation. In this paper, we consider the problem of solving Cauchy-like systems, and its application to mosaic Toeplitz systems, in two contexts: first in the unit cost model (which is a good model for computations over finite fields), then over Q. We introduce new variants of previous algorithms and describe an implementation of these techniques and its practical behavior. We pay a special attention to particular cases such as the computation of algebraic approximants.

We present explicit worst case degree and height bounds for the rational univariate representation of the isolated roots of polynomial systems based on mixed volume. We base our estimations on height bounds of resultants and we consider the case of 0-dimensional, positive dimensional, and parametric polynomial systems.

We give an algorithm for computing all roots of polynomials over a univariate power series ring over an exact field K. More precisely, given a precision d, and a polynomial Q whose coefficients are power series in x, the algorithm computes a representation of all power series f(x) such that Q(f(x)) = 0 mod xd. The algorithm works unconditionally, in particular also with multiple roots, where Newton iteration fails. Our main motivation comes from coding theory where instances of this problem arise and multiple roots must be handled. The cost bound for our algorithm matches the worst-case input and output size d deg(Q), up to logarithmic factors. This improves upon previous algorithms which were quadratic in at least one of d and deg(Q). Our algorithm is a refinement of a divide & conquer algorithm by Alekhnovich (2005), where the cost of recursive steps is better controlled via the computation of a factor of $Q$ which has a smaller degree while preserving the roots.

A roadmap for a semi-algebraic setSis a curve which has a non-empty and connected intersection with all connected components ofS. Hence, this kind of object, introduced by Canny, can be used to answer connectivity queries (with applications, for instance, to motion planning) but has also become of central importance in effective real algebraic geometry, since it is used in higher-level algorithms. In this article, we provide a probabilistic algorithm which computes roadmaps for smooth and bounded real algebraic sets. Its output size and running time are polynomial in (nD)nlog (d), whereDis the maximum of the degrees of the input polynomials,dis the dimension of the set under consideration andnis the number of variables. More precisely, the running time of the algorithm is essentially subquadratic in the output size. Even under our assumptions, it is the first roadmap algorithm with output size and running time polynomial in (nD)nlog (d).

The p-curvature of a system of linear differential equations in positive characteristic p is a matrix that measures how far the system is from having a basis of polynomial solutions. We show that the similarity class of the p-curvature can be determined without computing the p-curvature itself. More precisely, we design an algorithm that computes the invariant factors of the p-curvature in time quasi-linear in √ p. This is much less than the size of the p-curvature, which is generally linear in p. The new algorithm allows to answer a question originating from the study of the Ising model in statistical physics.

We compute minimal bases of solutions for a general interpolation problem, which encompasses Hermite-Pade approximation and constrained multivariate interpolation, and has applications in coding theory and security. This problem asks to find univariate polynomial relations between m vectors of size σ; these relations should have small degree with respect to an input degree shift. For an arbitrary shift, we propose an algorithm for the computation of an interpolation basis in shifted Popov normal form with a cost of O~(mω-1 σ) field operations, where ω is the exponent of matrix multiplication and the notation O~(·) indicates that logarithmic terms are omitted.

Let P and Q be two polynomials in K[x,y] with degree at most d, where K is a field. Denoting by R ∈ K[x] the resultant of P and Q with respect to y, we present an algorithm to compute R mod xk in O~(kd) arithmetic operations in K, where the ~O notation indicates that we omit polylogarithmic factors. This is an improvement over state-of-the-art algorithms that require to compute R in O~(d3) operations before computing its first k coefficients.

We design an algorithm for computing the p-curvature of a differential system in positive characteristic p. For a system of dimension r with coefficients of degree at most d, its complexity is O~ (p d rω) operations in the ground field (where ω denotes the exponent of matrix multiplication), whereas the size of the output is about p d r2. Our algorithm is then quasi-optimal assuming that matrix multiplication is (i.e. ω = 2). The main theoretical input we are using is the existence of a well-suited ring of series with divided powers for which an analogue of the Cauchy--Lipschitz Theorem holds.

We review several algorithms to construct finite fields and perform operations such as field embedding. Following previous work by notably Shoup, de Smit and Lenstra or Couveignes and Lercier, as well as results obtained with De Feo and Doliskani, we distinguish between algorithms that build "towers" of finite fields, with degrees of the form l, l2, l3,... and algorithms for composita. We show in particular how techniques that originate from algorithms for computing with triangular sets can be useful in such a context.

The interpolation step in the Guruswami-Sudan algorithm is a bivariate interpolation problem with multiplicities commonly solved in the literature using either structured linear algebra or basis reduction of polynomial lattices. This problem has been extended to three or more variables; for this generalization, all fast algorithms proposed so far rely on the lattice approach. In this paper, we reduce this multivariate interpolation problem to a problem of simultaneous polynomial approximations, which we solve using fast structured linear algebra. This improves the best known complexity bounds for the interpolation step of the list-decoding of Reed-Solomon codes, Parvaresh-Vardy codes, and folded Reed-Solomon codes. In particular, for Reed-Solomon list-decoding with re-encoding, our approach has complexity O~(ℓω-1m2(n - k)), where ℓ, m, n, and k are the list size, the multiplicity, the number of sample points, and the dimension of the code, and ω is the exponent of linear algebra; this accelerates the previously fastest known algorithm by a factor of ℓ/m.

We discuss theoretical and algorithmic questions related to the p-curvature of differential operators in characteristic p. Given such an operator L, and denoting by Ξ(L) the characteristic polynomial of its p-curvature, we first prove a new, alternative, description of Ξ(L). This description turns out to be particularly well suited to the fast computation of Ξ(L) when p is large: based on it, we design a new algorithm for computing Ξ(L), whose cost with respect to p is Õ(p0.5) operations in the ground field. This is remarkable since, prior to this work, the fastest algorithms for this task, and even for the subtask of deciding nilpotency of the p-curvature, had merely slightly subquadratic complexity Õ(p1.79).

We present algorithms to construct and do arithmetic operations in the algebraic closure of the finite field Fp. Our approach is inspired by algorithms for constructing irreducible polynomials, which first reduce to prime power degrees, then use composita techniques. We use similar ideas to give efficient algorithms for embeddings and isomorphisms.

Inspired by previous work of Shoup, Lenstra-De Smit and Couveignes-Lercier, we give fast algorithms to compute in the first levels of) the l-adic closure of a finite field. In many cases, our algorithms have quasi-linear complexity.

In this paper, we consider the problem of efficient computations with structured polynomials. We provide complexity results for computing Fourier Transform and Truncated Fourier Transform of symmetric polynomials, and for multiplying polynomials supported on a lattice.

We give an algorithm for solving bivariate polynomial systems over either k(T)[X,Y] or Q[X,Y] using a combination of lifting and modular composition techniques.

We provide algorithms computing power series solutions of a large class of differential or q-differential equations or systems. Their number of arithmetic operations grows linearly with the precision, up to logarithmic terms.

Let k be a field and let f ∈ k [T] be a polynomial of degree n. The universal decomposition algebra A is the quotient of k [X1,...,Xn] by the ideal of symmetric relations (those polynomials that vanish on all permutations of the roots of f). We show how to obtain efficient algorithms to compute in A. We use a univariate representation of A, i.e. an isomorphism of the form A k[T]/Q(T), since in this representation, arithmetic operations in A are known to be quasi-optimal. We give details for two related algorithms, to find the isomorphism above, and to compute the characteristic polynomial of any element of A.

We address complexity issues for linear differential equations in characteristic p >;0: resolution and computation of the p-curvature. For these tasks, our main focus is on algorithms whose complexity behaves well with respect to p. We prove bounds linear in p on the degree of polynomial solutions and propose algorithms for testing the existence of polynomial solutions in sublinear time Õ(p1/2), and for determining a whole basis of the solution space in quasi-linear time Õ(p); the Õ notation indicates that we hide logarithmic factors. We show that for equations of arbitrary order, the p-curvature can be computed in subquadratic time Õ(p1.79), and that this can be improved to O(log(p)) for first order equations and to Õ(p) for classes of second order equations.

An Artin-Schreier tower over the finite field Fp is a tower of field extensions generated by polynomials of the form Xp-X-α. 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.

Efficient algorithms are known for many operations on truncated power series (multiplication, powering, exponential, ...). Composition is a more complex task. We isolate a large class of power series for which composition can be performed efficiently. We deduce fast algorithms for converting polynomials between various bases, including Euler, Bernoulli, Fibonacci, and the orthogonal Laguerre, Hermite, Jacobi, Krawtchouk, Meixner and Meixner-Pollaczek.

It is classical that univariate algebraic functions satisfy linear differential equations with polynomial coefficients. Linear recurrences follow for the coefficients of their power series expansions. We show that the linear differential equation of minimal order has coefficients whose degree is cubic in the degree of the function. We also show that there exists a linear differential equation of order linear in the degree whose coefficients are only of quadratic degree. Furthermore, we prove the existence of recurrences of order and degree close to optimal. We study the complexity of computing these differential equations and recurrences. We deduce a fast algorithm for the expansion of algebraic series.

Linear systems with structures such as Toeplitz-, Vandermonde-or Cauchy-likeness can be solved in O~(α2n) operations, where n is the matrix size, α is its displacement rank, and O~denotes the omission of logarithmic factors. We show that for Toeplitz-like and Vandermonde-like trices, this cost can be reduced to O~(αω--1 n), where ω is a feasible exponent for matrix multiplication over the base field. The best known estimate for ω is ω< 2.38, resulting in costs of order O~(α1.38n). We also present consequences for Hermite-Padé approximation and bivariate interpolation.

We study arithmetic operations for triangular families of polynomials, concentrating on multiplication in dimension zero. By a suitable extension of fast univariate Euclidean division, we obtain theoretical and practical improvements over a direct recursive approach; for a family of special cases, we reach quasi-linear complexity. The main outcome we have in mind is the acceleration of higher-level algorithms, by interfacing our low-level implementation with languages such as AXIOM or Maple We show the potential for huge speed-ups, by comparing two AXIOM implementations of van Hoeij and Monagan's modular GCD algorithm.

The Schoof-Elkies-Atkin algorithm is the best known method for counting the number of points of an elliptic curve defined over a finite field of large characteristic. We use Abelian properties of division polynomials to design a fast theoretical and practical algorithm for finding the eigenvalue. 1.

We study the complexity of computing one or several terms (not necessarily consecutive) in a recurrence with polynomial coefficients. As applications, we improve the best currently known upper bounds for factoring integers deterministically and for computing the Cartier–Manin operator of hyperelliptic curves.

Though there is increased activity in the implementation of asymptotically fast polynomial arithmetic, little is reported on the details of such effort. In this paper, we discuss how we achieve high performance in implementing some well-studied fast algorithms for polynomial arithmetic in two high-level programming environments, AXIOM and Aldor.Two approaches are investigated. With Aldor we rely only on high-level generic code, whereas with AXIOM we endeavor to mix high-level, middle-level and low-level specialized code. We show that our implementations are satisfactory compared with other known computer algebra systems or libraries such as Magma v2.11-2 and NTL v5.4.

Changing the order of variables in bivariate triangular sets has applications in Trager's factorization algorithm, or in rational function integration. We discuss the complexity of this question, using baby steps / giant steps techniques and trace formulas, obtaining subquadratic estimates.

We present lifting techniques for triangular decompositions of zero-dimensional varieties, that extend the range of the previous methods. We discuss complexity aspects, and report on a preliminary implementation. Our theoretical results are comforted by these experiments. Categories and Subject Descriptors: I.I.2 [Computing

We study the multiplication of multivariate power series. We show that over large enough fields, the bilinear complexity of the product modulo a monomial ideal M is bounded by the product of the regularity of M by the degree of M. In some special cases, such as partial degree truncation, this estimate carries over to total complexity. This leads to complexity improvements for some basic algorithms with algebraic numbers, and some polynomial system solving algorithms.

Many polynomial factorization algorithms rely on Hensel lifting and factor recombination. For bivariate polynomials we show that lifting the factors up to a precision linear in the total degree of the polynomial to be factored is sufficient to deduce the recombination by linear algebra, using trace recombination. Then, the total cost of the lifting and the recombination stage is subquadratic in the size of the dense representation of the input polynomial. Lifting is often the practical bottleneck of this method: we propose an algorithm based on a faster multi-moduli computation for univariate polynomials and show that it saves a constant factor compared to the classical multifactor lifting algorithm.

We study the triangular representation of zero-dimensional varieties defined over the rational field (resp. a rational function field). We prove polynomial bounds in terms of intrinsic quantities for the height (resp. degree) of the coefficients of such triangular sets, whereas previous bounds were exponential. We also introduce a rational form of triangular representation, for which our estimates become linear. Experiments show the practical interest of this new representation.

The transposition principle, also called Tellegen's principle, is a set of transformation rules for linear programs. Yet, though well known, it is not used systematically, and few practical implementations rely on it. In this article, we propose explicit transposed versions of polynomial multiplication and division but also new faster algorithms for multipoint evaluation, interpolation and their transposes. We report on their implementation in Shoup's NTL C++ library.

Colloque avec actes et comité de lecture. internationale.

We study the representation of the solutions of a polynomial system by triangular sets, and concentrate on the positive-dimensional case. We reduce to dimension zero by placing the free variables in the base-field, so the solutions can be represented by triangular sets with coefficients in a rational function field. First, we give bounds on the degree of these coefficients; then we show how to apply lifting techniques in this context, and point out the role played by the evaluation properties of the input system. Our algorithms are implemented in Magma; we present two applications.

We propose a strategy to obtain approsin~ate solutions of an ovcrdctcrminecl consistent polynomial system of which we are only given an approximation.These systems will bc supposc:d to be instantiations of some polynomials Fl: . . .F,,.+I E k[X, :c] on the X variables: where k C C is an effective field: .c= (xl, : x,,) arc t.hc unknowns a.ntl X is to be seen as a set, of parameters.For an arbitrary choice of A; this system is generally inconsistent.M'c first propose hypothcscs under which the set of X where the systcni is consistent is an hypcrsurfacc of the space of paramclt.clrs.In the second part, wc use t.he algorithm for gcomctric resolution given in [7] in our particular setting, to give a theoretical polynomial-time resolution algorithm.Finally, we apply our st.rategv to the csaruple of an overconst,rainc:d parallel manipulator; where an est.ra m(xsurc is adjoined.-4 resolution is comput,ed in Magma t,hat demonstrates the feasibility of the method. .,