jacobi記号 - crypto-writeup-public

奇素数 $p$ と整数 $x$ に対して、 $J_p (x) = x^{\frac{p-1}{2}} \mod p$

$J_p(x) = 1$ のとき $x$ は mod pで平方剰余

$J_p(x) = -1$ のときそうでない

性質

$J_p(xy) = J_p(x) J_p(y)$

$N=pq$ で

$J_N(x) = J_p(x \mod p) J_q(x \mod q)$

※ $J_N(x) = 1$ になる場合として、 $J_p(x) = -1, J_q(x) = -1$ もありうる。この場合は xは平方剰余ではないので注意（ここが legendre記号との違い

原理はよくわかってないが、次のプログラムで $\mod n$ でのjacobi 記号を求めることができる。sageにもjacobi_symbol があるし、gmpy2にもjacobi がある

# https://rosettacode.org/wiki/Jacobi_symbol#Python
def jacobi(a, n):
    assert n > 0
    assert n % 2 == 1
    
    a %= n
    result = 1
    while a != 0:
        while a % 2 == 0:
            a = a//2
            n_mod_8 = n % 8
            if n_mod_8 in (3, 5):
                result = -result
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            result = -result
        a %= n
    if n == 1:
        return result
    else:
        return 0