François Morain

from Wikipedia, the free encyclopedia

François Morain is a French mathematician and computer scientist who specializes in algorithmic number theory , analysis of algorithms and cryptography .

Morain studied at the École polytechnique (graduation 1983) and received his doctorate in 1990 from the University of Lyon I ( Courbes elliptiques et tests de primalité ). In 1997 he completed his habilitation at the University of Paris VI ( Courbes elliptiques, arithmétique et corps finis ). He is at the Laboratory for Computer Science at the École polytechnique (LIX), where he heads the cross-university TANC project on algorithmic number theory. He is also an engineer at the French Ministry of Defense.

In 1988 he implemented the Atkin-Goldwasser-Kilian primality test algorithm using elliptic curves , which he improved with AOL Atkin . Later he also dealt with primality tests based on elliptic curves. He implemented the ECPP prime number test, which is improved compared to Goldwasser-Kilian and is based on an improvement of a test by AOL Atkin with elliptic curves with complex multiplication. He also implemented an even faster version by Jeffrey Shallit .

With Jeffrey Shallit and Hugh C. Williams, he discovered and reconstructed the number theoretic computer (which implemented a sieving process) exhibited by Eugène Carissan in Paris in 1920. Morain found the machine in good condition after a tip from the daughter of Carissan, who died in 1925, at the Bordeaux observatory. He was able to factor a 13-digit number in a test. It is now in the Conservatoire National du Arts et Metiers in Paris. Before that, Derrick Norman Lehmer and Derrick Henry Lehmer were the first to build such a number-theoretic special computer.

Fonts

  • With Jean-Louis Nicolas: Mathématiques / Informatique - 14problemèmes corrigés. Enseignement Supérieur et Informatique, Vuibert, 1995.

Web links

References

  1. ^ Atkin, Morain: Elliptic curves and primality proving. Math. Comp., Vol. 61, 1993, pp. 29-68. Morain also reports on this with R. Lercier in Eurocrypt 95, LN Computer Science Vol. 921, 1995
  2. ^ Elliptic Curve Primality Proving . Goldwasser-Kilian was based on the use of randomly chosen elliptical curves, the number of points of which had previously been tested for suitability according to the Schoof-Elkies-Atkin algorithm (SEA), which slowed the algorithm considerably. In the ECPP test, on the other hand, the number of points is known in advance. Morain: Elliptic curves for primality proving , in Henk van Tilborg (editor): Encyclopedia of cryptography and security. Springer 2005
  3. J. Shallit, HC Williams, F. Morain: Discovery of a lost factoring machine , Math. Intelligencer, Vol. 17, 1995, No. 3, pp. 41-47
  4. Ivars Peterson Cranking out primes: tracking down a long-lost factoring machine - Carissan's factoring machine - Cover Story ( Memento from July 8, 2012 in the web archive archive.today )