2.1.1 Basic computable objects and algorithms

The basic computable objects and algorithms we study, use, optimize or develop are among the most classical ones in computer algebra and are studied by many people around the world: they mainly focus on basic computer arithmetic, linear algebra, lattices, and both polynomial system and differential system solving.

In the context of OURAGAN, it is important to avoid reinventing the wheel and to re-use wherever possible existing objects and algorithms, not necessarily developed in our team so that the main effort is focused on finding good formulations/modelisations for an efficient use. Also, our approach for the development of basic computable objects and algorithms is application driven and follows a simple strategy : use the existing tools in priority, develop missing tools when required and then optimize the critical operations. First, for some selected problems, we do propose and develop general key algorithms (isolation of real roots of univariate polynomials, parametrisations of solutions of zero-dimensional polynomial systems, solutions of parametric equations, equidimensional decompositions, etc.) in order to complement the existing set computable objects developed and studied around the world (Gröbner bases, resultants 74, subresultants 95, critical point methods 52, etc.) which are also deeply used in our developments. Second, for a selection of well-known problems, we propose different computational strategies (for example the use of approximate arithmetic to speed up LLL algorithm or root isolators, still certifying the final result). Last, we propose specialized variants of known algorithms optimized for a given problem (for example, dedicated solvers for degenerated bivariate polynomials to be used in the computation of the topology of plane curves).

In the activity of OURAGAN, many key objects or algorithms around the resolution of algebraic systems are developed or optimized within the team, such as the resolution of polynomials in one variable with real coefficients 11414, rational parameterizations of solutions of zero-dimensional systems with rational coefficients 6013 or discriminant varieties for solving systems depending on parameters 11, but we are also power users of existing software (mainly Sage 1, Maple 2, Pari-GP 3,Snappea 4) and libraries (mainly gmp 5, mpfr 6, flint 7, arb 8, etc.) to which we contribute when it makes sense.

For our studies in number theory and applications to the security of cryptographic systems, our team works on three categories of basic algorithms: discrete logarithm computations 109 (for example to make progress on the computation of class groups in number fields 96), network reductions by means of LLL variants 85 and, obviously, various computations in linear algebra, for example dedicated to almost sparse matrices 110.

Finally, for the algorithmic approach to algebraic analysis of functional equations 56112113, we developed the effective study of both module theory and homological algebra 146 over certain noncommutative polynomial rings of functional operators 4, of Stafford's famous theorems on the Weyl algebras 136, of the equidimensional decomposition of functional systems 133, etc.

2.1.2 Computational Number Theory

Many frontiers between computable objects, algorithms (above section), computational number theory and applications, especially in cryptography are porous. However, one can classify our work in computational number theory into two classes of studies : computational algebraic number theory and (rigorous) numerical computations in number theory.

Our work on rigorous numerical computations is somehow a transverse activity in Ouragan : floating point arithmetic is used in many basic algorithms we develop (root isolation, LLL) and is thus present in almost all our research directions. However there are specific developments that could be labelized Number Theory, in particular contributions to numerical evaluations of $L$-functions which are deeply used in many problems in number theory (for example the Riemann Zeta function). We participate, for example to the L-functions and Modular Forms Database9 a world wide collaborative project.

Our work in computational algebraic number theory is driven by the algorithmic improvement to solve presumably hard problems relevant to cryptography. The use of number-theoretic hard problems in cryptography dates back to the invention of public-key cryptography by Diffie and Hellman 81, where they proposed a first instantiation of their paradigm based on the discrete logarithm problem in prime fields. The invention of RSA 144, based on the hardness of factoring came as a second example. The introduction of discrete logarithms on elliptic curves 115148 only confirmed this trend.

These crypto-systems attracted a lot of interest on the problems of factoring and discrete log. Their study led to the invention of fascinating new algorithms that can solve the problems much faster than initially expected :

• the elliptic curve method (ECM) 126
• the quadratic field for factoring 130 and its variant for discrete log called the Gaussian integers method 123
• the number field sieve (NFS) 125

Since the invention of NFS in the 90’s, many optimizations of this algorithm have been performed. However, an algorithm with better complexity hasn’t been found for factoring and discrete logarithms in large characteristic.

While factorization and discrete logarithm problems have a long history in cryptography, the recent post-quantum cryptosystems introduce a new variety of presumably hard problems/objects/algorithms with cryptographic relevance: the shortest vector problem (SVP), the closest vector problem (CVP) or the computation of isogenies between elliptic curves, especially in the supersingular case.

Members of OURAGAN started working on the topic of discrete logarithms around 1998, with several computation records that were announced on the NMBRTHRY mailing list. In large characteristic, especially for the case of prime fields, the best current method is the number field sieve (NFS) algorithm. In particular, they published the first NFS based record computation10. Despite huge practical improvements, the prime field case algorithm hasn't really changed since that first record. Around the same time, we also presented small characteristic computation record based on simplifications of the Function Field Sieve (FFS) algorithm  108.

In 2006, important changes occurred concerning the FFS and NFS algorithms, indeed, while the algorithms only covered the extreme case of constant characteristic and constant extension degree, two papers extended their ranges of applicability to all finite fields. At the same time, this permitted a big simplification of the FFS, removing the need for function fields.

Starting from 2012, new results appeared in small characteristic. Initially based on a simplification of the 2006 result, they quickly blossomed into the Frobenial representation methods, with quasi-polynomial time complexity 109, 97.

An interesting side-effect of this research was the need to revisit the key sizes of pairing-based cryptography. This type of cryptography is also a topic of interest for OURAGAN. In particular, it was introduced in 2000 9.

The computations of class groups in number fields has strong links with the computations of discrete logarithms or factorizations using the NFS (number field sieve) strategy which as the name suggests is based on the use of number fields. Roughly speaking, the NFS algorithm uses two number fields and the strategy consists in choosing number fields with small sized coefficients in their definition polynomials. On the contrary, in class group computations, there is a single number field, which is clearly a simplification, but this field is given as input by some fixed definition polynomial. Obviously, the degree of this polynomial as well as the size of its coefficients are both influencing the complexity of the computations so that finding other polynomials representing the same class group but with a better characterization (degree or coefficient's sizes) is a mathematical problem with direct practical consequences. We proposed a method to address the problem 96, but many issues remain open.

Computing generators of principal ideals of cyclotomic fields is also strongly related to the computation of class groups in number fields. Ideals in cyclotomic fields are used in a number of recent public-key cryptosystems. Among the difficult problems that ensure the safety of these systems, there is one that consists in finding a small generator, if it exists, of an ideal. The case of cyclotomic fields is considered 55.

2.1.3 Topology in small dimension

2.1.4 Algebraic analysis of functional systems

Systems of functional equations or simply functional systems are systems whose unknowns are functions, such as systems of ordinary or partial differential equations, of differential time-delay equations, of difference equations, of integro-differential equations, etc.

Numerical aspects of functional systems, especially differential systems, have been widely studied in applied mathematics due to the importance of numerical simulation issues.

Complementary approaches, based on algebraic methods, are usually upstream or help the numerical simulation of systems of functional systems. These methods also tackle a different range of questions and problems such as algebraic preconditioning, elimination and simplification, completion to formal integrability or involution, computation of integrability conditions and compatibility conditions, index reduction, reduction of variables, choice of adapted coordinate systems based on symmetries, computation of first integrals of motion, conservation laws and Lax pairs, Liouville integrability, study of the (asymptotic) behavior of solutions at a singularity, etc. Although not yet very popular in applied mathematics, these theories have lengthy been studied in fundamental mathematics and were developed by Lie, Cartan, Janet, Ritt, Kolchin, Spencer, etc. 104112113116143131.

Over the past years, certain of these algebraic approaches to functional systems have been investigated within an algorithmic viewpoint, mostly driven by applications to engineering sciences such as mathematical systems theory and control theory. We have played a role towards these effective developments, especially in the direction of an algorithmic approach to the so-called algebraic analysis112, 113, 56, a mathematical theory developed by the Japanese school of Sato, which studies linear differential systems by means of both algebraic and analytic methods. To develop an effective approach to algebraic analysis, we first have to make algorithmic standard results on rings of functional operators, module theory, homological algebra, algebraic geometry, sheaf theory, category theory, etc., and to implement them in computer algebra systems. Based on elimination theory (Gröbner or Janet bases 104, 72, 145, differential algebra 5886, Spencer's theory 131, etc.), in 4, 5, we have initiated such a computational algebraic analysis approach for general classes of functional systems (and not only for holonomic systems as done in the literature of computer algebra 72). Based on the effective aspects to algebraic analysis approach, the parametrizability problem 4, the reduction and (Serre) decomposition problems 5, the equidimensional decomposition 133, Stafford's famous theorems for the Weyl algebras 136, etc., have been studied and solutions have been implemented in Maple, Mathematica, and GAP715. But these results are only the first steps towards computational algebraic analysis, its implementation in computer algebra systems, and its applications to mathematical systems, control theory, signal processing, mathematical physics, etc.

Rigorous numerical computations

Some studies in this area will be driven by some other directions, for example, the rigorous evaluation of non algebraic functions on algebraic varieties might become central for some of our work on topology in small dimension (volumes of varieties, drawing of amoeba) or control theory (approximations of discriminant varieties) are our two main current sources of interesting problems. In the same spirit, the work on $L$-functions computations (extending the computation range, algorithmic tools for computing algebraic data from the $L$ function) will naturally follow.

On the other hand, another objective is to extend existing results on periods of algebraic curves to general curves and higher dimensional varieties is a general promising direction. This project aims at providing tools for integration on higher homology groups of algebraic curves, ie computing Gauss-Manin connections. It requires good understanding of their topology, and more algorithmic tools on differential equations.

Character varieties

The brute force approach to computable objects from topology of small dimension will not allow any significant progress. As explained above, the systems that arise from these problems are simply outside the range of doable computations. We still continue the work in this direction by a four-fold approach, with all three directions deeply inter-related. First, we focus on a couple of especially meaningful (for the applications) cases, in particular the 3-dimensional manifold called Whitehead link complement. At this point, we are able to make steps in the computation and describe part of the solutions 89, 101; we hope to be able to complete the computation using every piece of information to simplify the system. Second, we continue the theoretical work to understand more properties of these systems 87. These properties may prove how useful for the mathematical understanding is the resolution of such systems - or at least the extraction of meaningful information. This approach is for example carried on by Falbel and his work on configuration of flags 90, 92. Third, we position ourselves as experts in the know-how of this kind of computations and natural interlocutors for colleagues coming up with a question on such a computable object (see 98 and 101). This also allows us to push forward the kind of computation we actually do and make progress in the direction of the second point. We are credible interlocutors because our team has the blend of theoretical knowledge and computational capabilities that grants effective resolutions of the problems we are presented. And last, we use the knowledge already acquired to pursue our theoretical study of the CR-spherical geometry 79, 91, 88.

Another direction of work is the help to the community in experimental mathematics on new objects. It involves downsizing the system we are looking at (for example by going back to systems coming from hyperbolic geometry and not CR-spherical geometry) and get the most out of what we can compute, by studying new objects. An example of this research direction is the work of Guilloux around the volume function on deformation varieties. This is a real-analytic function defined on the varieties we specialized in computing. Being able to do effective computations with this function led first to a conjecture 100. Then, theoretical discussions around this conjecture led to a paper on a new approach to the Mahler measure of some 2-variables polynomials 99. In turn, this last paper gave a formula for the Mahler measure in terms of a function akin to the volume function applied at points in an algebraic variety whose moduli of coordinates are 1. The OURAGAN team has the expertise to compute all the objects appearing in this formula, opening the way to another area of application. This area is deeply linked with number theory as well as topology of small dimension. It requires all the tools at disposition within OURAGAN.

Knot theory

We will carry on the exhaustive search for the lexicographic degrees for the rational knots. They correspond to trigonal space curves: computations in the braid group $B_3$, explicit parametrization of trigonal curves corresponding to "dessins d'enfants", etc. The problem seems much more harder when looking for more general knots.

On the other hand, a natural direction would be: given an explicit polynomial space curve, determine the under/over nature of the crossings when projecting, draw it and determine the known knot 16 it is isotopic to.

Vizualisation and Computational Geometry

As mentioned above, the drawing of algebraic curves and surfaces is a critical action in OURAGAN since it is a key ingredient in numerous developments. In some cases, one will need a fully certified study of the variety for deciding existence of solutions (for example a region in a robot's parameter's space with solutions to the DKP above or deciding if some variety crosses the unit polydisk for some stability problems in control-theory), in some other cases just a partial but certified approximation of a surface (path planning in robotics, evaluation of non algebraic functions over an algebraic variety for volumes of knot complements in the study of character varieties).

On the one hand, we will contribute to general tools like ISOTOP 17 under the supervision of the GAMBLE project-team and, on the other hand, we will propose ad-hoc solutions by gluing some of our basic tools (problems of high degrees in robust control theory). The priority is to provide a first software that implements methods that fit as most as possible the very last complexity results we got on several (theoretical) algorithms for the computation of the topology of plane curves.

A particular effort will be devoted to the resolution of overconstraint bivariate systems which are useful for the studies of singular points and to polynomials systems in 3 variables in the same spirit : avoid the use of Gröbner basis and propose a new algorithm with a state-of-the-art complexity and with a good practical behavior.

In parallel, one will have to carefully study the drawing of graphs of non algebraic functions over algebraic complex surfaces for providing several tools which are useful for mathematicians working on topology in small dimension (a well known example is the drawing of amoebia, a way of representing a complex curve on a sheet of paper).

6.1.1 ISOTOP

• Name: Topology and geometry of planar algebraic curves
• Keywords: Topology, Curve plotting, Geometric computing
• Functional Description: Isotop is a Maple software for computing the topology of an algebraic plane curve, that is, for computing an arrangement of polylines isotopic to the input curve. This problem is a necessary key step for computing arrangements of algebraic curves and has also applications for curve plotting. This software has been developed since 2007 in collaboration with F. Rouillier from Inria Paris - Rocquencourt.
• URL: https://isotop.gamble.loria.fr/
• Publications: hal-00809430, hal-00809425, inria-00329754, inria-00580431, hal-00992634, hal-01342211, inria-00425383, inria-00517175, hal-01468796, hal-00977671
• Authors: Luis Penaranda, Marc Pouget, Sylvain Lazard
• Contacts: Sylvain Lazard, Marc Pouget
• Participants: Luis Penaranda, Marc Pouget, Sylvain Lazard

6.1.2 RS

• Functional Description: Real Roots isolation for algebraic systems with rational coefficients with a finite number of Complex Roots
• URL: https://team.inria.fr/ouragan/software/
• Author: Fabrice Rouillier
• Contact: Fabrice Rouillier
• Participant: Fabrice Rouillier

6.1.3 A NewDsc

• Name: A New Descartes
• Keyword: Scientific computing
• Functional Description: Computations of the real roots of univariate polynomials with rational coefficients.
• URL: https://anewdsc.mpi-inf.mpg.de
• Authors: Fabrice Rouillier, Alexander Kobel, Michael Sagraloff
• Contact: Fabrice Rouillier
• Partner: Max Planck Institute for Software Systems

6.1.4 SIROPA

• Keywords: Robotics, Kinematics
• Functional Description: Library of functions for certified computations of the properties of articulated mechanisms, particularly the study of their singularities
• URL: http://siropa.gforge.inria.fr/
• Authors: Damien Chablat, Fabrice Rouillier, Guillaume Moroz, Philippe Wenger
• Contacts: Fabrice Rouillier, Guillaume Moroz
• Partner: LS2N

6.1.5 MPFI

• Keyword: Arithmetic
• Functional Description: MPFI is a C library based on MPFR and GMP for multi precision floating point arithmetic.
• URL: http://mpfi.gforge.inria.fr
• Contacts: Fabrice Rouillier, Nathalie Revol

7.1.1 Numerical verification of the Cohen-Lenstra-Martinet heuristics and of Greenberg's p-rationality conjecture

In 16, we make a series of numerical experiments to support Greenberg's p-rationality conjecture, we present a family of p-rational biquadratic fields and we find new examples of p-rational multiquadratic fields. In the case of multiquadratic and multicubic fields we show that the conjecture is a consequence of the Cohen-Lenstra-Martinet heuristic and of the conjecture of Hofmann and Zhang on the p-adic regulator, and we bring new numerical data to support the extensions of these conjectures. We compare the known algorithmic tools and propose some improvements.

7.1.2 An asymptotically faster version of FV supported on HPR

State-of-the-art implementations of homomorphic encryption exploit the Fan and Vercauteren (FV) scheme and the Residue Number System (RNS). While the RNS breaks down large integer arithmetic into smaller independent channels, its non-positional nature makes operations such as division and rounding hard to implement, and makes the representation of small values inefficient. In 25, we propose the application of the Hybrid Position-Residues Number System representation to the FV scheme. This is a positional representation of large radix where the digits are represented in RNS. It inherits the benefits from RNS and allows to accelerate the critical division and rounding operations while also making the representation of smaller values more compact. This directly benefits the decryp-tion and the homomorphic multiplication procedures, reducing their asymptotic complexity, in dimension n, from $O\left(n^{2}logn\right)$ to $O\left(nlogn\right)$ and from $O\left(n^{3}logn\right)$ to $O\left(n^3\right)$, respectively and has resulted in noticeable speedups when experimentally compared to related art RNS implementations.

7.2.1 Multilinear Polynomial Systems: Root Isolation and Bit Complexity

In 21, we exploit structure in polynomial system solving by considering polyno-mials that are linear in subsets of the variables. We focus on algorithms and their Boolean complexity for computing isolating hyperboxes for all the isolated complex roots of well-constrained, unmixed systems of multilinear polynomials based on resultant methods. We enumerate all expressions of the multihomogeneous (or multigraded) resultant of such systems as a determinant of Sylvester-like matrices, aka generalized Sylvester matrices. We construct these matrices by means of Weyman homological complexes, which generalize the Cayley-Koszul complex. The computation of the determinant of the resultant matrix is the bottleneck for the overall complexity. We exploit the quasi-Toeplitz structure to reduce the problem to efficient matrix-vector multiplication, which corresponds to multivariate polynomial multiplication, by extending the seminal work on Macaulay matrices of Canny, Kaltofen, and Yagati to the multi-homogeneous case. We compute a rational univariate representation of the roots, based on the primitive element method. In the case of 0-dimensional systems we present a Monte Carlo algorithm with probability of success $1-1/2^r$, for a given $r\ge 1$, and bit complexity $O_B(n^2{D}^{(4+e)}(n^{(N+1)}+\tau )+n{D}^{(2+e)}r(D+r))$ for any $e>0$, where $n$ is the number of variables, $D$ equals the multilinear Bézout bound, $N$ is the number of variable subsets, and $\tau$ is the maximum coefficient bitsize. We present an algorithmic variant to compute the isolated roots of overdetermined and positive-dimensional systems. Thus our algorithms and complexity analysis apply in general with no assumptions on the input.

7.2.2 Separation bounds for polynomial systems

In 22, we rely on aggregate separation bounds for univariate polynomials to introduce novel worst-case separation bounds for the isolated roots of zero-dimensional, positive-dimensional, and overde- termined polynomial systems. We exploit the structure of the given system, as well as bounds on the height of the sparse (or toric) resultant, by means of mixed volume, thus establishing adaptive bounds. Our bounds improve upon Canny’s Gap theorem [9]. Moreover, they exploit sparseness and they apply without any assumptions on the input polynomial system. To evaluate the quality of the bounds, we present polynomial systems whose root separation is asymptotically not far from our bounds. We apply our bounds to three problems. First, we use them to estimate the bitsize of the eigenvalues and eigenvectors of an integer matrix; thus we provide a new proof that the problem has polynomial bit complexity. Second, we bound the value of a positive polynomial over the simplex: we improve by at least one order of magnitude upon all existing bounds. Finally, we asymptotically bound the number of steps of any purely subdivision-based algorithm that isolates all real roots of a polynomial system.

7.2.3 Matrix formulae for Resultants and Discriminants of Bivariate Tensor-product Polynomials

The construction of optimal resultant formulae for polynomial systems is one of the main areas of research in computational algebraic geometry. However, most of the constructions are restricted to formulae for unmixed polynomial systems, that is, systems of polynomials which all have the same support. Such a condition is restrictive, since mixed systems of equations arise frequently in many problems. Nevertheless, resultant formulae for mixed polynomial systems is a very challenging problem. In 19, we present a square, Koszul-type, matrix, the determinant of which is the resultant of an arbitrary (mixed) bivariate tensor-product polynomial system. The formula generalizes the classical Sylvester matrix of two univariate polynomials, since it expresses a map of degree one, that is, the elements of the corresponding matrix are up to sign the coefficients of the input polynomials. Interestingly, the matrix expresses a primal-dual multiplication map, that is, the tensor product of a univariate multiplication map with a map expressing derivation in a dual space. In addition we prove an impossibility result which states that for tensor-product systems with more than two (affine) variables there are no universal degree-one formulae, unless the system is unmixed. Last but not least, we present applications of the new construction in the efficient computation of discriminants and mixed discriminants.

7.2.4 Certified lattice reduction

Quadratic form reduction and lattice reduction are fundamental tools in computational number theory and in computer science, especially in cryptography. The celebrated Lenstra–Lenstra–Lovász reduction algorithm (so-called LLL) has been improved in many ways through the past decades and remains one of the central methods used for reducing integral lattice basis. In particular, its floating-point variants—where the rational arithmetic required by Gram–Schmidt orthogonalization is replaced by floating-point arithmetic—are now the fastest known. However, the systematic study of the reduction theory of real quadratic forms or, more generally, of real lattices is not widely represented in the literature. When the problem arises, the lattice is usually replaced by an integral approximation of (a multiple of) the original lattice, which is then reduced. While practically useful and proven in some special cases, this method doesn't offer any guarantee of success in general. In 23, we present an adaptive-precision version of a generalized LLL algorithm that covers this case in all generality. In particular, we replace floating-point arithmetic by Interval Arithmetic to certify the behavior of the algorithm. We conclude by giving a typical application of the result in algebraic number theory for the reduction of ideal lattices in number fields.

7.3.1 Computing polynomial solutions and annihilators of integro-differential operators with polynomial coefficients

In 37, we study algorithmic aspects of the algebra of linear ordinary integro-differential operators with polynomial coefficients. Even though this algebra is not Noetherian and has zero divisors, Bavula recently proved that it is coherent, which allows one to develop an algebraic systems theory over this algebra. For an algorithmic approach to linear systems of integro-differential equations with boundary conditions, computing the kernel of matrices with entries in this algebra is a fundamental task. As a first step, we have to find annihilators of integro-differential operators, which, in turn, is related to the computation of polynomial solutions of such operators. For a class of linear operators including integro-differential operators, we present an algorithmic approach for computing polynomial solutions and the index. A generating set for right annihilators can be constructed in terms of such polynomial solutions. For initial value problems, an involution of the algebra of integro-differential operators then allows us to compute left annihilators, which can be interpreted as compatibility conditions of integro-differential equations with boundary conditions. We illustrate our approach using an implementation in the computer algebra system Maple.

7.3.2 Equivalences of linear functional systems

In 36, within the algebraic analysis approach to linear systems theory, we investigate the equivalence problem of linear functional systems, i.e., the problem of characterizing when all the solutions of two linear functional systems are in a one-to- one correspondence. To do that, we first provide a new characterization of isomorphic finitely presented modules in terms of inflation of their presentation matrices. We then prove several isomorphisms which are consequences of the unimodular completion problem. We then use these isomorphisms to complete and refine existing results concerning Serre’s reduction problem. Finally, different consequences of these results are given. All the results obtained here are algorithmic for rings for which Gröbner basis techniques exist and the computations can be performed by the Maple packages OreModules and OreMorphisms or the Mathematica package OreAlgebraicAnalysis.

7.3.3 Effective algebraic analysis approach to linear systems over Ore algebras

The purpose of 35 is to present a survey on the effective algebraic analysis approach to linear systems theory with applications to control theory and mathematical physics. In particular, we show how the combination of effective methods of computer algebra – based on Gröbner basis techniques over a class of noncommutative polynomial rings of functional operators called Ore algebras – and constructive aspects of module theory and homological algebra enables the characterization of structural properties of linear functional systems. Algorithms are given and a dedicated implementation, called OreAlgebraicAnalysis, based on the Mathematica package HolonomicFunctions, is demonstrated.

7.4.1 Computing the Homology of Semialgebraic Sets. II: General formulas.

In 18, we describe and analyze a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of semialgebraic sets given by Boolean formulas. The algorithm works in weak exponential time. This means that outside a subset of data having exponentially small measure, the cost of the algorithm is single exponential in the size of the data. This extends the work in Part I to arbitrary semialgebraic sets. All previous algorithms proposed for this problem have doubly exponential complexity.

7.4.2 Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces

The condition-based complexity analysis framework is one of the gems of modern numerical algebraic geometry and theoretical computer science. One of the challenges that it poses is to expand the currently limited range of random polynomials that we can handle. Despite important recent progress, the available tools cannot handle random sparse polynomials and Gaussian polynomials, that is polynomials whose coefficients are i.i.d. Gaussian random variables. In 30, initiate a condition-based complexity framework based on the norm of the cube, that is a step in this direction. We present this framework for real hypersurfaces. We demonstrate its capabilities by providing a new probabilistic complexity analysis for the Plantinga-Vegter algorithm, which covers both random sparse (alas a restricted sparseness structure) polynomials and random Gaussian polynomials. We present explicit results with structured random polynomials for problems with two or more dimensions. Additionally, we provide some estimates of the separation bound of a univariate polynomial in our current framework.

7.4.3 Computing the topology of a plane or space hyperelliptic curve

In 15,We present algorithms to compute the topology of 2D and 3D hyperelliptic curves. The algorithms are based on the fact that 2D and 3D hyperelliptic curves can be seen as the image of a planar curve (the Weierstrass form of the curve), whose topology is easy to compute, under a birational mapping of the plane or the space. We report on a Maple implementation of these algorithms, and present several examples. Complexity and certification issues are also discussed.

7.4.4 PTOPO: A Maple package for the topology of parametric curves

In 24, we present PTOPO, a MAPLE package computing the topology and describing the geometry of a parametric plane curve. The algorithm behind PTOPO constructs an abstract graph that is isotopic to the curve. PTOPO exploits the benefits of the parametric representation and performs all computations in the parameter space using exact computing. PTOPO computes the topology and visualizes the curve in less than a second for most examples in the literature.

7.4.5 On the Geometry and the Topology of Parametric Curves

In 31, we consider the problem of computing the topology and describing the geometry of a parametric curve in ${ℝ}^n$. We present an algorithm, PTOPO, that constructs an abstract graph that is isotopic to the curve in the embedding space. Our method exploits the benefits of the parametric representation and does not resort to implicitization. Most importantly, we perform all computations in the parameter space and not in the implicit space. When the parametrization involves polynomials of degree at most $d$ and maximum bitsize of coefficients $\tau$, then the worst case bit complexity of PTOPO is ${\tilde{O}}_B(n{d}^6+n{d}^5\tau +d^4(n^2+n\tau )+d^3(n^2\tau +n^3)+n^3{d}^2\tau )$. This bound matches the current record bound ${\tilde{O}}_B(d^6+d^5\tau )$ for the problem of computing the topology of a planar algebraic curve given in implicit form. For planar and space curves, if $N=max\{d,\tau \}$, the complexity of PTOPO becomes ${\tilde{O}}_B\left(N^6\right)$, which improves the state-of-the-art result, due to Alcázar and Díaz-Toca, by a factor of $N^{10}$. However, visualizing the curve on top of the abstract graph construction, increases the bound to ${\tilde{O}}_B\left(N^7\right)$. We have implemented PTOPO in maple for the case of planar curves. Our experiments illustrate its practical nature.

7.4.6 Sampling the feasible sets of SDPs and volume approximation

In 20, we present algorithmic, complexity, and implementation results on the problem of sampling points in the interior and the boundary of a spectrahedron, that is the feasible region of a semidefinite program. Our main tool is random walks. We define and analyze a set of primitive geometric operations that exploits the algebraic properties of spectrahedra and the polynomial eigenvalue problem, and leads to the realization of a broad collection of efficient random walks. We demonstrate random walks that experimentally show faster mixing time than the ones used previously for sampling from spectrahedra in theory or applications, for example Hit and Run. Consecutively, the variety of random walks allows us to sample from general probability distributions, for example the family of log-concave distributions which arise frequently in numerous applications. We apply our tools to compute (i) the volume of a spectrahedron and (ii) the expectation of functions coming from robust optimal control. We provide a C++ open source implementation of our methods that scales efficiently up to to dimension 200. We illustrate its efficiency on various data sets.

7.4.7 The lexicographic degree of the first two-bridge knots

In 17 study the degree of polynomial representations of knots. We give the lexicographic degree of all two-bridge knots with 11 or fewer crossings. First, we estimate the total degree of a lexicographic parametrisation of such a knot. This allows us to transform this problem into a study of real algebraic trigonal plane curves, and in particular to use the braid theoretical method developed by Orevkov.

7.5.1 Algebraic aspects of a rank factorization problem arising in vibration analysis

The article 28 continues the study of a factorization problem arising in gear fault surveillance. The structure of a class of solutions – interesting in practice – of this factorization problem is studied. We show that these solutions can be parametrized. The parameter space P is proved to be the complementary of an algebraic set that is explicitly characterized based on module theory and computer algebra. A finite open cover of P is obtained and for each basic open subset of the cover, a closed-form solution is computed using computer algebra. Hence, the local structure of the solution space can be finely studied. Finally, we show that the existence of a single closed-form solution defined on the whole parameter space P is related to difficult problems in module theory.

7.5.2 On a rank factorisation problem arising in gearbox vibration analysis

Given a field $K$, r matrices $D_i\in K^{n\times n}$, a matrix $M\in K^{n\times m}$ of rank at most $r$, in 29, we study the problem of factoring $M$ as follows $M={\sum }_{i=}^r{D}_u*u*v_i$, where $u\in K^{n\times 1}$ and $v_i\in K^{1\times m}$, for $i=1..r$. This problem arises in modulation-based mechanical models studied in gearbox vibration analysis (e.g., amplitude and phase modulation). We show how linear algebra methods combined with linear system theory ideas can be used to characterize when this polynomial problem is solvable and if so, how to explicitly compute the solutions.

7.6.1 Computation of the L-Infinity norm of finite-dimensional linear systems

In 26, we study the computation of the ${ℒ}_{\infty }$-norm for finite-dimensional linear systems. This problem is first reduced to the computation of the maximal $x$-projection of the real solutions $(x,y)$ of a bivariate polynomial system $\{𝒫,\frac{\partial 𝒫}{\partial y}\}\subset \mathbb{Z}[x,y]$. We then apply computer algebra methods to solve the problem. We alternatively study a method based on rational univariate representations, a method based on root separation and finally a method based on the sign variation of the leading coefficients of the signed subresultant sequence and on the identification of an isolating interval for the maximal $x$-projection of the real solutions of the system.

7.6.2 On the effective computation of stabilizing controllers of 2D systems

In 32, we show how stabilizing controllers for 2D systems can effectively be computed based on computer algebra methods dedicated to polynomial systems, module theory and homological algebra. The complete chain of algorithms for the computation of stabilizing controllers, implemented in Maple, is illustrated with an explicit example.

7.6.3 Symbolic Methods for Solving Algebraic Systems of Equations and Applications for Testing the Structural Stability

In 33, we provide an overview of the classical symbolic techniques for solving algebraic systems of equations and show the interest of such techniques in the study of some problems in dynamical system theory, namely testing the structural stability of multidimensional systems.

7.7.1 TRPLP – Trifocal Relative Pose From Lines at Points

In 27, we present a method for solving two minimal problems for relative camera pose estimation from three views, which are based on three view correspondences of (i) three points and one line and (ii) three points and two lines through two of the points. These problems are too difficult to be efficiently solved by the state of the art Grobner basis methods. Our method is based on a new efficient homotopy continuation (HC) solver, which dramatically speeds up previous HC solving by specializing HC methods to generic cases of our problems. We show in simulated experiments that our solvers are numerically robust and stable under image noise. We show in real experiment that (i) SIFT features provide good enough point-and-line correspondences for three-view reconstruction and (ii) that we can solve difficult cases with too few or too noisy tentative matches where the state of the art structure from motion initialization fails.

7.7.2 Using Maple to analyse parallel robots

in 34, we present the SIROPA Maple Library which has been designed to study serial and parallel manipulators at the conception level. We show how modern algorithms in Computer Algebra can be used to study the workspace, the joint space but also the existence of some physical capabilities w.r.t. to some design parameters left as degree of freedom for the designer of the robot.

9.1.1 Inria associate team not involved in an IIL

9.1.2 Inria international partners

9.2.1 FP7 & H2020 Projects

Program: H2020-EU.1.1. - EXCELLENT SCIENCE - European Research Council (ERC)

Project acronym: Almacrypt

Project title: Algorithmic and Mathematical Cryptology

Duration: 01/2016 - 06/2021

Coordinator: Antoine Joux

Abstract: Cryptology is a foundation of information security in the digital world. Today's internet is protected by a form of cryptography based on complexity theoretic hardness assumptions. Ideally, they should be strong to ensure security and versatile to offer a wide range of functionalities and allow efficient implementations. However, these assumptions are largely untested and internet security could be built on sand. The main ambition of Almacrypt is to remedy this issue by challenging the assumptions through an advanced algorithmic analysis. In particular, this proposal questions the two pillars of public-key encryption: factoring and discrete logarithms. Recently, the PI contributed to show that in some cases, the discrete logarithm problem is considerably weaker than previously assumed. A main objective is to ponder the security of other cases of the discrete logarithm problem, including elliptic curves, and of factoring. We will study the generalization of the recent techniques and search for new algorithmic options with comparable or better efficiency. We will also study hardness assumptions based on codes and subset-sum, two candidates for post-quantum cryptography. We will consider the applicability of recent algorithmic and mathematical techniques to the resolution of the corresponding putative hard problems, refine the analysis of the algorithms and design new algorithm tools. Cryptology is not limited to the above assumptions: other hard problems have been proposed to aim at post-quantum security and/or to offer extra functionalities. Should the security of these other assumptions become critical, they would be added to Almacrypt's scope. They could also serve to demonstrate other applications of our algorithmic progress. In addition to its scientific goal, Almacrypt also aims at seeding a strengthened research community dedicated to algorithmic and mathematical cryptology.

9.3.1 ANR

• ANR JCJC GALOP (Games through the lens of ALgebra and OPptimization)

  Coordinator: Elias Tsigaridas

  Duration: 2018 – 2022

  GALOP is a Young Researchers (JCJC) project with the purpose of extending the limits of the state- of-the-art algebraic tools in computer science, especially in stochastic games. It brings original and innovative algebraic tools, based on symbolic-numeric computing, that exploit the geometry and the structure and complement the state-of-the-art. We support our theoretical tools with a highly efficient open-source software for solving polynomials. Using our algebraic tools we study the geometry of the central curve of (semi-definite) optimization problems. The algebraic tools and our results from the geometry of optimization pave the way to introduce algorithms and precise bounds for stochastic games.

Chair of conference program committees

Jean-Claude Bajard was co-chair of the 8th International Workshop, WAIFI 2020, Rennes, France, July 6-8, 2020

Member of the conference program committees

Alban Quadrat was member of the Program Committee of the 2020 Maple Conference, 02-06/11/2020

Elias Tsigaridas was a member of the program committee of the 21th International Workshop on Computer Algebra in Scientific Computing (CASC) 2020.

10.1.1 Journal

10.1.2 Leadership within the scientific community

Alban Quadrat co-organized the invited session Algebraic and Symbolic Methods in Mathematical Systems Theory at the 21st IFAC World Congress, 13-17 July 2020

10.1.3 Scientific expertise

Alban Quadrat is member of the Scientific committee of the Journées Nationales de Calcul Formel (JNCF)

10.1.4 Research administration

Alban Quadrat is member of the Conseil d'Administration of the Société Mathématique de France (SMF).

Fabrice Rouillier is a member of the scientific commitee of the Indo French Centre for Applied Mathematics.

Elisha Falbel is director of the École Doctorale Sciences Mathématiques de Paris Centre - ED 386.

Elias Tsigaridas is an elected member of the Commission d’évaluation d’Inria (CE).

10.2.1 Teaching

Alban Quadrat, Project Démodulation (2 groups), 10, L3, Sorbonne University.

Fabrice Rouillier: Course in Algebraic Computations, M1, 24h, Sorbonne Université.

Antonin Guilloux: Courses L1 at Sorbonne Université; Courses and organization of the "Préparation à l'Option C de mathématiques", at Sorbonne Université

Pascal Molin collaborates to the funded (20K euros) project AATEM for implementing a Jupyter+Cocalc server for teaching Maths and coputer science à Paris University.

Pierre-Vincent Koseleff did propose anew course in Master 1 at Sorbonne Université : Algèbre Algorithmique

10.2.2 Supervision

Alban Quadrat supervised the Master thesis of Valérian Hatey, Etude effective de l'algèbre des opérateurs intégro-différentiels ordinaires à coefficients polynomiaux, M2 Algèbre Appliquée, University of Paris Saclay

Pierre-Vincent Koseleff supervised the Master thesis of Andrea Negro, some properties of the Alexander polynomials of two-bridge knots, M2 Mathématiques fondamentales, Sorbonne Université

• PhD in progress: Mahya Mehrabdollahei, 09/2018, directed by Antonin Guilloux and Fabrice Rouillier
• PhD in progress: Grace Younes, 09/2018, directed by Alban Quadrat and Fabrice Rouillier
• PhD in progress: Christina Katsamaki, 09/2019, directed by Elias Tsigaridas and Fabrice Rouillier
• PhD in progress: Raphael Alexandre, 09/2019, directed by Elisha Falbel.
• PhD in progress : Thibauld Feneuil, 10/2020, directed by Jean-Claude Bajard.
• PhD in progress : Carles Checa, 10/2020, directed by Elias Tsigaridas (co-supervision with Ioannis Emiris)
• Sudarshan Shinde, defense in July 2020 was directed by Razvan Barbulescu and Pierre-Vincent Koseleff

10.2.3 Juries

J.-C. Bajard was reviewer for the PhD of Mohamad Ali Mehrabi on hardware implementation of Elliptic Curve Cryptography based on Residue Number Systems , Macquarie University, Australia

J.-C. Bajard was president of the Jury for the PhD of Timo ZIJLSTRA on accélérateurs matériels sécurisés pour la cryptographie post- quantique, Université de Bretagne Sud.

J.-C. Bajard was was member of the jury for the PhD of Natalia Kharchenko on lattice algorithms and lattice-based cryptography , Sorbonne University.

10.3.1 Internal or external Inria responsibilities

Alban Quadrat is member of the technical committee Linear Systems of the International Federation of Automatic Control (IFAC)

Fabrice Rouillier is the President of the association Animath.

Fabrice Rouillier is Chargé de mission Médiation for the Inria Paris research center.

Fabrice Rouillier is in the editoria board of Interstices.

Fabrice Rouillier is a member of the comité de pilotage de l'année des matématiques

Fabrice Rouillier is a member of the comité de pilotage de la semaine des mathématiques

Fabrice Rouillier est membre du Jury des Olympiades Nationales de Mathématiques

10.3.2 Interventions

Fabrice Rouillier participated to the semaine des mathématiques for the Paris Inria Paris research center.

International journals

• 15 article J. Alcázar, J. Caravantes, G. Diaz-Toca and E. Tsigaridas. Computing the topology of a plane or space hyperelliptic curve Computer Aided Geometric Design February 2020
  HAL DOI back to text
• 16 articleR. Barbulescu and J. Ray. Numerical verification of the Cohen-Lenstra-Martinet heuristics and of Greenberg's p-rationality conjectureJournal de Théorie des Nombres de Bordeaux3212020, 159-177
  HALback to text
• 17 articleE. Brugallé, P.-V. Koseleff and D. Pecker. The lexicographic degree of the first two-bridge knotsAnnales de la Faculté des Sciences de Toulouse. Mathématiques.294December 2020, https://afst.centre-mersenne.org/item/AFST_2020_6_29_4_761_0/
  HALback to textback to text
• 18 article P. Bürgisser, F. Cucker and J. Tonelli-Cueto. Computing the Homology of Semialgebraic Sets. II: General formulas Foundations of Computational Mathematics January 2021
  HAL DOI back to text
• 19 articleL. Busé, A. Mantzaflaris and E. Tsigaridas. Matrix formulae for Resultants and Discriminants of Bivariate Tensor-product PolynomialsJournal of Symbolic Computation98June 2020, 65-83
  HALDOIback to text
• 20 article T. Chalkis, V. Fisikopoulos, P. Repouskos and E. Tsigaridas. Sampling the feasible sets of SDPs and volume approximation ACM Communications in Computer Algebra 2021
  HAL back to text
• 21 articleI. Emiris, A. Mantzaflaris and E. Tsigaridas. Multilinear Polynomial Systems: Root Isolation and Bit ComplexityJournal of Symbolic Computation1052021, 145-164
  HALDOIback to text
• 22 articleI. Emiris, B. Mourrain and E. Tsigaridas. Separation bounds for polynomial systemsJournal of Symbolic Computation1012020, 128-151
  HALDOIback to text
• 23 articleT. Espitau and A. Joux. Certified lattice reductionAdvances in Mathematics of Communications141February 2020, 137-159
  HALDOIback to text
• 24 articleC. Katsamaki, F. Rouillier, E. Tsigaridas and Z. Zafeirakopoulos. PTOPO: A Maple package for the topology of parametric curvesACM Communications in Computer Algebra542September 2020, 49-52
  HALDOIback to text

National journals

Invited conferences

International peer-reviewed conferences

• 25 inproceedings J.-C. Bajard, J. Eynard, P. Martins, L. Sousa and V. Zucca. An asymptotically faster version of FV supported on HPR ARITH-2020 - 27th IEEE International Symposium on Computer Arithmetic Portland, United States http://arith2020.arithsymposium.org/programme.html June 2020
  HAL back to text
• 26 inproceedings Y. Bouzidi, A. Quadrat, F. Rouillier and G. Younes. Computation of the $\mathcal{L}_{\infty}$-norm of finite-dimensional linear systems Maple Conference Waterloo, Canada November 2020
  HAL back to text
• 27 inproceedingsR. Fabbri, T. Duff, H. Fan, M. Regan, D. da Costa de Pinho, E. Tsigaridas, C. Wampler, J. Hauenstein, P. Giblin, B. Kimia, A. Leykin and T. Pajdla. TRPLP – Trifocal Relative Pose From Lines at PointsCVPR 2020 - IEEE/CVF Conference on Computer Vision and Pattern RecognitionSeattle / Virtual, United StatesJune 2020, 12070-12080
  HALDOIback to text
• 28 inproceedings E. Hubert, A. Barrau, Y. Bouzidi, R. Dagher and A. Quadrat. Algebraic aspects of a rank factorization problem arising in vibration analysis Maple Conference Waterloo / Virtual, Canada November 2020
  HAL back to text
• 29 inproceedings E. Hubert, A. Barrau, Y. Bouzidi, R. Dagher and A. Quadrat. On a rank factorisation problem arising in gearbox vibration analysis IFAC 2020 - 21st World Congress Berlin / Virtual, Germany https://www.ifac-control.org/events/ifac-world-congress-21th-wc-2020 July 2020
  HAL back to text
• 30 inproceedingsJ. Tonelli-Cueto and E. Tsigaridas. Condition Numbers for the Cube. I: Univariate Polynomials and HypersurfacesProceedings of the 2020 International Symposium on Symbolic and Algebraic Computation, ISSAC'20Kalamata, Greecehttp://www.issac-conference.org/2020/July 2020, 434-441
  HALDOIback to text

National peer-reviewed Conferences

Conferences without proceedings

• 31 inproceedings C. Katsamaki, F. Rouillier, E. Tsigaridas and Z. Zafeirakopoulos. On the Geometry and the Topology of Parametric Curves ISSAC 2020 - International Symposium on Symbolic and Algebraic Computation Kalamata / Virtual, Greece July 2020
  HAL back to text

Scientific books

Scientific book chapters

• 32 inbookY. Bouzidi, T. Cluzeau, A. Quadrat and F. Rouillier. On the effective computation of stabilizing controllers of 2D systemsMaple in Mathematics Education and ResearchMaple in Mathematics Education and Researchhttps://link.springer.com/book/10.1007/978-3-030-41258-6#toc2020, 30-49
  HALback to text
• 33 inbookY. Bouzidi and F. Rouillier. Symbolic Methods for Solving Algebraic Systems of Equations and Applications for Testing the Structural StabilityAlgebraic and Symbolic Computation Methods in Dynamical SystemsMay 2020, 203-237
  HALDOIback to text
• 34 inbookD. Chablat, G. Moroz, F. Rouillier and P. Wenger. Using Maple to analyse parallel robotsMaple in Mathematics Education and ResearchMaple in Mathematics Education and ResearchFebruary 2020, 50-64
  HALDOIback to text
• 35 inbookT. Cluzeau, C. Koutschan, A. Quadrat and M. Tõnso. Effective algebraic analysis approach to linear systems over Ore algebras9Algebraic and Symbolic Computation Methods in Dynamical SystemsAdvances in Delays and Dynamicshttps://www.springer.com/gp/book/97830303835582020, 4-52
  HALback to text
• 36 inbookT. Cluzeau and A. Quadrat. Equivalences of linear functional systems9Algebraic Methods and Symbolic-Numeric Computation in Systems Theoryhttps://www.springer.com/gp/book/97830303835582020, 53-86
  HALback to text
• 37 inbook A. Quadrat and G. Regensburger. Computing polynomial solutions and annihilators of integro-differential operators with polynomial coefficients 9 Algebraic and Symbolic Computation Methods in Dynamical Systems Advances in Delays and Dynamics 87-114 https://www.springer.com/gp/book/9783030383558#aboutBook 2020
  HAL back to text

Edition (books, proceedings, special issue of a journal)

• 38 bookA. Quadrat and E. Zerz. Algebraic and Symbolic Computation Methods in Dynamical Systems9Advances in Delays and Dynamics2020, 311
  HALDOIback to text

Doctoral dissertations and habilitation theses

• 39 thesis S. Shinde. Cryptographic applications of modular curves Sorbonne Université July 2020
  HAL back to text

Reports & preprints

• 40 misc R. Alexandre. Geodesic convexity and closed nilpotent similarity manifolds March 2020
  HAL
• 41 misc R. Alexandre. Redundancy of hyperbolic triangle groups in spherical CR representations June 2020
  HAL
• 42 misc J.-C. Bajard and S. Duquesne. Montgomery-friendly primes and applications to cryptography June 2020
  HAL
• 43 misc R. Barbulescu and S. Shinde. A classification of ECM-friendly families using modular curves: intégré à la thèse de doctorat de Sudarshan Shinde, Sorbonne Université, 10 juillet 2020. July 2020
  HAL
• 44 misc A. Chalkis, I. Emiris, V. Fisikopoulos, P. Repouskos and E. Tsigaridas. Efficient Sampling from Feasible Sets of SDPs and Volume Approximation October 2020
  HAL
• 45 misc A. Chalkis, V. Fisikopoulos, E. Tsigaridas and H. Zafeiropoulos. Geometric algorithms for sampling the flux space of metabolic networks December 2020
  HAL
• 46 misc C. Chenavier, T. Cluzeau and A. Quadrat. Presenting isomorphic finitely presented modules by equivalent matrices: a constructive approach March 2020
  HAL
• 47 misc F. Cucker, A. Ergür and J. Tonelli-Cueto. Functional norms, condition numbers and numerical algorithms in algebraic geometry February 2021
  HAL
• 48 misc F. Cucker, A. Ergür and J. Tonelli-Cueto. On the Complexity of the Plantinga-Vegter Algorithm December 2020
  HAL
• 49 misc C. Katsamaki, F. Rouillier, E. Tsigaridas and Z. Zafeirakopoulos. PTOPO: Computing the Geometry and the Topology of Parametric Curves December 2020
  HAL
• 50 misc J. Tonelli-Cueto and E. Tsigaridas. Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces December 2020
  HAL

Other scientific publications

Scientific popularization

Educational activities

Patents

Softwares

Cited publications

• 51 inproceedingsD. Aggarwal, A. Joux, A. Prakash and M. Santha. A New Public-Key Cryptosystem via Mersenne NumbersAdvances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III2018, 459--482URL: https://doi.org/10.1007/978-3-319-96878-0_16
  DOIback to text
• 52 book S. Basu, R. Pollack and M.-F. Roy. Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics) Berlin, Heidelberg Springer-Verlag 2006
  back to text
• 53 articleV. Bavula. The algebra of integro-differential operators on an affine line and its modulesJ. Pure Appl. Algebra2172013, 495--529
  back to text
• 54 article N. Bergeron, E. Falbel and A. Guilloux. Tetrahedra of flags, volume and homology of SL(3) Geometry & Topology Monographs 18 2014
  HAL DOI back to text
• 55 inproceedingsJ.-F. Biasse, T. Espitau, P.-A. Fouque, A. Gélin and P. Kirchner. Computing generator in cyclotomic integer rings36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2017)10210Lecture Notes in Computer ScienceParis, FranceApril 2017, 60-88
  HALDOIback to text
• 56 book A. Borel. Algebraic D-modules Perspectives in mathematics Academic Press 1987
  back to text back to text back to text
• 57 book N. Bose. Multidimensional Systems Theory: Progress, Directions and Open Problems in Multidimensional Systems Mathematics and Its Applications Springer Netherlands 2001
  back to text back to text back to text
• 58 articleF. Boulier, D. Lazard, F. Ollivier and M. Petitot. Computing representations for radicals of finitely generated differential idealsApplicable Algebra in Engineering, Communication and Computing202009, 73--121
  back to textback to text
• 59 inproceedingsY. Bouzidi, T. Cluzeau, G. Moroz and A. Quadrat. Computing effectively stabilizing controllers for a class of $n$D systemsThe 20th World Congress of the International Federation of Automatic Control501Toulouse, FranceJuly 2017, 1847 -- 1852
  HALDOIback to text
• 60 inproceedings Y. Bouzidi, S. Lazard, G. Moroz, M. Pouget and F. Rouillier. Improved algorithm for computing separating linear forms for bivariate systems ISSAC - 39th International Symposium on Symbolic and Algebraic Computation Kobe, Japan July 2014
  HAL back to text back to text
• 61 articleY. Bouzidi, S. Lazard, G. Moroz, M. Pouget, F. Rouillier and M. Sagraloff. Solving bivariate systems using Rational Univariate RepresentationsJournal of Complexity372016, 34--75
  HALDOIback to textback to textback to text
• 62 articleY. Bouzidi, S. Lazard, M. Pouget and F. Rouillier. Separating linear forms and Rational Univariate Representations of bivariate systemsJournal of Symbolic Computation680May 2015, 84-119
  HALDOIback to textback to text
• 63 incollection Y. Bouzidi, A. Poteaux and A. Quadrat. A symbolic computation approach to the asymptotic stability analysis of differential systems with commensurate delays Delays and Interconnections: Methodology, Algorithms and Applications Advances on Delays and Dynamics at Springer Springer Verlag March 2017
  HAL back to text
• 64 unpublishedY. Bouzidi, A. Quadrat and F. Rouillier. Certified Non-conservative Tests for the Structural Stability of Multidimensional SystemsAugust 2017, To appear in Multidimensional Systems and Signal Processing, https://link.springer.com/article/10.1007/s11045-018-0596-y
  HALback to textback to text
• 65 inproceedings Y. Bouzidi, A. Quadrat and F. Rouillier. Computer algebra methods for testing the structural stability of multidimensional systems IEEE 9th International Workshop on Multidimensional (nD) Systems (IEEE nDS 2015) Proceedings of the IEEE 9th International Workshop on Multidimensional (nD) Systems (IEEE nDS 2015) Vila Real, Portugal September 2015
  HAL back to text
• 66 inproceedings Y. Bouzidi and F. Rouillier. Certified Algorithms for proving the structural stability of two dimensional systems possibly with parameters MNTS 2016 - 22nd International Symposium on Mathematical Theory of Networks and Systems Proceedings of the 22nd International Symposium on Mathematical Theory of Networks and Systems Minneapolis, United States July 2016
  HAL back to text back to text
• 67 article E. Brugallé, P.-V. Koseleff and D. Pecker. On the lexicographic degree of two-bridge knots Journal Of Knot Theory And Its Ramifications (JKTR) 25 7 14p., 21 figs June 2016
  HAL DOI back to text
• 68 article E. Brugallé, P.-V. Koseleff and D. Pecker. Untangling trigonal diagrams Journal Of Knot Theory And Its Ramifications (JKTR) 25 7 10p., 24 figs June 2016
  HAL DOI back to text
• 69 inproceedingsD. Chablat, R. Jha, F. Rouillier and G. Moroz. Non-singular assembly mode changing trajectories in the workspace for the 3-RPS parallel robot14th International Symposium on Advances in Robot KinematicsLjubljana, SloveniaJune 2014, 149 -- 159
  HALback to text
• 70 inproceedingsD. Chablat, R. Jha, F. Rouillier and G. Moroz. Workspace and joint space analysis of the 3-RPS parallel robotASME 2013 International Design Engineering Technical Conferences & Computers and Information in Engineering ConferenceVolume 5ABuffalo, United StatesAugust 2014, 1-10
  HALback to text
• 71 articleF. Chyzak, A. Quadrat and D. Robertz. Effective algorithms for parametrizing linear control systems over Ore algebrasApplicable Algebra in Engineering, Communications and Computing162005, 319--376
  back to text
• 72 articleF. Chyzak and B. Salvy. Non-commutative elimination in Ore algebras proves multivariate identitiesJournal of Symbolic Computation2621998, 187--227
  back to textback to text
• 73 inproceedingsG. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decompostionAutomata Theory and Formal Languages 2nd GI Conference Kaiserslautern, May 20--23, 1975Berlin, HeidelbergSpringer Berlin Heidelberg1975, 134--183
  back to text
• 74 book D. Cox, J. Little and D. O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3/e (Undergraduate Texts in Mathematics) Berlin, Heidelberg Springer-Verlag 2007
  back to text
• 75 articleM. Crocco, A. Del Bue and V. Murino. A bilinear approach to the position self-calibration of multiple sensorsIEEE Transactions on Signal Processing6022012, 660--673
  back to text
• 76 book R. Curtain and H. Zwart. An Introduction to Infinite-Dimensional Linear Systems Theory Texts in Applied Mathematics Springer New York 2012
  back to text
• 77 article R. Dagher, A. Quadrat and G. Zheng. Algebraic solutions to the metric multidimensional unfolding. Application to the position self-calibration problem in preparation 2019
  back to text
• 78 article R. Dagher, A. Quadrat and G. Zheng. Auto-localisation par mesure de distances Pattern n. FR1853553 2018
  back to text
• 79 articleM. Deraux and E. Falbel. Complex hyperbolic geometry of the figure eight knotGeometry and Topology19February 2015, 237--293
  HALDOIback to text
• 80 unpublishedD. Diatta, S. Diatta, F. Rouillier, M.-F. Roy and M. Sagraloff. Bounds for polynomials on algebraic numbers and application to curve topologyOctober 2018, working paper or preprint
  HALback to textback to text
• 81 articleW. Diffie and M. Hellman. New directions in cryptographyIEEE Transactions on Information Theory2261976, 644-654
  back to text
• 82 articleS. Diop. Differential-algebraic decision methods and some applications to system theoryTheoret. Comput. Sci.981992, 137--161
  back to text
• 83 articleS. Diop. Elimination in control theoryMath. Control Signals Systems41991, 17--32
  back to text
• 84 articleJ. Doliskani, A. Narayanan and É. Schost. Drinfeld Modules with Complex Multiplication, Hasse Invariants and Factoring Polynomials over Finite FieldsCoRRabs/1712.006692017, URL: http://arxiv.org/abs/1712.00669
  back to text
• 85 articleT. Espitau and A. Joux. Adaptive precision LLL and Potential-LLL reductions with Interval arithmeticIACR Cryptology ePrint Archive20162016, 528URL: http://eprint.iacr.org/2016/528
  back to text
• 86 incollectionH. Evelyne. Notes on Triangular Sets and Triangulation-Decomposition Algorithms II: Differential SystemsSymbolic and Numerical Scientific ComputationLecture Notes in Computer Science 2630Springer2003, 40-87
  back to textback to text
• 87 article E. Falbel and A. Guilloux. Dimension of character varieties for 3-manifolds Proceedings of the American Mathematical Society 2016
  HAL DOI back to text
• 88 unpublishedE. Falbel, A. Guilloux and P. Will. Hilbert metric, beyond convexity2018, working paper or preprint
  HALback to text
• 89 articleE. Falbel, P.-V. Koseleff and F. Rouillier. Representations of fundamental groups of 3-manifolds into PGL(3,C): Exact computations in low complexityGeometriae Dedicata1771August 2015, 52
  HALDOIback to textback to text
• 90 unpublishedE. Falbel, M. Maculan and G. Sarfatti. Configurations of flags in orbits of real formsApril 2018, working paper or preprint
  HALback to text
• 91 articleE. Falbel and R. Santos Thebaldi. A Flag structure on a cusped hyperbolic 3-manifold with unipotent holonomyPacific Journal of Mathematics27812015, 51-78
  HALback to text
• 92 unpublishedE. Falbel and J. Veloso. Flag structures on real 3-manifoldsApril 2018, working paper or preprint
  HALback to text
• 93 articleJ. Faugère and D. Lazard. Combinatorial classes of parallel manipulatorsMechanism and Machine Theory3061995, 765 -- 776URL: http://www.sciencedirect.com/science/article/pii/0094114X9400069W
  DOIback to text
• 94 articleM. Fliess and H. Sira-Ramırez. An algebraic framework for linear identificationESAIM Control Optim. Calc. Variat.92003, 151–-168
  back to text
• 95 book J. Gathen and J. Gerhard. Modern Computer Algebra New York, NY, USA Cambridge University Press 2013
  back to text
• 96 inproceedingsA. Gélin and A. Joux. Reducing number field defining polynomials: an application to class group computationsAlgorithmic Number Theory Symposium XII19LMS Journal of Computation and MathematicsAKaiserslautern, GermanyAugust 2016, 315--331
  HALDOIback to textback to text
• 97 articleF. Göloğlu and A. Joux. A Simplified Approach to Rigorous Degree 2 Elimination in Discrete Logarithm AlgorithmsIACR Cryptology ePrint Archive20182018, 430URL: https://eprint.iacr.org/2018/430
  back to text
• 98 unpublishedA. Guilloux and I. Kim. Deformation space of discrete groups of SU(2,1) in quaternionic hyperbolic planeMarch 2018, working paper or preprint
  HALback to text
• 99 unpublishedA. Guilloux and J. Marché. Volume function and Mahler measure of exact polynomialsApril 2018, working paper or preprint
  HALback to text
• 100 article A. Guilloux. Volume of representations and birationality of peripheral holonomy Experimental Mathematics May 2017
  HAL back to text
• 101 unpublishedA. Guilloux and P. Will. On SL(3,C)-representations of the Whitehead link group2018, To appear in Geom. Ded
  HALback to textback to text
• 102 inproceedingsE. Hubert, A. Barrau and M. El Badaoui. New Multi-Carrier Demodulation Method Applied to Gearbox Vibration Analysis04 2018, 2141-2145
  DOIback to text
• 103 inproceedingsM. Husty and H.-P. Schröcker. Algebraic Geometry and KinematicsNonlinear Computational GeometryNew York, NYSpringer New York2010, 85--107
  back to text
• 104 book M. Janet. Leçons sur les systèmes d'équations aux dérivées partielles Gauthier-Villars 1929
  back to text back to text
• 105 articleR. Jha, D. Chablat, L. Baron, F. Rouillier and G. Moroz. Workspace, Joint space and Singularities of a family of Delta-Like RobotMechanism and Machine Theory127September 2018, 73-95
  HALDOIback to text
• 106 inproceedings R. Jha, D. Chablat, F. Rouillier and G. Moroz. An algebraic method to check the singularity-free paths for parallel robots International Design Engineering Technical Conferences & Computers and Information in Engineering Conference ASME Boston, United States August 2015
  HAL back to text
• 107 inproceedings R. Jha, D. Chablat, F. Rouillier and G. Moroz. Workspace and Singularity analysis of a Delta like family robot 4th IFTOMM International Symposium on Robotics and Mechatronics Poitiers, France June 2015
  HAL back to text
• 108 inproceedingsA. Joux and R. Lercier. The function field sieve is quite specialAlgorithmic Number Theory-ANTS V2369Lecture Notes in Computer ScienceSpringer2002, 431-445
  back to text
• 109 inproceedingsA. Joux and C. Pierrot. Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms - Simplified Setting for Small Characteristic Finite Fields20th International Conference on the Theory and Application of Cryptology and Information Security8873Lecture Notes in Computer ScienceKaoshiung, TaiwanSpringer Berlin HeidelbergDecember 2014, 378-397
  HALDOIback to textback to text
• 110 incollection A. Joux and C. Pierrot. Nearly Sparse Linear Algebra and application to Discrete Logarithms Computations Contemporary Developments in Finite Fields and Applications WorldScientific 2016
  HAL DOI back to text
• 111 book T. Kailath. Linear Systems Prentice-Hall 1980
  back to text
• 112 book M. Kashiwara. Algebraic study of systems of partial differential equations 63 Master’s thesis 1970 (English translation) Mémoires de la S. M. F. 1995
  back to text back to text back to text back to text
• 113 book M. Kashiwara, T. Kawai and T. Kimura. Foundations of Algebraic Analysis 37 Princeton University Press 1986
  back to text back to text back to text back to text
• 114 inproceedingsA. Kobel, F. Rouillier and M. Sagraloff. Computing Real Roots of Real Polynomials ... and now For Real! ISSAC '16 Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation ISSAC '16 Proceedings of the ACM on International Symposium on Symbolic and Algebraic ComputationWaterloo, CanadaJuly 2016, 7
  HALDOIback to textback to text
• 115 articleN. Koblitz. Elliptic curve cryptosystemsMathematics of Computation48177January 1987, 203--209
  back to text
• 116 book E. Kolchin. Differential Algebra & Algebraic Groups Pure and Applied Mathematics Elsevier Science 1973
  back to text
• 117 articleP.-V. Koseleff and D. Pecker. Chebyshev KnotsJournal of Knot Theory and Its Ramifications204April 2011, 575-593
  HALDOIback to text
• 118 articleP.-V. Koseleff and D. Pecker. Harmonic KnotsJournal Of Knot Theory And Its Ramifications (JKTR)251318 p., 30 fig.2016, 18
  HALDOIback to text
• 119 articleP.-V. Koseleff and D. Pecker. On Alexander--Conway polynomials of two-bridge linksJournal of Symbolic ComputationVolume 68215pMay 2015, 215-229
  HALDOIback to text
• 120 articleP.-V. Koseleff, D. Pecker and F. Rouillier. The first rational Chebyshev knotsJournal of Symbolic Computation4512December 2010, 1341-1358
  HALDOIback to text
• 121 articleP.-V. Koseleff, D. Pecker, F. Rouillier and C. Tran. Computing Chebyshev knot diagramsJournal of Symbolic Computation862018, 21
  HALDOIback to text
• 122 inproceedings P.-V. Koseleff, F. Rouillier and C. Tran. On the sign of a trigonometric expression ISSAC ' 15 Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation Bath, United Kingdom July 2015
  HAL DOI back to text
• 123 articleB. LaMacchia and A. Odlyzko. Computation of discrete logarithms in prime fieldsDesigns, Codes and Cryptography11991, 47--62
  back to text
• 124 articleS. Lazard, M. Pouget and F. Rouillier. Bivariate triangular decompositions in the presence of asymptotesJournal of Symbolic Computation822017, 123 -- 133
  HALDOIback to text
• 125 book A. Lenstra H. Lenstra The development of the number field sieve 1554 Lecture Notes in Mathematics Springer-Verlag 1993
  back to text
• 126 articleH. Lenstra~Jr.. Factoring integers with elliptic curvesAnnals of Mathematics12621987, 649--673
  back to text
• 127 inproceedingsB. Mourrain. The 40 Generic Positions of a Parallel RobotProceedings of the 1993 International Symposium on Symbolic and Algebraic ComputationISSAC '93New York, NY, USAKiev, UkraineACM1993, 173--182URL: http://doi.acm.org/10.1145/164081.164120
  DOIback to text
• 128 inproceedingsD. Niang Diatta, F. Rouillier and M.-F. Roy. On the computation of the topology of plane curvesInternational Symposium on Symbolic and Algebraic ComputationKobe UniversityKobe, JapanACM PressJuly 2014, 130-137
  HALDOIback to text
• 129 articleU. Oberst. Multidimensional constant linear systemsActa Appl. Math.201990, 1--175
  back to textback to text
• 130 incollectionC. Pomerance. Analysis and comparison of some integer factoring methodsComputational methods in number theory -- Part I154Mathematical centre tractsAmsterdamMathematisch Centrum1982, 8--139
  back to text
• 131 book Pommaret. Systems of Partial Differential Equations and Lie Pseudogroups Ellis Horwood Series in Mathematics and its Applications Gordon and Breach Science Publishers 1978
  back to text back to text
• 132 inproceedings A. Quadrat. A constructive algebraic analysis approach to Artstein's reduction of linear time-delay systems 12th IFAC Workshop on Time Delay Systems Proceedings of 12th IFAC Workshop on Time Delay Systems University of Michigan Ann Arbor, United States May 2016
  HAL back to text back to text back to text
• 133 articleA. Quadrat. Grade filtration of linear functional systemsActa Applicandė Mathematicė1271October 2013, 27--86
  HALDOIback to textback to text
• 134 inproceedingsA. Quadrat. Noncommutative geometric structures on stabilizable infinite-dimensional linear systemsECC 2014Strasbourg, FranceJune 2014, 2460 -- 2465
  HALDOIback to text
• 135 techreportA. Quadrat and G. Regensburger. Computing Polynomial Solutions and Annihilators of Integro-Differential Operators with Polynomial CoefficientsRR-9002Inria Lille - Nord Europe ; Institute for Algebra, Johannes Kepler University LinzDecember 2016, 24
  HALback to textback to text
• 136 articleA. Quadrat and D. Robertz. A constructive study of the module structure of rings of partial differential operatorsActa Applicandė Mathematicė1332014, 187--243
  HALDOIback to textback to text
• 137 inproceedings A. Quadrat. Towards an effective study of the algebraic parameter estimation problem IFAC 2017 Workshop Congress Toulouse, France July 2017
  HAL back to text back to text back to text
• 138 inproceedingsA. Quadrat and R. Ushirobira. Algebraic analysis for the Ore extension ring of differential time-varying delay operators 22nd International Symposium on Mathematical Theory of Networks and Systems (MTNS)Minneapolis, United StatesJuly 2016, 8
  HALback to text
• 139 inproceedingsG. Rance, Y. Bouzidi, A. Quadrat and A. Quadrat. A symbolic-numeric method for the parametric H$\infty$ loop-shaping design problem22nd International Symposium on Mathematical Theory of Networks and Systems (MTNS) Minneapolis, United StatesJuly 2016, 8
  HALback to text
• 140 inproceedings G. Rance, Y. Bouzidi, A. Quadrat and A. Quadrat. Explicit H$\infty$ controllers for 1st to 3rd order single-input single-output systems with parameters IFAC 2017 Workshop Congress Toulouse, France July 2017
  HAL back to text
• 141 inproceedings G. Rance, Y. Bouzidi, A. Quadrat, A. Quadrat and F. Rouillier. Explicit H$\infty$ controllers for 4th order single-input single-output systems with parameters and their applications to the two mass-spring system with damping IFAC 2017 Workshop Congress Toulouse, France July 2017
  HAL back to text back to text
• 142 phdthesis G. Rance. Parametric $H_{\infty}$ control and its application to gyrostabilized sights Université Paris-Saclay July 2018
  HAL back to text
• 143 book J. Ritt. Differential Algebra Colloquium publications American Mathematical Society 1950
  back to text
• 144 articleR. Rivest, A. Shamir and L. Adleman. A method for obtaining digital signatures and public-key cryptosystemsCommun. ACM2121978, 120--126
  back to text
• 145 book D. Robertz. Formal Algorithmic Elimination for PDEs Lecture Notes in Mathematics 2121 Springer 2014
  back to text
• 146 book J. Rotman. An Introduction to Homological Algebra Universitext Springer New York 2008
  back to text back to text
• 147 articleJ. Stafford. Module structure of Weyl algebrasJ. London Math. Soc.181978, 429--442
  back to text
• 148 inproceedingsV.~Miller. Use of elliptic curves in cryptographyAdvances in Cryptology --- CRYPTO'85218LNCSSpringer1986, 417--428
  back to text
• 149 incollectionV. Vassiliev. Cohomology of knot spacesTheory of singularities and its applications1Adv. Soviet Math.Amer. Math. Soc., Providence, RI1990, 23--69
  back to text
• 150 incollectionJ. Weeks. Chapter 10 - Computation of Hyperbolic Structures in Knot TheoryHandbook of Knot TheoryAmsterdamElsevier Science2005, 461 -- 480URL: http://www.sciencedirect.com/science/article/pii/B9780444514523500113
  DOIback to text
• 151 inproceedings P. Wenger. A new general formalism for the kinematic analysis of all nonredundant manipulators ICRA 1992
  back to text
• 152 book J. Willems and J. Polderman. Introduction to Mathematical Systems Theory: A Behavioral Approach Texts in Applied Mathematics Springer New York 2013
  back to text