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 ( ;; ) _:; -- https://mail.python.org/mailman3//lists/python-list.python.org
