Research at LIX

Note: a new page is being written, following more closely the french version.

Integer factorisation

There are basically two types of methods for factoring integers. The first one contains probabilistic algorithms, which find a prime factor of a given number with a running time that is difficult to analyse precisely. This is the case of Pollard's p-1 algorithm, or of Lenstra's ECM. The second class includes general-purpose algorithms, that can factor any number in a given time. The most efficient algorithms are the quadratic sieve and the number field sieve (see [LeLe93]). Here at LIX, we have factored several numbers of the RSA Partition Challenge (e.g. RSA-155) or of the Cunningham Project:

RSA Partition Challenge
Name original size size of the factor size of the cofactor date
p(16981) 141 18 90 14/12/92
p(21059) 157 19 89 26/12/92
p(16369) 138 24 78 09/01/93
p(19079) 149 27 95 20/01/93
p(18911) 149 15 95 01/03/93
p(14627) 130 37 - 09/03/93
p(18587) 147 29 - 20/03/93
p(12799) 122 32 - 24/03/93
p(17791) 144 29 94 28/04/93
p(19777) 152 22 100 24/09/93
p(22469) 162 34 86 02/03/94

Cunningham Project
Name size of the cofactor date
2, 529- 101 31/07/93
10, 212+ 141 14/02/00

(10,212+ was factored with a group of people under the direction of the H. te Riele from CWI.)

For more information

[AtGrLeLe94] Derek Atkins, Michael Graff, Arjen K. Lenstra, and Paul C. Leyland. The magic words are squeamish ossifrage. In Josef Pieprzyk and Reihanah Safavi-Naini, editors, Advances in Cryptology -- ASIACRYPT '94, volume 917 of Lecture Notes in Comput. Sci., pages 263--277. Springer-Verlag, 1995. 4th International Conference on the Theory and Applications of Cryptology, Wollongong, Australia, November/December 1994, Proceedings.

[LeLe93] A. K. Lenstra and H. W. Lenstra, Jr., editors. The development of the number field sieve, volume 1554 of Lecture Notes in Math. Springer, 1993.

[RSA155] S. Cavallar et al. Factorization of a 512-bit RSA modulus. Proc. EUROCRYPT 2000, LNCS.

Primality proving

Once again, there are two types of algorithms. The first one is really that of compositeness, that can give a proof that a number is definitely composite. Among these algorithms, we find the tests of Fermat, Solovay-Strassen, Dubois-Selfridge-Miller-Rabin, etc. The other class is that of the primality proving algorithms that give a proof that the number is prime or not. There are basically two algorithms in this class: the Jacobi sums test [CoLe84] and the ECPP test [AtMo93b].

For more information

[AtMo93b] A. O. L. Atkin and F. Morain. Elliptic curves and primality proving. Math. Comp., 61(203):29--68, July 1993.

[Morain98] F. Morain Primality proving using elliptic curves: an update Proc. ANTS-III, LNCS 1423, 1998.

[CoLe84] H. Cohen and H. W. Lenstra, Jr. Primality testing and Jacobi sums. Math. Comp., 42(165):297--330, 1984.

Elliptic curve computations

An elliptic curve is defined by an equation y^2 = x^3+a*x+b; we can put a group law on such an object, as exemplified in the above figure. The use of elliptic curves in computational number theory dates back 1985, when H. W. Lenstra, Jr. introduced his ECM for factoring integers [Lenstra87]. Numerous applications followed: primality proving [GoKi86], [AtMo93b]; cryptosystems (see for instance [Menezes93]).

In order to build cryptosystems over finite fields, it is necessary to compute the cardinality of such objects. There is an algorithm for doing this, due to Schoof [Schoof85], which does that in polynomial time. Numerous improvements were recently given. One can see part of them among F. Morain's article. LIX has the world record for this, as indicated in the following tables.

size Who When
65 Atkin 24/02/1991
75 Atkin 14/02/1992
100 Atkin 24/02/1992
120 Atkin 24/07/1992
130 Atkin 24/07/1992
150 Atkin 29/03/1992
200 Atkin 24/07/1992
225 Atkin ??/07/1993
250 FM 07/02/1994
276 Atkin 29/03/1994
350 RL-FM ??/04/1994
376 Müller ??/04/1994
400 RL-FM 03/10/1994
425 Müller ??/10/1994
500 RL-FM 27/01/1995
Cardinality of elliptic curves defined over F(p)

size Who When
300 RL-FM ??/09/94
400 RL-FM 28/09/94
500 RL-FM 18/10/94
601 RL-FM 27/12/94
701 RL-FM 10/03/95
1009 RL-FM 31/07/95
1301 RL-FM ??/04/96
1663 RL-Joux 19/06/98
1999 Vercauteren 17/10/99
3001 Fouquet-Gaudry-Harley 10/05/2000 Satoh-FGH
8009 Fouquet-Gaudry-Harley 05/10/2000 Satoh-FGH
16001 Harley ??/??/2001 AGM
32003 Harley 20/08/02 p-adique
Cardinality of elliptic curves defined over F(2^n)

Hyperelliptic curve computations

Curves of the form y^2 = f(x) = x^(2g+1) + ... of genus g are being studied by P. Gaudry.

For more information

[BlSeSm99] I. Blake and G. Seroussi and N. Smart Elliptic curves in cryptography. Cambridge University Press, 1999.

[GoKi86] S. Goldwasser and J. Kilian. Almost all primes can be quickly certified. In Proc. 18th STOC, pages 316--329. ACM, 1986. May 28--30, Berkeley.

[Lenstra87] Hendrik W. Lenstra, Jr. Factoring integers with elliptic curves. Annals of Math., 126:649--673, 1987.

[Menezes93] Alfred J. Menezes. Elliptic curve public key cryptosystems. Kluwer Academic Publishers, 1993.

[Schoof85] R. Schoof. Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp., 44:483--494, 1985.