Abstract Let ℰ∕ 𝔽 q be an elliptic curve, and P a point in ℰ (𝔽 q) of prime order ℓ. Vélu's
formulæ let us compute a quotient curve ℰ′= ℰ∕⟨ P⟩ and rational maps defining a …

We present an algorithm that computes the product of two n-bit integers in O(nlog\,n) bit
operations, thus confirming a conjecture of Schönhage and Strassen from 1971. Our …

La popularité de la cryptographie à base de réseau euclidien a considérablement augmenté
ces dernières années avec la découverte de nouvelles fonctionnalités spectaculaires, telles …

We give a new algorithm for the multiplication of n-bit integers in the bit complexity model,
which is asymptotically faster than all previously known algorithms. More precisely, we prove …

Assuming a widely believed hypothesis concerning the least prime in an arithmetic
progression, we show that polynomials of degree less than over a finite field with elements …

At EUROCRYPT'10, van Dijk et al. presented simple fully-homomorphic encryption (FHE)
schemes based on the hardness of approximate integer common divisors problems, which …

Le calcul formel traite des objets mathématiques exacts d'un point de vue informatique. Cet
ouvrage «Algorithmes efficaces en calcul formel» explore deux directions: la calculabilité et …

Polynomials over finite fields play a central role in algorithms for cryptography, error
correcting codes, and computer algebra. The complexity of multiplying such polynomials is …

We present an efficient implementation of hypergeometric functions in arbitrary-precision
interval arithmetic. The functions 0 F 1, 1 F 1, 2 F 1, and 2 F 0 (or the Kummer U-function) are …

A univariate function is called D-finite if it satisfies a linear differential equation with
polynomial coefficients. The concept of D-finiteness applies more generally to sequences …