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, die auf elliptischen Kurven basieren. 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 13-stellige Zahl faktorisieren. Sie steht nun im Conservatoire National du Arts et Métiers in Paris.[4] Davor galten Derrick Norman Lehmer und Derrick Henry Lehmer als Erste, die einen solchen zahlentheoretischen Spezialcomputer bauten.

Schriften

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

Weblinks

Homepage
Literatur von und über François Morain im SUDOC-Katalog (Verbund französischer Universitätsbibliotheken)
Angaben zu François Morain in der Datenbank der Bibliothèque nationale de France.

Verweise

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
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
J. Shallit, H. C. Williams, F. Morain: Discovery of a lost factoring machine, Math. Intelligencer, Bd. 17, 1995, Nr. 3, S. 41–47
Ivars Peterson Cranking out primes: tracking down a long-lost factoring machine - Carissan's factoring machine - Cover Story (Memento vom 8. Juli 2012 im Webarchiv archive.today)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[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: tracking down a long-lost factoring machine - Carissan's factoring machine - Cover Story (Memento vom 8. Juli 2012 im Webarchiv archive.today)