asymptotically fast Jacobi symbol

[Niels Möller]

Paul Zimmermann <Paul.Zimmermann at loria.fr> 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.
Right?

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.

Regards,
/Niels

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