asymptotically fast Jacobi symbol

Paul Zimmermann Paul.Zimmermann at
Mon Jan 18 16:36:01 CET 2010


GMP 5.0.0 implements a quadratic algorithm for the Jacobi symbol. In we describe a subquadratic
algorithm, and exhibit speedups of almost a factor of 100 over GMP (which is
very difficult to achieve).

Richard P. Brent
Paul Zimmermann

More information about the gmp-devel mailing list