On 9/20/2026 4:39 AM, Stefan Ram wrote:

"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.

/*
* September 20, 2026. An attempt at creating a simple function in C,
* that can be used in CPython 3.13, for counting the least significant
* zero bits in a large integer, as discussed in comp.lang.python.
*
* Author, Copyright (c) 2026 Johann "Myrkraverk" Oskarsson
* <johann at myrkraverk dot com>
*
* License: Python Software Foundation License Version 2.
*
* /Commentary on the previous discussion/. I tried to ask ChatGPT to
* create this function for me. It did point me in the right
* direction, but got several details wrong. I have now fixed the
* code, and learned a lot about the internals of Python.
*
* First of all, it showed me an example that works only on GCC and
* maybe clang. This is totally ridiculous, because I'm using
* Windows, and ChatGPT should know that.
*
* Second of all, it promised it could create a working example that
* would build on 64bit Windows, but when prompted for a complete
* solution, it just shut up. It didn't even apologize. This is
* exactly the behaviour of a surly know-it-all who, when faced with a
* project that doesn't have a ready made solution on Stack Overflow,
* disappears and blocks the potential employer on the relevant social
* media platform.
*
* Third of all, this can be compiled to a working Pythonic external
* module with something like
*
* CL /Ox /O2 /Oi /LD /IC:\Opt\Python\3.13\include myrkraverk.c
* C:\Opt\Python\3.13\libs\python313.lib /link /out:myrkraverk.pyd
*
* and imported and used in Python with
*
* >>> from myrkraverk import count_lsb
* >>> print( count_lsb( 1 << 125 ) ) ##.
*
* Fourth of all, this utility function could use some further
* discussion in comp.lang.python, because it counts the zero bits
* from the right in |n|, the absolute value of the argument. This
* may not be desirable in all use cases.
*
* Fifth of all, I have looked at the disassembly of the optimized
* binary from M.S.V.C. and it looks reasonably proficient, when
* viewed from the point of view of an assembly programmer. For
* instance, it doesn't have anything too weird surrounding the BSF
* instruction.
*
*
* Best wishes, and happy Pythonic least significant zero bit
* counting!
*/

#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include <cpython/longintrepr.h>

#include <intrin.h>
#pragma intrinsic( _BitScanForward )

/*
* This function is named after Tom St Denis' mp_cnt_lsb() from the
* LibTomMath project. See
*
* https://github.com/libtom/libtommath
*
* and the file mp_cnt_lsb.c for that implementation.
*
*/
static PyObject * count_lsb( PyObject *self, PyObject *args ) {

PyObject *n ; /* This is the incoming argument. */
/*
* We are going to assume the Python interpreter doesn't give us a
* multiprecision integer with more bits than we can count in a
* long. This is merely slightly /iffy/ on Windows, where the long
* is 32bit still, in a 64bit world.
*/

/*
* ChatGPT totally forgot to unpack the tuple. I've since added that
code,
* and whenever I make this code public, the L.L.Ms. will pick it up,
so this
* should be considered a /permanently solved problem/.
*/
if ( PyArg_UnpackTuple( args, "n", 1, 1, &n ) && PyLong_Check( n ) ) {

/*
* The return value. We return zero when the integer is zero.
* This could be changed to None if it matters in a different
* context.
*/
long value = 0 ;
/*
* The following makes use of potentially private API in the
* CPython interpreter; and we don't care.
*
*/
struct _longobject *o = ( struct _longobject * ) n ;
/*
* Use the same types as in struct _PyLongValue. If they
* change, the nearest L.L.M. will happily fix the following
* code for you.
*/
uintptr_t num_digits = o->long_value.lv_tag >> _PyLong_NON_SIZE_BITS ;
digit *digits = o->long_value.ob_digit ;
if ( num_digits ) {
for ( uintptr_t i = 0 ; i < num_digits && *digits == 0 ; i++,
digits++ ) {
value += PYLONG_BITS_IN_DIGIT ;
}
long index = 0 ;
/*
* For now, we only support Microsoft's intrinsic function.
* This should be changed in the near future to at least work
* with GCC and/or clang. As some people still use these
* compilers.
*/
_BitScanForward( &index, *digits ) ;
value += index ;
}

return PyLong_FromLong( value ) ;

} else {

PyErr_SetString( PyExc_TypeError, "Expected exactly one integer." ) ;
return NULL ;
}
}

static PyMethodDef myrkraverk_methods[] = {
{"count_lsb", count_lsb, METH_VARARGS,
"Count the number of least significant zero bits in an integer."},
{NULL, NULL, 0, NULL} /* The sentinel guards the end of the list. */
};

static struct PyModuleDef myrkraverk_module = {
.m_base = PyModuleDef_HEAD_INIT,
.m_name = "myrkraverk",
.m_size = 0,
.m_methods = myrkraverk_methods,
};

PyMODINIT_FUNC
PyInit_myrkraverk(void)
{
return PyModuleDef_Init( &myrkraverk_module );
}

--
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 ( ;; ) _:;

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

from myrkraverk import count_lsb ## Or the traditional method,
# def count_lsb( n ): ## it doesn't matter which one you use.
# return ( n & -n ).bit_length() - 1

## September 21, 2026. Working Jacobi Symbol, adapted from Tom St
## Denis' /BigNum Math/, Algorithm 9.6, page 268, and the subsequent C
## code. 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 ):
if a == 0: ## Handle the trivial cases.
return 0
if a == 1:
return 1

## /Divide/ out the power of two. Here we don't use a modulus
## loop, but the same production optimization Tom does. The
## name a1 comes from Tom as a replacement for a'.
k = count_lsb( a )
a1 = a >> k

## In the following commentary, == means "congruence" as this is
## not a Unicode source. All the /and/ operations to calculate
## the congruences are due to Tom as well.

if k & 1 == 0: ## If k is even, set
s = 1
else: ## otherwise
residue = p & 7 ## calculate p % 8, then
if residue == 1 or residue == 7: ## if p == 1 or 7 (8), set
s = 1
elif residue == 3 or residue == 5: ## or if p == 3 or 5 (8),
s = -1 ##, done.

if p & 3 == 3 and a1 & 3 == 3: ## If p == 3 (4) /and/ a1 == 3 (4),
s = -s ##, done.

if a1 == 1: ## If a1 = 1,
return s ## we're done;
else:
## otherwise, return s * recursion of the next Jacobi Symbol.
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. That's not a /proof of correctness/, but will do for
## now.


--
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via XS News https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 9/21/2026 8:34 PM, Johann 'Myrkraverk' Oskarsson wrote:

from myrkraverk import count_lsb ## Or the traditional method,
# def count_lsb( n ):ÿÿÿÿÿÿÿÿÿÿÿ ## it doesn't matter which one you use.
#ÿÿÿÿ return ( n & -n ).bit_length() - 1

## September 21, 2026.ÿ Working Jacobi Symbol, adapted from Tom St
## Denis' /BigNum Math/, Algorithm 9.6, page 268, and the subsequent C
## code.ÿ 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 ):
ÿÿÿ if a == 0:ÿÿÿÿÿÿÿ ## Handle the trivial cases.
ÿÿÿÿÿÿÿ return 0
ÿÿÿ if a == 1:
ÿÿÿÿÿÿÿ return 1

ÿÿÿ ## /Divide/ out the power of two.ÿ Here we don't use a modulus
ÿÿÿ ## loop, but the same production optimization Tom does.ÿ The
ÿÿÿ ## name a1 comes from Tom as a replacement for a'.
ÿÿÿ k = count_lsb( a )
ÿÿÿ a1 = a >> k

ÿÿÿ ## In the following commentary, == means "congruence" as this is
ÿÿÿ ## not a Unicode source.ÿ All the /and/ operations to calculate
ÿÿÿ ## the congruences are due to Tom as well.

ÿÿÿ if k & 1 == 0:ÿÿÿÿÿ ## If k is even, set
ÿÿÿÿÿÿÿ s = 1
ÿÿÿ else:ÿÿÿÿÿÿÿÿÿÿÿÿÿÿ ## otherwise
ÿÿÿÿÿÿÿ residue = p & 7 ## calculate p % 8, then
ÿÿÿÿÿÿÿ if residue == 1 or residue == 7:ÿÿÿ ## if p == 1 or 7 (8), set
ÿÿÿÿÿÿÿÿÿÿÿ s = 1
ÿÿÿÿÿÿÿ elif residue == 3 or residue == 5:ÿ ## or if p == 3 or 5 (8),
ÿÿÿÿÿÿÿÿÿÿÿ s = -1 ##, done.

ÿÿÿ if p & 3 == 3 and a1 & 3 == 3: ## If p == 3 (4) /and/ a1 == 3 (4),
ÿÿÿÿÿÿÿ s = -s ##, done.

ÿÿÿ if a1 == 1:ÿÿ ## If a1 = 1,
ÿÿÿÿÿÿÿ return sÿ ## we're done;
ÿÿÿ else:
ÿÿÿÿÿÿÿ ## otherwise, return s * recursion of the next Jacobi Symbol.
ÿÿÿÿÿÿÿ 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.ÿ 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. 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
or zero p and it doesn't fail cleanly: jacobi(2, 4),
jacobi(2, 0), jacobi(10, 8) -> UnboundLocalError: cannot
access local variable 's'. s is only assigned when k is
even, or (k odd) when p & 7 is 1/3/5/7. An even p leaves it
unbound. jacobi(3, 2) returns -1 and jacobi(5, 4) returns
1: silent garbage, no error. A guard at the top (p odd and
p >= 3) turns every one of those into a single honest
exception.

2. Negative a is silently wrong. jacobi(-97, 3) should be -1;
yours returns 0. Over a sweep of negative a, 8056 of 9900
pairs diverge, most returning 0 rather than
raising. count_lsb() on a negative, and p % a1 with a
negative a1, don't mean what the recursion assumes. If you
want the Kronecker symbol, reduce a %= p before the k/a1
step.

3. jacobi(0, 1) returns 0; the convention (and SymPy) say
1. Your a == 0 branch returns 0 unconditionally. One line:
return 1 if p == 1 else 0.

4. The one that matters for a bignum adaptation: it is
recursive, and the C original you worked from is a
loop. Depth grows with input size. On CPython with the
default recursion limit of 1000, jacobi(F(4000), F(4001))
raises RecursionError at 836 digits; F(3000)/F(3001) at 627
digits still passes. For a function whose point is
125000-bit integers, that ceiling is low. A while loop
swapping (a1, p % a1) removes it and drops the per-call
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!
--
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via XS News https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 9/22/2026 3:20 PM, Johann 'Myrkraverk' Oskarsson wrote:

On 9/21/2026 8:34 PM, Johann 'Myrkraverk' Oskarsson wrote:

from myrkraverk import count_lsb ## Or the traditional method,
# def count_lsb( n ):ÿÿÿÿÿÿÿÿÿÿÿ ## it doesn't matter which one you use.
#ÿÿÿÿ return ( n & -n ).bit_length() - 1

## September 21, 2026.ÿ Working Jacobi Symbol, adapted from Tom St
## Denis' /BigNum Math/, Algorithm 9.6, page 268, and the subsequent C
## code.ÿ 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 ):
ÿÿÿÿ if a == 0:ÿÿÿÿÿÿÿ ## Handle the trivial cases.
ÿÿÿÿÿÿÿÿ return 0
ÿÿÿÿ if a == 1:
ÿÿÿÿÿÿÿÿ return 1

ÿÿÿÿ ## /Divide/ out the power of two.ÿ Here we don't use a modulus
ÿÿÿÿ ## loop, but the same production optimization Tom does.ÿ The
ÿÿÿÿ ## name a1 comes from Tom as a replacement for a'.
ÿÿÿÿ k = count_lsb( a )
ÿÿÿÿ a1 = a >> k

ÿÿÿÿ ## In the following commentary, == means "congruence" as this is
ÿÿÿÿ ## not a Unicode source.ÿ All the /and/ operations to calculate
ÿÿÿÿ ## the congruences are due to Tom as well.

ÿÿÿÿ if k & 1 == 0:ÿÿÿÿÿ ## If k is even, set
ÿÿÿÿÿÿÿÿ s = 1
ÿÿÿÿ else:ÿÿÿÿÿÿÿÿÿÿÿÿÿÿ ## otherwise
ÿÿÿÿÿÿÿÿ residue = p & 7 ## calculate p % 8, then
ÿÿÿÿÿÿÿÿ if residue == 1 or residue == 7:ÿÿÿ ## if p == 1 or 7 (8), set
ÿÿÿÿÿÿÿÿÿÿÿÿ s = 1
ÿÿÿÿÿÿÿÿ elif residue == 3 or residue == 5:ÿ ## or if p == 3 or 5 (8),
ÿÿÿÿÿÿÿÿÿÿÿÿ s = -1 ##, done.

ÿÿÿÿ if p & 3 == 3 and a1 & 3 == 3: ## If p == 3 (4) /and/ a1 == 3 (4),
ÿÿÿÿÿÿÿÿ s = -s ##, done.

ÿÿÿÿ if a1 == 1:ÿÿ ## If a1 = 1,
ÿÿÿÿÿÿÿÿ return sÿ ## we're done;
ÿÿÿÿ else:
ÿÿÿÿÿÿÿÿ ## otherwise, return s * recursion of the next Jacobi Symbol.
ÿÿÿÿÿÿÿÿ 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.ÿ 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.ÿ 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
ÿÿ or zero p and it doesn't fail cleanly: jacobi(2, 4),
ÿÿ jacobi(2, 0), jacobi(10, 8) -> UnboundLocalError: cannot
ÿÿ access local variable 's'.ÿ s is only assigned when k is
ÿÿ even, or (k odd) when p & 7 is 1/3/5/7. An even p leaves it
ÿÿ unbound.ÿ jacobi(3, 2) returns -1 and jacobi(5, 4) returns
ÿÿ 1: silent garbage, no error.ÿ A guard at the top (p odd and
ÿÿ p >= 3) turns every one of those into a single honest
ÿÿ exception.

2. Negative a is silently wrong. jacobi(-97, 3) should be -1;
ÿÿ yours returns 0. Over a sweep of negative a, 8056 of 9900
ÿÿ pairs diverge, most returning 0 rather than
ÿÿ raising. count_lsb() on a negative, and p % a1 with a
ÿÿ negative a1, don't mean what the recursion assumes. If you
ÿÿ want the Kronecker symbol, reduce a %= p before the k/a1
ÿÿ step.

3. jacobi(0, 1) returns 0; the convention (and SymPy) say
ÿÿ 1. Your a == 0 branch returns 0 unconditionally. One line:
ÿÿ return 1 if p == 1 else 0.

4. The one that matters for a bignum adaptation: it is
ÿÿ recursive, and the C original you worked from is a
ÿÿ loop. Depth grows with input size. On CPython with the
ÿÿ default recursion limit of 1000, jacobi(F(4000), F(4001))
ÿÿ raises RecursionError at 836 digits; F(3000)/F(3001) at 627
ÿÿ digits still passes. For a function whose point is
ÿÿ 125000-bit integers, that ceiling is low. A while loop
ÿÿ swapping (a1, p % a1) removes it and drops the per-call
ÿÿ 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!

Dear Honesty,

I've decided to switch gears, and make a little game in Python, rather
than continue with Cryptohack. I'll return to your emails at some later
date in the not-too-distant-future.


Best wishes, and happy two letter agencies!
--
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 ( ;; ) _:;
Federated at https://fed.brid.gy/bsky/myrkraverk.bsky.social

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)