Lagrange polynomial | EPFL Graph Search

In numerical analysis, the Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data. Given a data set of coordinate pairs (x_j, y_j) with 0 \leq j \leq k, the x_j are called nodes and the y_j are called values. The Lagrange polynomial L(x) has degree \leq k and assumes each value at the corresponding node, L(x_j) = y_j. Although named after Joseph-Louis Lagrange, who published it in 1795, the method was first discovered in 1779 by Edward Waring. It is also an easy consequence of a formula published in 1783 by Leonhard Euler. Uses of Lagrange polynomials include the Newton–Cotes method of numerical integration, Shamir's secret sharing scheme in cryptography, and Reed–Solomon error correction in coding theory. For equispaced nodes, Lagrange interpolation is susceptible to Runge's phenomenon of large oscillation. Defi

Geometrical reconstruction of curves and surfaces using NURBS

Sylvain Rouge

The aim of this project is the analysis of different approaches for curve and surface reconstruction and the development of a related MATLAB library. We initially study the Lagrange polynomial interpolation, then the Bezier, the B-splines and the NURBS curves and finally we introduce the NURBS surfaces. At each step we list the useful properties of the different approaches, the details of the mathematical representation and the evolution from simpler to more complicated representations.

2008

Arithmetic and metric aspects of open de Rham spaces

Tamás Hausel, Michael Lennox Wong, Dimitri Stelio Wyss

In this paper we determine the motivic class---in particular, the weight polynomial and conjecturally the Poincar'e polynomial---of the open de Rham space, defined and studied by Boalch, of certain moduli of irregular meromorphic connections on the trivial bundle on

\mathbb{P}^1

. The computation is by motivic Fourier transform. We show that the result satisfies the purity conjecture, that is, it agrees with the pure part of the conjectured mixed Hodge polynomial of the corresponding wild character variety. We also identify the open de Rham spaces with quiver varieties with multiplicities of Yamakawa and Geiss--Leclerc--Schr"oer. We finish with constructing natural complete hyperk"ahler metrics on them, which in the

4

-dimensional cases are expected to be of type ALF.

2018

Attacks on some post-quantum cryptographic protocols: The case of the Legendre PRF and SIKE

Novak Kaluderovic

Post-quantum cryptography is a branch of cryptography which deals with cryptographic algorithms whose hardness assumptions are not based on problems known to be solvable by a quantum computer, such as the RSA problem, factoring or discrete logarithms.This thesis treats two such algorithms and provides theoretical and practical attacks against them.The first protocol is the generalised Legendre pseudorandom function - a random bit generator computed as the Legendre symbol of the evaluation of a secret polynomial at an element of a finite field. We introduce a new point of view on the protocol by analysing the action of the group of Möbius transformations on the set of secret keys (secret polynomials).We provide a key extraction attack by creating a table which is cubic in the number of the function queries, an improvement over the previous algorithms which only provided a quadratic yield. Furthermore we provide an ever stronger attack for a new set of particularly weak keys.The second protocol that we cover is SIKE - supersingular isogeny key encapsulation.In 2017 the American National Institute of Standards and Technology (NIST) opened a call for standardisation of post-quantum cryptographic algorithms. One of the candidates, currently listed as an alternative key encapsulation candidate in the third round of the standardisation process, is SIKE.We provide three practical side-channel attacks on the 32-bit ARM Cortex-M4 implementation of SIKE.The first attack targets the elliptic curve scalar multiplication, implemented as a three-point ladder in SIKE. The lack of coordinate randomisation is observed, and used to attack the ladder by means of a differential power analysis algorithm.This allows us to extract the full secret key of the target party with only one power trace.The second attack assumes coordinate randomisation is implemented and provides a zero-value attack - the target party is forced to compute the field element zero, which cannot be protected by randomisation. In particular we target both the three-point ladder and isogeny computation in two separate attacks by providing maliciously generated public keys made of elliptic curve points of irregular order.We show that an order-checking countermeasure is effective, but comes at a price of 10% computational overhead. Furthermore we show how to modify the implementation so that it can be protected from all zero-value attacks, i.e., a zero-value is never computed during the execution of the algorithm.Finally, the last attack targets a point swapping procedure which is a subroutine of the three-point ladder. The attack successfully extracts the full secret key with only one power trace even if the implementation is protected with coordinate randomisation or order-checking. We provide an effective countermeasure --- an improved point swapping algorithm which protects the implementation from our attack.

EPFL2022