An O(M(n) log n) algorithm for the Jacobi symbol

Richard Brent 1 Paul Zimmermann 2
2 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : The best known algorithm to compute the Jacobi symbol of two $n$-bit integers runs in time $O(M(n)\log n)$, using Schönhage's fast continued fraction algorithm combined with an identity due to Gauss. We give a different $O(M(n)\log n)$ algorithm based on the binary recursive gcd algorithm of Stehlé and Zimmermann. Our implementation --- which to our knowledge is the first to run in time $O(M(n)\log n)$ --- is faster than GMP's quadratic implementation for inputs larger than about $10000$ decimal digits.
Type de document :
Communication dans un congrès
Guillaume Hanrot and François Morain and Emmanuel Thomé. 9th Algorithmic Number Theory Symposium - ANTS IX, Jul 2010, Nancy, France. Springer Verlag, 6197, pp.83-95, 2010, Lecture Notes in Computer Science; Algorithmic Number Theory. <10.1007/978-3-642-14518-6_10>
Liste complète des métadonnées

https://hal.inria.fr/inria-00447968
Contributeur : Paul Zimmermann <>
Soumis le : lundi 18 janvier 2010 - 08:51:26
Dernière modification le : jeudi 22 septembre 2016 - 14:31:15

Identifiants

Collections

Citation

Richard Brent, Paul Zimmermann. An O(M(n) log n) algorithm for the Jacobi symbol. Guillaume Hanrot and François Morain and Emmanuel Thomé. 9th Algorithmic Number Theory Symposium - ANTS IX, Jul 2010, Nancy, France. Springer Verlag, 6197, pp.83-95, 2010, Lecture Notes in Computer Science; Algorithmic Number Theory. <10.1007/978-3-642-14518-6_10>. <inria-00447968>

Partager

Métriques

Consultations de la notice

175