asymptotically fast Jacobi symbol
nisse at lysator.liu.se
Sun Jan 24 14:26:44 CET 2010
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.
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