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.