jacobi  평방 잉여 기호 (a/p)의 값을 계산한다

int jacobi(long a, long p);

a  평방 잉여 기호의 분자
p  평방 잉여 기호의 분모

평방 잉여 기호의 값 +1 또는 -1. 인수에 의해 계산 불능의 경우는 0.

int jacobi(long a, long p)
{
    int  x = 1;
    long tmp;
    
    if (p <= 0) return 0;
    if (p > 2 && (p & 1) == 0) return 0;
    if ((a = a % p) <= 0) return 0;
   
    while (a > 1) {
        if (a & 1) {
            if ((a & 3) == 3 && (p & 3) == 3) x = -x;
            tmp = p;
            p = a;
            a = tmp;
            a = a % p;
        } else {
            a >>= 1;
            if ((p & 7) == 3 || (p & 7) == 5) x = -x;
        }
    }
    if (a == 0) return 0;
    return x;
}

　　　　x²≡a　(mod p)

되는 x 는 존재할 때와 존재하지 않을 때가 있다. 예를 들어, p = 7 때
　　　　1²≡1, 2²≡4, 3²≡2, 4²≡2, 5²≡4, 6²≡1
이기 때문에, a≡1 또는 2 또는 4 때 마셔 해가 있다. 해가 있을 때, a 를 mod p 에서의 평방 잉여라고 한다. a 가 있는 수를 평방 해 p 로 나눈 나머지와 되기 때문이다. 해가 없을 때는, 평방비잉여라고 한다. 이 때,

　　　　(a/p)= 1 　　해가 있어
　　　　(a/p)=-1 　　해가 없음

(이)라고 정의된다. 또, 이 (a/p)를 평방 잉여 기호라고 한다.

평방 잉여 기호의 값을 계산하는데, 이하의 성질이 이용된다.

　　　　(1/p) = 1
　　　　(ab/p) = (a/p)(b/p)

　　　　(2/p) = 1, p≡1 또는 7 (mod 8) 시
　　　　(2/p) = -1, p≡3 또는 5 (mod 8) 시

　　　　홀수 a 와 서로 순수한 p 에 대해서, Gauss 정리보다
　　　　(a/p) = (p/a), p≡1 또는 a≡1 (mod 4) 시
　　　　(a/p) = -(p/a), p≡3 또한 a≡3 (mod 4) 시

위의 성질로부터, a 의 값이 홀수인가 짝수인가로 다른 처리를 한다. 짝수의 경우는, (2/p)의 값을 들여 두어 a 자신의 값을 반으로 한다. 홀수의 경우는, 분모와 분자를 바꿔 넣어 Euclid호제법을 적용한다. 이 반복을 a 가 1 이 될 때까지 실시한다.

따라서, 본알고리즘에서는 평방 잉여 기호의 값을 log(p)에 비례 시간에 계산된다.