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é).^[1] 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.^[2] 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.^[3] 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).^[4] 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.^[5] Davor galten Derrick Norman Lehmer und Derrick Henry Lehmer als Erste, die einen solchen zahlentheoretischen Spezialcomputer bauten.