asymptotically fast Jacobi symbol

Niels Möller nisse at
Sun Jan 24 14:26:44 CET 2010

Paul Zimmermann <Paul.Zimmermann at> writes:

>> Does it suffer from the same inherent growth-to-the-left problem as the
>> gcd algorithm?
> yes (for the right-to-left variant).

And if I understood the paper correctly, the growth is slightly worse,
since the right-to-left Jacobi algorithm uses non-negative quotients,
while the corresponding gcd algorithm works with signed quotients.

I'm looking into left-to-right Jacobi now, although I'm not sure how
much time I will have for it. I think it should run at almost the same
speed as gcd (either Lehmer or sub-quadratic). Just one additional table
lookup per quotient.


Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list