François Morain

François Morain ist ein französischer Mathematiker und Informatiker, der sich mit Algorithmischer Zahlentheorie, Analyse von Algorithmen und Kryptographie beschäftigt.

Morain studierte an der École polytechnique (Abschluss 1983) und promovierte 1990 an der Universität Lyon I (Courbes elliptiques et tests de primalité). 1997 habilitierte er sich an der Universität Paris VI (Courbes elliptiques, arithmétique et corps finis). Er ist am Labor für Informatik der École polytechnique (LIX), wo er das Universitäts-übergreifende TANC Projekt zur algorithmischen Zahlentheorie leitet. Außerdem ist er Ingenieur des französischen Verteidigungsministeriums.

1988 implementierte er den Elliptische Kurven verwendenden Atkin-Goldwasser-Kilian Primzahltest-Algorithmus, den er mit A. O. L. Atkin verbesserte.^[1] Auch später befasste er sich mit Primzahltests basierend auf Elliptischen Kurven. So implementierte er den gegenüber Goldwasser-Kilian verbesserten ECPP-Primzahltest, der auf einer Verbesserung eines Tests von A. O. L. Atkin mit Elliptischen Kurven mit komplexer Multiplikation beruht.^[2] Er implementierte auch eine noch schnellere Version von Jeffrey Shallit.

Mit Jeffrey Shallit und Hugh C. Williams entdeckte und rekonstruierte er den von Eugène Carissan 1920 in Paris ausgestellten zahlentheoretischen Computer (der ein Siebverfahren implementierte).^[3] Morain fand die Maschine nach einem Hinweis der Tochter des 1925 verstorbenen Carissan im Observatorium von Bordeaux noch in gutem Zustand. Er konnte damit in einem Test eine 13stellige Zahl faktorisieren. Sie steht nun im Conservatoire National du Arts et Metiers in Paris.^[4] Davor galt Derrick Lehmer als der Erste, der einen solchen zahlentheoretischen Spezialcomputer baute.

Schriften

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

Weblinks

• Homepage

Verweise

1. ↑ Atkin, Morain: Elliptic curves and primality proving. Math. Comp., Bd. 61, 1993, S. 29–68. Morain berichtet darüber auch mit R. Lercier in Eurocrypt 95, LN Computer Science Bd. 921, 1995
2. ↑ Elliptic Curve Primality Proving. Goldwasser-Kilian beruhte auf der Verwendung zufällig gewählter elliptischer Kurven, deren Punkteanzahl zuvor nach dem Schoof-Elkies-Atkin Algorithmus (SEA) auf Eignung getestet wurde, was den Algorithmus beträchtlich verlangsamte. Im ECPP-Test ist die Anzahl der Punkte dagegen von vornherein bekannt. Morain: Elliptic curves for primality proving, in Henk van Tilborg (Herausgeber): Encyclopedia of cryptography and security. Springer 2005
3. ↑ J. Shallit, H. C. Williams, F. Morain: Discovery of a lost factoring machine, Math. Intelligencer, Bd. 17, 1995, Nr. 3, S. 41–47
4. ↑ Ivars Peterson Cranking out primes

PND: kein individualisierter Datensatz vorhanden (Stand: 24. Januar 2011)

Normdaten: LCCN: nb2010020840 | WorldCat | WP-Personeninfo