On 9/20/2026 2:23 AM, Stefan Ram wrote:
"Johann \"Myrkraverk\" Oskarsson" <[email protected]> wrote or quoted:
The above formula seems to work, given a few spot checks, but I thought
this should be a utility function in the underlying multiprecision lib-
rary in Python. Is the calculation n & -n really necessary?
While "n & -n" might take some time for large Python integers,
I see no way to do it faster in Python.
In C, one might be able to access the segments of large numbers
(the "limbs") starting with the least significant one to shortcut
the operation as soon as a "1" is found.
Yes, this is perplexing. I'm working with /arbitrary large numbers/ in
Cryptohack, for cryptographic purposes, and need a utility function to
count the number of zero bits from the right.
The toy implementations of the Jacobi Symbol I've seen online, in Python
and otherwise, all seem to use a loop to repeatedly divide by two, which
is presumably much slower, so I'm /sort of happy/ with this method.
For practical applications, I resorted to the jacobi_symbol() function
in SymPy, since I have not finished a correct implementation myself.
But more on that in a later post.
--
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via Easynews.com
https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;
--
https://mail.python.org/mailman3//lists/python-list.python.org
