docs: def jacobi( a, n ):
    """Jacobi symbol"""
  
    # Based on the Handbook of Applied Cryptography (HAC), algorithm 2.149.
  
    # This function has been tested by comparison with a small
    # table printed in HAC, and by extensive use in calculating
    # modular square roots.
  
    assert n >= 3
    assert n%2 == 1
    a = a % n
    if a == 0: return 0
    if a == 1: return 1
    a1, e = a, 0
    while a1%2 == 0:
      a1, e = a1//2, e+1
    if e%2 == 0 or n%8 == 1 or n%8 == 7: s = 1
    else: s = -1
    if a1 == 1: return s
    if n%4 == 3 and a1%4 == 3: s = -s
    return s * jacobi( n % a1, a1 )