this should be a utility function in the underlying multiprecision lib-
rary in Python. Is the calculation n & -n really necessary?
"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> 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.
On 9/20/2026 2:23 AM, Stefan Ram wrote:
"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> 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.-a Is the calculation n & -n really necessary?
-a-a While "n & -n" might take some time for large Python integers,
-a-a I see no way to do it faster in Python.
-a-a In C, one might be able to access the segments of large numbers
-a-a (the "limbs") starting with the least significant one to shortcut
-a-a the operation as soon as a "1" is found.
Yes, this is perplexing.-a 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 "Myrkraverk" Oskarsson wrote:
On 9/20/2026 2:23 AM, Stefan Ram wrote:
"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> 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.-a Is the calculation n & -n really necessary?
-a-a While "n & -n" might take some time for large Python integers,
-a-a I see no way to do it faster in Python.
-a-a In C, one might be able to access the segments of large numbers
-a-a (the "limbs") starting with the least significant one to shortcut
-a-a the operation as soon as a "1" is found.
Yes, this is perplexing.-a 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.
Negative values are stored by flipping all bits of n and adding 1. This
is exactly why negating numbers with trailing zeros causes long carry chains, and negating numbers with trailing ones does not.
it really should be simpler to just
count the zero bits in the underlying C code.
Why can't we do that?
On 9/20/2026 3:37 AM, Lane W wrote:
Johann "Myrkraverk" Oskarsson wrote:
On 9/20/2026 2:23 AM, Stefan Ram wrote:
"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> 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.-a Is the calculation n & -n really necessary?
-a-a While "n & -n" might take some time for large Python integers,
-a-a I see no way to do it faster in Python.
-a-a In C, one might be able to access the segments of large numbers
-a-a (the "limbs") starting with the least significant one to shortcut >>>> -a-a the operation as soon as a "1" is found.
Yes, this is perplexing.-a 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.
Negative values are stored by flipping all bits of n and adding 1.
This is exactly why negating numbers with trailing zeros causes long
carry chains, and negating numbers with trailing ones does not.
Thank you for that exposition.-a This is precisely why I am perplexed and befuddled.-a For arbitrary long integers -- in bits -- this chain of
carries over unknown machine words internally to the Python interpreter
seems completely unnecessary, and it really should be simpler to just
count the zero bits in the underlying C code.
Why can't we do that?
"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:
it really should be simpler to just
count the zero bits in the underlying C code.
Why can't we do that?
You /can/ ask your chatbot to generate a C extension that does this
and explain how to compile and call it from Python.
( n & -n ).bit_length() - 1
"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:
it really should be simpler to just
count the zero bits in the underlying C code.
Why can't we do that?
You /can/ ask your chatbot to generate a C extension that does this
and explain how to compile and call it from Python.
_BitScanForward( &index, *digits ) ;
"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:
_BitScanForward( &index, *digits ) ;
From the documentation:
|If no bit is found, the function returns 0 and the value
|written to the address in the first parameter is undefined.
. However, if there are 32 0s before a 1 is found, this
might be intended to add "32" to the total zero count.
(GCC's and Clang's "__builtin_ctz" can also count bits and
might be more portable.)
Newsgroups: comp.lang.python,comp.lang.c,sci.math
Followup-To: comp.lang.python,comp.lang.c
125from myrkraverk import count_lsb
print( count_lsb( -( 1 << 125 ) ) )
import timeit
Traceback (most recent call last):timeit.timeit( "count_lsb( 1 << 125 )" )
A bit more worrying is that I do not off hand know how to time my cre-
ation. This is because /timeit/ can't find it.
"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:
Perhaps I should have made that clearer in the code comments?
No, I was too focused on just that one line,
not paying attention to the global context.
A bit more worrying is that I do not off hand know how to time my cre-
ation. This is because /timeit/ can't find it.
Maybe you can pass the globals which should contain the name
"count_lsb":
timeit.timeit("count_lsb(1 << 125)", globals=globals())
. The optional "globals" argument specifies a namespace in
which to execute the code.
You could also try the pattern,
start_time = timeit.default_timer()
count_lsb(1<<125)
dt = timeit.default_timer() - start_time
. However, when "count_lsb(1<<125)` is very fast, the results
might be less accurate. (You can ask your chatbot about
"pitfalls of microbenchmarks in Python".)
125000n = 1 << 125000
( n & -n ).bit_length() - 1
... return ( n & -n ).bit_length() - 1def lsb( n ):
3.679828499996802timeit.timeit( "lsb( n )", globals=globals() )
3.6671537999936845timeit.timeit( "lsb( n )", globals=globals() )
3.677232099988032timeit.timeit( "lsb( n )", globals=globals() )
0.8524350000079721timeit.timeit( "count_lsb( n )", globals=globals() )
0.8531503000122029timeit.timeit( "count_lsb( n )", globals=globals() )
0.8298240999865811timeit.timeit( "count_lsb( n )", globals=globals() )
0.8146453999797814timeit.timeit( "count_lsb( n )", globals=globals() )
0.22153766143356377print( 0.8146453999797814 / 3.677232099988032 )
from myrkraverk import count_lsb ## Or the traditional method,
# def count_lsb( n ):-a-a-a-a-a-a-a-a-a-a-a ## it doesn't matter which one you use.
#-a-a-a-a return ( n & -n ).bit_length() - 1
## September 21, 2026.-a Working Jacobi Symbol, adapted from Tom St
## Denis' /BigNum Math/, Algorithm 9.6, page 268, and the subsequent C
## code.-a I believe Figure 9.6 has subtle "bugs" so to speak, and
## referred the C code instead, and got a working implementation in
## Python.
def jacobi( a, p ):
-a-a-a if a == 0:-a-a-a-a-a-a-a ## Handle the trivial cases.
-a-a-a-a-a-a-a return 0
-a-a-a if a == 1:
-a-a-a-a-a-a-a return 1
-a-a-a ## /Divide/ out the power of two.-a Here we don't use a modulus
-a-a-a ## loop, but the same production optimization Tom does.-a The
-a-a-a ## name a1 comes from Tom as a replacement for a'.
-a-a-a k = count_lsb( a )
-a-a-a a1 = a >> k
-a-a-a ## In the following commentary, == means "congruence" as this is
-a-a-a ## not a Unicode source.-a All the /and/ operations to calculate
-a-a-a ## the congruences are due to Tom as well.
-a-a-a if k & 1 == 0:-a-a-a-a-a ## If k is even, set
-a-a-a-a-a-a-a s = 1
-a-a-a else:-a-a-a-a-a-a-a-a-a-a-a-a-a-a ## otherwise
-a-a-a-a-a-a-a residue = p & 7 ## calculate p % 8, then
-a-a-a-a-a-a-a if residue == 1 or residue == 7:-a-a-a ## if p == 1 or 7 (8), set
-a-a-a-a-a-a-a-a-a-a-a s = 1
-a-a-a-a-a-a-a elif residue == 3 or residue == 5:-a ## or if p == 3 or 5 (8),
-a-a-a-a-a-a-a-a-a-a-a s = -1 ##, done.
-a-a-a if p & 3 == 3 and a1 & 3 == 3: ## If p == 3 (4) /and/ a1 == 3 (4),
-a-a-a-a-a-a-a s = -s ##, done.
-a-a-a if a1 == 1:-a-a ## If a1 = 1,
-a-a-a-a-a-a-a return s-a ## we're done;
-a-a-a else:
-a-a-a-a-a-a-a ## otherwise, return s * recursion of the next Jacobi Symbol.
-a-a-a-a-a-a-a return s * jacobi( p % a1, a1 )
## I have checked the above function with the ten Cryptohack challenge
## numbers against the implementation in SymPy, and they are
## equivalent.-a That's not a /proof of correctness/, but will do for
## now.
On 9/21/2026 8:34 PM, Johann 'Myrkraverk' Oskarsson wrote:
from myrkraverk import count_lsb ## Or the traditional method,
# def count_lsb( n ):-a-a-a-a-a-a-a-a-a-a-a ## it doesn't matter which one you use.
#-a-a-a-a return ( n & -n ).bit_length() - 1
## September 21, 2026.-a Working Jacobi Symbol, adapted from Tom St
## Denis' /BigNum Math/, Algorithm 9.6, page 268, and the subsequent C
## code.-a I believe Figure 9.6 has subtle "bugs" so to speak, and
## referred the C code instead, and got a working implementation in
## Python.
def jacobi( a, p ):
-a-a-a-a if a == 0:-a-a-a-a-a-a-a ## Handle the trivial cases.
-a-a-a-a-a-a-a-a return 0
-a-a-a-a if a == 1:
-a-a-a-a-a-a-a-a return 1
-a-a-a-a ## /Divide/ out the power of two.-a Here we don't use a modulus
-a-a-a-a ## loop, but the same production optimization Tom does.-a The
-a-a-a-a ## name a1 comes from Tom as a replacement for a'.
-a-a-a-a k = count_lsb( a )
-a-a-a-a a1 = a >> k
-a-a-a-a ## In the following commentary, == means "congruence" as this is
-a-a-a-a ## not a Unicode source.-a All the /and/ operations to calculate
-a-a-a-a ## the congruences are due to Tom as well.
-a-a-a-a if k & 1 == 0:-a-a-a-a-a ## If k is even, set
-a-a-a-a-a-a-a-a s = 1
-a-a-a-a else:-a-a-a-a-a-a-a-a-a-a-a-a-a-a ## otherwise
-a-a-a-a-a-a-a-a residue = p & 7 ## calculate p % 8, then
-a-a-a-a-a-a-a-a if residue == 1 or residue == 7:-a-a-a ## if p == 1 or 7 (8), set
-a-a-a-a-a-a-a-a-a-a-a-a s = 1
-a-a-a-a-a-a-a-a elif residue == 3 or residue == 5:-a ## or if p == 3 or 5 (8),
-a-a-a-a-a-a-a-a-a-a-a-a s = -1 ##, done.
-a-a-a-a if p & 3 == 3 and a1 & 3 == 3: ## If p == 3 (4) /and/ a1 == 3 (4), >> -a-a-a-a-a-a-a-a s = -s ##, done.
-a-a-a-a if a1 == 1:-a-a ## If a1 = 1,
-a-a-a-a-a-a-a-a return s-a ## we're done;
-a-a-a-a else:
-a-a-a-a-a-a-a-a ## otherwise, return s * recursion of the next Jacobi Symbol.
-a-a-a-a-a-a-a-a return s * jacobi( p % a1, a1 )
## I have checked the above function with the ten Cryptohack challenge
## numbers against the implementation in SymPy, and they are
## equivalent.-a That's not a /proof of correctness/, but will do for
## now.
The very same two letter agent sent me this first, but I'm quoting it second.-a It's also been cleaned up in an Emacs before pasting into Thun- derbird.
--------------------------------------------------------------------
Johann,
Replying again to your real address (my first attempt went to
the .invalid header, which can't resolve). You said the ten
Cryptohack vectors aren't a proof, only a smoke test. You're
right, and the gap is wider than you flagged. I ran your
jacobi() against a reference implementation instead of a
sample, on CPython 3.11.6.
On the domain you intend (a >= 0, p odd >= 3) it is clean:
exhaustive over p odd 1..299 x a 0..399, plus 20,000 random
pairs with p up to 10^12. Zero divergences. The core is right,
well past ten vectors. Now the edges, where the vectors don't
go.
1. No domain guard. Jacobi needs p odd and >= 3. Give it even
-a-a or zero p and it doesn't fail cleanly: jacobi(2, 4),
-a-a jacobi(2, 0), jacobi(10, 8) -> UnboundLocalError: cannot
-a-a access local variable 's'.-a s is only assigned when k is
-a-a even, or (k odd) when p & 7 is 1/3/5/7. An even p leaves it
-a-a unbound.-a jacobi(3, 2) returns -1 and jacobi(5, 4) returns
-a-a 1: silent garbage, no error.-a A guard at the top (p odd and
-a-a p >= 3) turns every one of those into a single honest
-a-a exception.
2. Negative a is silently wrong. jacobi(-97, 3) should be -1;
-a-a yours returns 0. Over a sweep of negative a, 8056 of 9900
-a-a pairs diverge, most returning 0 rather than
-a-a raising. count_lsb() on a negative, and p % a1 with a
-a-a negative a1, don't mean what the recursion assumes. If you
-a-a want the Kronecker symbol, reduce a %= p before the k/a1
-a-a step.
3. jacobi(0, 1) returns 0; the convention (and SymPy) say
-a-a 1. Your a == 0 branch returns 0 unconditionally. One line:
-a-a return 1 if p == 1 else 0.
4. The one that matters for a bignum adaptation: it is
-a-a recursive, and the C original you worked from is a
-a-a loop. Depth grows with input size. On CPython with the
-a-a default recursion limit of 1000, jacobi(F(4000), F(4001))
-a-a raises RecursionError at 836 digits; F(3000)/F(3001) at 627
-a-a digits still passes. For a function whose point is
-a-a 125000-bit integers, that ceiling is low. A while loop
-a-a swapping (a1, p % a1) removes it and drops the per-call
-a-a overhead too.
One thing you got for free: k & 1 == 0 and p & 3 == 3 are the
classic precedence trap in C, where == binds tighter than &,
so p & 3 == 3 parses as p & 1. In Python & binds tighter, so
they parse as you meant. If you ever port this back to C, add
the parentheses.
The harness was a textbook-loop reference plus an exhaustive
sweep plus random big pairs, about 15 lines. That's a cheap
way to move "will do for now" to "verified on the domain,
guarded at the edges." Happy to send it if you want it.
Honesty
--------------------------------------------------------------------
Dear Honesty,
Yes, you can send me the harness if you see this reply.
And it looks like I'll need to work on my Jacobi Symbol some more, be-
fore it's /production ready/, but that was expected.
Best wishes, and happy Python!
| Sysop: | Amessyroom |
|---|---|
| Location: | Fayetteville, NC |
| Users: | 74 |
| Nodes: | 6 (0 / 6) |
| Uptime: | 121:05:06 |
| Calls: | 1,194 |
| Files: | 1,352 |
| Messages: | 290,204 |