# Next seminar

Gilles Villard (AriC)

February 22th, 2018 at 10h15, room 116, Monod site

Computation of the resultant of two generic bivariate polynomials over a field

An algorithm is presented for computing the resultant of two generic bivariate polynomials over a field \(\mathbb{K}\).

For such \(p\) and \(q\) in \(\mathbb{K}[x,y]\) of degree \(d\) in \(x\) and \(n\) in \(y\), the algorithm computes the resultant with respect to \(y\) using \((n^{2 – 1/\omega} d) ^{1+o(1)}\) arithmetic operations in \(\mathbb{K}\), where two \(n\times n\) matrices are multiplied using \(O(n^{\omega})\) operations. Previous algorithms from the early 1970’s required time \((n^{2} d) ^{1+o(1)}\).

We also discuss some extensions of the approach to the computation of characteristic polynomials of generic structured matrices and in univariate quotient algebras.

# 2017-2018

Nick Trefethen (AriC and University of Oxford)

February 15th, 2018 at 10h15, room 116, Monod site

Minimax approximation of functions

My interest in minimax approimation started with my undergraduate thesis with Garrett Birkhoff at Harvard in 1977 and continues strong with the exciting new algorithm developed with Filip, Nakatsukasa, and Beckermann. This talk will collect observations about many aspects of this problem — both real and complex, polynomial and rational.

Koen de Boer (CWI, Amsterdam)

February 8th, 2018 at 10h15, room 116, Monod site

Attacks on the AJPS Mersenne-based Cryptosystem

Aggarwal, Joux, Prakash and Santha recently introduced a new potentially quantum-safe public-key cryptosystem, and suggested that a brute-force attack is essentially optimal against it. They consider but then dismiss both Meet-in-the-Middle attacks and LLL-based attacks. Very soon after their paper appeared, Beunardeau et al. proposed a practical LLL-based technique that seemed to significantly reduce the security of the AJPS system.

We do two things. First, we show that a Meet-in-the-Middle attack can also be made to work against the AJPS system, using locality-sensitive hashing to overcome the difficulty that Aggarwal et al. saw for such attacks. We also present a quantum version of this attack. Second, we give a more precise analysis of the attack of Beunardeau et al., confirming and refining their results.

Jean-Michel Muller (AriC team)

February 1st, 2018 at 10h15, room 116, Monod site

On the relative error of computing complex square roots in floating-point arithmetic

(joint work with Claude-Pierre Jeannerod)

We study the accuracy of a classical approach to computing complex square-roots in floating-point arithmetic.

Our analyses are done in binary floating-point arithmetic in precision \(p\), and we assume that the (real) arithmetic operations \(+\), \(-\), \(\times\), \(\div\), \(\sqrt{ }\) are rounded to nearest, so the unit roundoff is \(u = 2^{-p}\).

We show that in the absence of underflow and overflow, the componentwise and normwise relative errors of this approach are at most \(\frac{7}{2}u\) and \(\frac{\sqrt{37}}{2}u\), respectively, and this without having to neglect terms of higher order in \(u\). We then provide some input examples showing that these bounds are reasonably sharp for the three basic binary interchange formats (binary32, binary64, and binary128) of the IEEE 754 standard for floating-point arithmetic. Finally, we consider another, slightly more accurate algorithm.

Tanguy Rivoal (Institut Fourier, CNRS and Université Grenoble Alpes)

December 21, 2017 at 10h15, room 116, Monod site

Exceptional algebraic values of E-functions

E-functions are power series with algebraic Taylor coefficients at the origin (satisfying certain growth conditions) and solutions of linear differential equations with polynomial coefficients. Siegel defined them in 1929 to generalize the diophantine properties of the exponential function, which takes transcendental values at any non-zero algebraic point. The situation is more complicated in general, as an E-function may sometimes return an algebraic value when evaluated at a non-zero algebraic point. In this talk, I will first explain the classical Diophantine results for E-functions. I will then present an algorithm which, given an E-function \(F(z)\) as input, outputs the finite list of algebraic numbers \(A\) such that \(F(A)\) is algebraic.

This is a joint work with Boris Adamczewski (CNRS et Université Lyon 1).

Alexandre Wallet (AriC, LIP)

December 14, 2017 at 10h15, room 116, Monod site

On variants of Ring-LWE and Polynomial-LWE

Learning With Errors is a popular security assumption for post-quantum cryptographic schemes: informally, an integer solution of a “noisy” linear system must be found. It is based on hard problems on Euclidean lattices, and it allows for a lot of functionalities in cryptography. Structured variants based on algebraic number theory have been introduced to improve time and memory efficiency. However, the addition of new mathematical objects such as number fields/rings has led to several possible security assumptions, and the link between them is not always clear.

I will present recent results toward the clarification of the situation. For a large familyof number fields, we showed that all versions of the problem are equivalent (up to polynomial increases in the noise, and up to non-uniformity of some of the underlying reductions). Our reductions rely on mathematical tools, some of them being new in the Ring-based LWE context, such as perturbation techniques for polynomials.

Based on a joint work with Miruna Rosca and Damien Stehlé.

Warwick Tucker (Uppsala University and AriC, LIP)

November 23, 2017 at 10h15, room 116, Monod site

Validated numerics – part II

In this talk, we will cover the fundamentals of validated numerics, namely the inclusion principle and its consequences for mathematical proofs. In particular, we will talk about the set-valued Newton operator, and how it comes into play in many computer-assisted proofs. Again – the talk will be based upon concrete examples, and some small computer demo will illustrate the presented methods.

Nick Trefethen (AriC and University of Oxford)

Thursday November 16, 2017 at 10h15, room 116, Monod site

Numerical Computation with Rational Functions

I will begin with a review of rational functions in numerical computation, including a review of twelve applications where they are useful and of two famous problems of rational approximation theory. Then we find ourselves with an “inverse Yogiism”. Although it is mathematically correct that a rational function is a quotient \(r = p/q\) of two polynomials, representations of this form are numerically unstable in precisely the cases where rational functions should be most powerful. A better alternative is a barycentric representation \(r = n/d\) in which \(n\) and \(d\) are partial fraction sums, and this leads to the exciting new “AAA algorithm”, which we will explain and demonstrate. This is joint work with Silviu Filip, Yuji Nakatsukasa, and Olvier Séte.

Paola Boito, Elena Kirshanova, Benoît Libert, and Nathalie Revol (AriC, LIP)

Thursday November 9, 2017 at 10h15, room 116, Monod site

Back from Conferences

Short talks (10’ + 5’ for questions) when people are back from a conference, on talks they attended and found interesting. We will have, by alphabetical order :

- Paola Boito on «
*Solving large scale Lyapunov and Sylvester equations with quasiseparable coefficients*» by Stefano Massei at Structured Matrices in Numerical Linear Algebra;

Abstract: Let us consider a Sylvester matrix equation \(AX+XB=C\) where the coefficients \(A\), \(B\) and \(C\) are matrices with low-rank off-diagonal blocks. What can be said about the rank structure of the solution \(X\)? It turns out that, under suitable hypotheses, \(X\) inherits a rank structure as well. The main idea of the proof relies on a recent result by Beckermann and Townsend on displacement structured matrices. - Elena Kirshanova on «
*Grover Meets Simon – Quantumly Attacking the FX-construction*» by Gregor Leander and Alexander May,to be presented at AsiaCrypt’17; - Benoît Libert on «
*Asymptotically Compact Adaptively Secure Lattice IBEs and Verifiable Random Functions via Generalized Partitioning Techniques*» by Shota Yamada at IACR-CRYPTO-2017; - Nathalie Revol on «
*Utah Floating-Point Toolset*» by Zvonimir Rakamaric at Dagstuhl Seminar 17352 – Analysis and Synthesis of Floating-point Programs.

Rencontres “Arithmétique de l’Informatique Mathématique”

October 24-26, 2017

Monthly Lattice Meeting

October 19-20, 2017 in room 115, Monod site

Nick Trefethen (University of Oxford and AriC, LIP)

Thursday October 19, 2017 at 10h15, room 116, Monod site

Chebyshev Series

Chebyshev series are the basic tool for working with functions on a real interval — the equivalent of Fourier series but without the assumption of periodicity. They are also the basis of the software system Chebfun. We review the properties of Chebyshev series, using Chebfun to illustrate them, and then discuss the surprisingly challenging problem of “chopping a Chebyshev series” to obtain a representation to a prescribed precision, which is an analogue for functions of the floating-point rounding of real numbers.

We close with a few words about Faber’s theorem of 1914 and “inverse Yogiisms”.

Warwick Tucker (Uppsala University and AriC, LIP)

Thursday October 12, 2017 at 10h15, room 116, Monod site

Validated numerics – a brief overview

In this talk, I will give a short introduction to the field of validated numerics. We will take a top-down approach, and begin by studying some natural mathematical problems that arise in the study of dynamical systems. Such problems invariably lead to some numerical challenges, and we will see how they can be addressed in the framework of validated numerics. Everything will be explained from “first principles”, so no prior knowledge of dynamical systems is needed.

Vincent Lefèvre, Jean-Michel Muller, Bruno Salvy and Damien Stehlé (AriC, LIP)

Thursday September 28, 2017 at 10h15, room 116, Monod site

Back from Conferences

Short talks (10’ + 5’ for questions) when people are back from a conference, on talks they attended and found interesting. We will have, by alphabetical order :

- Vincent Lefèvre on «
*Multiple-precision floating-point arithmetic on SIMD processors*» by van der Hoeven at Arith; - Jean-Michel Muller on «
*The rise of multi precision computations*» by Higham at Arith; - Bruno Salvy on «
*A universal ordinary differential equation*» by Bournez & Pouly at FoCM; - Damien Stehlé on «
*Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time*» by Micciancio & Walter at Crypto.

# 2016-2017

Thomas Prest (Thales)

Thursday May 11, 2017 at 9h45 (please note the unusual time), room 116, Monod site

Easier floating-point on a Rényi day

This talk is part of the Monthly Lattice Meetings.

Paola Boito (XLIM, U. Limoges and AriC)

Thursday April 20, 2017 at 10h15, room 116, Monod site

Efficient Solution of Parameter Dependent Quasiseparable Systems

and Computation of Meromorphic Matrix Functions

In this work we focus on the solution of shifted quasiseparable systems and of more general parameter dependent matrix equations with quasiseparable representations. We propose an efficient algorithm exploiting the invariance of the quasiseparable structure under diagonal shifting and inversion. This algorithm is applied to compute various functions of matrices. Numerical experiments show the effectiveness of the approach.

This is joint work with Luca Gemignani (Pisa) and Yuli Eidelman (Tel Aviv).

Alin Bostan (Inria Saclay)

Thursday April 13, 2017 at 10h15, room 116, Monod site

Proving algorithmically the transcendence of D-finite power series

Given a sequence represented by a linear recurrence with polynomial coefficients and sufficiently many initial terms, a natural question is whether the transcendence of its generating function can be decided algorithmically. The question is non trivial even for sequences satisfying a recurrence of first order. An algorithm due to Michael Singer is sufficient, in principle, to answer the general case. However, this algorithm suffers from too high a complexity to be effective in practice. We will present a recent method that we have used to treat a non-trivial combinatorial example. It reduces the question of transcendence to a (structured) linear algebra problem.

Laurent Grémy (Loria)

Monday April 10, 2017 at 15h00, room 115, Monod site

Computing discrete logarithms: sieving for the number field sieve

Factoring large integers and computing discrete logarithms over finite fields are two difficult problems, efficiently solved by a family of algorithms, the index calculus. The security of some cryptosystems rely on this difficulty.

Since 1982 and the use of the quadratic sieve by Pomerance to factor large integers, it is well known that an important step of these algorithms, called relation collection, can be done quickly using sieving algorithms, basically like the sieve of Eratosthenes to find primes. Among the index calculus algorithms, the number field sieve (NFS) reaches the best complexity. It requires a two-dimensional sieving. In 2005, Franke and Kleinjung described the most efficient algorithm to sieve over two dimensions.

The diversity of finite fields implies that different variants of the NFS, as the one described by Joux–Lercier–Smart–Vercauteren in 2006 or by Kim–Barbulescu in 2016, need to sieve in higher dimensions, basically from 3 to 6. In this talk, we will describe three sieving algorithms in dimension three, some computational results of their implementations and finally an algorithm to sieve in any small dimension.

Jean-Michel Muller (AriC)

Thursday March 23, 2017 at 10h15, room 116, Monod site

Tight and rigorous error bounds for basic building blocks of double-word arithmetic

(Joint work with Mioara Joldes and Valentina Popescu)

We analyze several classical basic building blocks of double-word arithmetic (frequently called “double-double arithmetic” in the literature): the addition of a double-word number and a floating-point number, the addition of two double-word numbers, the multiplication of a double-word number by a floating-point number, the multiplication of two double-word numbers, the division of a double-word number by a floating-point number, and the division of two double-word numbers. For multiplication and division we get better relative error bounds than the ones previously published. For addition of two double-word numbers, we show that the previously published bound was incorrect, and we provide a new relative error bound. We introduce new algorithms for division. We also give examples that illustrate the tightness of our bounds.

George Labahn (U. Waterloo, Canada)

Friday February 3, 2017 at 10h15, room 116, Monod site

Sigma Bases, Kernel Bases and their use in fast computation for polynomial matrices

In this talk we discuss sigma bases and kernel bases of polynomial matrices and illustrate their role in fast algorithms for arithmetic with polynomial matrices. In particular we focus on the use of kernel bases for triangulation, computing determinants and Hermite normal form computation.

Joint work with Vincent Neiger (Lyon and TU Denmark) and Wei Zhou (Waterloo)

Marc Mezzarobba (CNRS, UPMC)

Thursday January 26, 2017 at 10h15, room 116, Monod site

Rigorous Multiple-Precision Evaluation of D-Finite Functions in SageMath

We present an implementation, on top of the SageMath computer algebra system, of a collection of tools for computing numerical values of D-finite functions. Recall that a complex analytic function is D-finite when it satisfies an ordinary differential equation whose coefficients are polynomial in the independent variable. D-finite functions can be viewed as a class of special functions analogous to those of algebraic or hypergeometric functions, but more general. They come up in areas such as analytic combinatorics and mathematical physics, and lend themselves well to symbolic manipulation by computer algebra systems.

The main task our package performs is the “numerical analytic continuation” of D-finite functions. This process results in a numerical approximation of the transition matrix that maps “initial values” of an ODE somewhere on the complex plane to “initial values” elsewhere that define the same solution. Numerical analytic continuation can then be used to compute things like values or polynomial approximations of D-finite functions anywhere on their Riemann surfaces, and monodromy matrices of differential operators. The code supports the important limit case where the (generalized) initial values are provided at regular singular points of the ODE, making it possible in particular to compute connection constants between regular singularities. It is rigorous in the sense that it returns interval results that are guaranteed to enclose the exact mathematical result.

The new package can be considered a successor of NumGfun, a Maple package by the same author with broadly similar features.

Brice Minaud (RHUL)

Thursday January 19, 2017 at 10h15, room 116, Monod site

Cryptanalysis of the CLT15 Multilinear Map over the Integers

Multilinear maps are a powerful cryptographic primitive: a wide array of cryptographic schemes can be built from multilinear maps, including some for which there is no other known construction, such as non-interactive multipartite key exchange, or general program obfuscation. However to this day there is no provable construction of multilinear maps. Moreover both of the original constructions (proposed in 2013 by Garg, Gentry, and Halevi, and by Coron, Lepoint, and Tibouchi) have been broken for their most direct application, namely non-interactive multipartite key exchange. This has led Coron, Lepoint and Tibouchi to introduce an improved variant of their original construction at Crypto 2015. We propose a polynomial attack on this new construction, which fully breaks the scheme. The presentation will of course begin with a general introduction to multilinear maps and the CLT construction, which aims to be accessible to all; and will conclude with a brief overview of the current state of the topic.

Anastasia Volkova (UPMC Paris 6, LIP6)

Thursday January 5, 2017 at 10h15, room 116, Monod site

Towards reliable implementation of digital filters

Linear digital filters are frequently used in digital signal processing. We are interested in implementation of such algorithms in Fixed-Point Arithmetic. However, on each step of an implementation various issues arise. We propose an automatised filter-to-code generator which encompasses the filter implementation flow and provides a consistent error-analysis of involved algorithms.

In this talk we make an overview of the filter-to-code generator and focus on determining the Fixed-Point formats for an implementation that is optimal with respect to a certain criteria. We consider Linear Time Invariant filters in state-space representation. The computational errors in the intermediate steps of the filter evaluation as well as their accumulation over time are fully taken into account. Our approach is fully rigorous in the way that the output Fixed-Point formats are shown to be free of overflows and that we do not use any (non-exhaustive) filter simulation steps but proofs.

Crypto and Lattices Days

Thursday December 15, 2016 at 10h15, room 116, Monod site

TBA

Cf. the Web page of the Crypto and Lattices Days

Crypto and Lattices Days

Thursday November 24, 2016 at 10h15, room 116, Monod site

TBA

Cf. the Web page of the Crypto and Lattices Days

Paola Boito (U. Limoges and LIP, AriC team)

Thursday October 6, 2016 at 10h15, room 116, Monod site

Quasiseparable structure and polynomial rootfinding

Computing the roots of a univariate polynomial is a classical task in computer algebra and numerical analysis and it is often solved via a companion matrix approach. But can we exploit the matrix structures that arise in this problem to devise fast eigensolvers and rootfinding algorithms, without losing accuracy?

Motivated by this problem, we

- review some useful rank structures of Frobenius and Chebyshev companion matrices and pencils,
- introduce the quasiseparable representation for such matrices and pencils,
- show how to adapt suitable versions of the Francis/Kublanovskaya QR algorithm to the quasi separable representation, so that the arithmetic complexity of each iteration is linear in the size of the matrix,
- comment on numerical results, applications, and perspectives for further work.

This is joint work with Luca Gemignani (University of Pisa) and Yuli Eidelman (University of Tel Aviv).

Serge Torres (LIP, AriC team)

Thursday September 22, 2016 2:30 PM, in lecture theater B, at the 3d floor of the GN1 building, Monod Campus.

PhD defense: Tools for the Design of Reliable and Efficient Function Evaluation Libraries

Can you tell me more about that?

The design of function evaluation libraries is a complex task that requires great care and dedication, especially when one wants to satisfy high standards of reliability and performance. In practice, it cannot be correctly performed, as a routine operation, without tools that not only help the designer to find his way in a complex and extended solution space but also guarantee that his solutions are correct and (possibly) optimal.

As of the present state of the art, one has to think in terms of “toolbox” from which he has to smartly mix-and-match the utensils that better fit his goals rather than expect to have at hand a solve-all automatic device.

What is it that you have done?

The work presented here is dedicated to the design and implementation of such specialized tools in two realms:

- the radical consolidation of Ziv’s rounding test that is used, in a more or less empirical way for ages, in the implementation of functions approximation;
- the development of an implementation of the SLZ-algorithm in order to “solve” (in a specific sense that will be made clear) the Table Maker Dilemma; the suitability of this implementation is also challenged for the development of correctly rounded approximations of functions with quad-precision floating-point (aka IEEE-754 Binary128 format) arguments and images.

About the defense, see the report on the intranet of ENS de Lyon.

Rémi Imbach (Inria Nancy – Grand Est, VEGAS Team)

Thursday September 15, 2016 at 10h15, room 116 (site Monod M1)

Certified numerical tools for computing the topology of projected curves

We are interested in computing the topology of the projection of an algebraic or analytic space curve in the plane. Such a projection is not a smooth curve and has singularities. State of the art approaches to compute the topology of algebraic plane curves use symbolic calculus but in the case of a projection, latter approaches suffer from the size of the implicit representation of the curve as a resultant polynomial.

Using numerical tools to compute the projected curve or its singularities is a challenging problem since the projected curve is not smooth, and state-of-the-art characterizations of the singularities use over-determined systems of equations. We will first propose a new characterization of the singularities of the projection of an algebraic curve using a square system polynomials; its solutions are regular and it can be solved numerically.

However its equations are coefficients of resultant polynomials and are still very large polynomials. The demand in arithmetic precision to carry out numerical calculus with such polynomials makes classical solvers either incomplete or dramatically time consuming. We will propose a multi-precision solver using interval subdivision specially designed to handle large polynomials to compute the solutions of this system. We will then consider the more general case of projections of analytic space curves, and propose a geometric approach to describe its singularities. It results in a square system of equations with only regular solutions, that do not involve resultant theory, and that can be solved with our certified numerical solver. Finally we will present a new approach to compute the topology of the projected curve, i.e. find a graph that has the same topology. We use a certified numerical path tracker to enclose the space curve in a sequence of boxes, allowing both to simplify the research of singularities and to compute smooth branches linking singularities.

# Archives of the seminar

For seminars in previous years, see former AriC seminars.