Jeudi 16 novembre 2017 à 16h00 en salle C48
Sudarshan Shinde (UMPC)

Titre : Finding ECM-friendly curves - A Galois approach

Résumé :
The elliptic curve method (ECM) is a factorization algorithm widely used in cryptog- raphy. It was proposed in 1985 by Lenstra and improved a couple of months later by Montgomery using well-chosen curves. In order to compare different families of curves, he associated to each elliptic curve E and prime l, the mean valuation of l in the cardinality of E modulo random primes. More precisely, we set vl = E(vl(#(E(Fp)))) where the expectation is with respect to random primes p. Montgomery increased vl by forcing curves to have l-torsion points over Q. Brier and Clavier further increased v2 by imposing torsion points over Q(i). In 2012, Barbulescu et al (cf [1]) produced families of elliptic curves with better mean valuation without adding any torsion points on Q(i). Moreover, they showed that it is impossible to change vl without changing the degree of the l-torsion field, which has a generic value (cf [2]) in the sense in which the Galois group of an irreducible polynomial of degree n is generically Sn. In this talk we search families of elliptic curves with a larger valuation for l = 2 and l = 3 which boils down to searching families with non-generic Galois groups. Initially, we considered the method of Lagrange resolvant but this is not feasible for our polynomials of interest: the degree of division polynomials is quadratic in l. We then present two algorithms which produce a system of polynomial equations char- acterising every subfamily of elliptic curves having non-generic v3 and every subfamily of Montgomery curves having non-generic v2.