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. 〈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 11 janvier 2018 - 06:23:16

Lien texte intégral

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. 〈10.1007/978-3-642-14518-6_10〉. 〈inria-00447968〉

Partager

Métriques

Consultations de la notice

197