@inproceedings{80648c9156354fdd9c552ee0ed7fd7c7,
title = "Randomized root finding over finite FFT-fields using tangent Graeffe transforms",
abstract = "Consider a finite field Fq whose multiplicative group has smooth cardinality. We study the problem of computing all roots of a polynomial that splits over Fq, which was one of the bottlenecks for fast sparse interpolation in practice. We revisit and slightly improve existing algorithms and then present new randomized ones based on the Graeffe transform. We report on our implementation in the Mathemagix computer algebra system, confirming that our ideas gain by a factor ten at least in practice, for sufficiently large inputs.",
keywords = "Algorithm, Finite fields, Mathemagix, Polynomial root finding",
author = "Bruno Grenet and \{Van Der Hoeven\}, Joris and Gr{\'e}goire Lecerf",
year = "2015",
month = jun,
day = "24",
doi = "10.1145/2755996.2756647",
language = "English",
series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",
publisher = "Association for Computing Machinery",
pages = "197--204",
booktitle = "ISSAC 2015 - Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation",
note = "40th ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2015 ; Conference date: 06-07-2015 Through 09-07-2015",
}