jacobi_symbol.py (was: Re: myrkraverk.c)

[Johann 'Myrkraverk' Oskarsson]

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