BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Michael Monagan (Simon Fraser University)
DTSTART:20201119T173000Z
DTEND:20201119T183000Z
DTSTAMP:20260422T054117Z
UID:SFUQNTAG/16
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/SFUQNTAG/16/
 ">The Tangent-Graeffe root finding algorithm</a>\nby Michael Monagan (Simo
 n Fraser University) as part of SFU NT-AG seminar\n\n\nAbstract\nLet $f(x)
 $ be a polynomial of degree $d$ over a prime field of size $p$.\nSuppose $
 f(x)$ has $d$ distinct roots in the field and we want to compute them.\nQu
 estion: How fast can we compute the roots?\n\nThe most well known method i
 s the Cantor-Zassenhaus algorithm from 1981.\nIt is implemented in Maple a
 nd Magma.  It does\, on average\, $O(M(d) \\log d \\log p)$\narithmetic op
 erations in the field where $M(d)$ is the cost of multiplying two \npolyno
 mials of degree $\\le d$.\n\nIn 2015 Grenet\, van der Hoeven and Lecerf fo
 und a beautiful new method for \nthe case $p = s 2^k + 1$ with $s \\in O(d
 )$.\nThe new method improves on Cantor-Zassenhaus by a factor of $O(\\log 
 d)$.\nOur contribution is a speed up for the core computation of the new\n
 method by a constant factor and a C implementation of the new method\nusin
 g asymptotically fast polynomial arithmetic.\n\nIn the talk I will present
  the main ideas behind the new Tangent-Graeffe algorithm\,\nsome timings c
 omparing the Tangent Graeffe algorithm with the Cantor-Zassenhaus \nalgori
 thm in Magma\, and a new polynomial factorization world record.\n\nThis is
  joint work with Joris van der Hoeven.\n
LOCATION:https://researchseminars.org/talk/SFUQNTAG/16/
END:VEVENT
END:VCALENDAR