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 |
Name | size of the cofactor | date |
2, 529- | 101 | 31/07/93 |
10, 212+ | 141 | 14/02/00 |
[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.
[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.
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 |
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 |
[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.