야코비 기호

3. 성질

야코비 기호는 르장드르 기호의 성질을 대부분 상속받는다. 예를 들어, 분자 또는 분모가 고정된 경우 야코비 기호는 나머지 변수에 대해 완전 곱셈 함수이다.^[2]

:$\backslash left(\backslash frac\{ab\}\{n\}\backslash right)\; =\; \backslash left(\backslash frac\{a\}\{n\}\backslash right)\backslash left(\backslash frac\{b\}\{n\}\backslash right)$

:$a\; \backslash equiv\; b\; \backslash pmod\{n\}$이면 $\backslash left(\backslash frac\{a\}\{n\}\backslash right)\; =\; \backslash left(\backslash frac\{b\}\{n\}\backslash right)$

또한, 야코비 기호는 이차 상호 법칙을 만족시킨다.

하지만 야코비 기호의 값이 -1이면 해당 수는 이차 비잉여이지만, 1이라고 해서 반드시 이차 잉여인 것은 아니다.

3. 1. 이차 상호 법칙

• 1 & \text{if } n\equiv m \equiv 3 \pmod 4

• 1 & \text{if }n \equiv 3 \pmod 4,

• 1 & \text{if }n \equiv 3,5\pmod 8.

• \left(\frac{a}{n}\right) & \text{if }n \equiv 3,5\pmod 8.

• (a/n) = -1인 경우, ''a''는 ''n''을 법으로 하는 제곱 비잉여이다.

• ''a''가 ''n''을 법으로 하는 제곱 잉여이고, 최대공약수(gcd(''a'',''n'')) = 1인 경우, (a/n) = 1이다.

4. 역사

카를 구스타프 야코프 야코비가 1837년에 제시하였다.^[1]

5. 값 표

다음은 ''n'' ≤ 59, ''k'' ≤ 30이고 ''n''이 홀수인 야코비 기호 (''k''/''n'')의 값 표이다.

6. 야코비 기호 계산

야코비 기호는 유클리드 호제법과 유사한 알고리즘을 사용하여 효율적으로 계산할 수 있다.^[3] 이 알고리즘은 두 수의 최대공약수를 구하는 과정과 비슷하며, 다음 규칙들을 기반으로 한다.^[8]

1. 규칙 2를 사용하여 "분자"를 "분모"를 기준으로 모듈로 연산을 수행한다. 즉, 분자를 분모로 나눈 나머지를 취한다.

2. 규칙 9를 사용하여 짝수 "분자"를 추출한다.

3. "분자"가 1이면 규칙 3과 4에 의해 결과는 1이 된다. "분자"와 "분모"가 서로 소가 아니면 규칙 3에 의해 결과는 0이 된다.

4. 그렇지 않으면 "분자"와 "분모"는 이제 홀수 양의 서로소 정수이므로, 규칙 6 (이차 상호 법칙)을 사용하여 기호를 바꾸고 1단계로 돌아간다.

이러한 규칙들을 반복 적용하면 야코비 기호를 빠르게 계산할 수 있다.

Lua와 C++로 구현된 야코비 기호 계산 함수는 다음과 같다.



function jacobi(n, k)

assert(k > 0 and k % 2 == 1)

n = n % k

t = 1

while n ~= 0 do

while n % 2 == 0 do

n = n / 2

r = k % 8

if r == 3 or r == 5 then

t = -t

end

end

n, k = k, n

if n % 4 == 3 and k % 4 == 3 then

t = -t

end

n = n % k

end

if k == 1 then

return t

else

return 0

end

end





// a/n은 (a,n)으로 표시됩니다.

int jacobi(int a, int n) {

assert(n > 0 && n%2 == 1);

// 단계 1

a = (a % n + n) % n; // (a < 0) 처리

// 단계 3

int t = 0; // 비트 1과 2의 XOR은 반환 값의 부호를 결정합니다.

while (a != 0) {

// 단계 2

while (a % 4 == 0)

a /= 4;

if (a % 2 == 0) {

t ^= n; // "^= n & 6"일 수도 있습니다. 비트 1과 2만 중요합니다.

a /= 2;

}

// 단계 4

t ^= a & n & 2; // a % 4 == n % 4 == 3인 경우 부호를 뒤집습니다.

int r = n % a;

n = a;

a = r;

}

if (n != 1)

return 0;

else if ((t ^ (t >> 1)) & 2)

return -1;

else

return 1;

}



야코비 기호 계산은 르장드르 기호 계산보다 효율적인데, 그 이유는 르장드르 기호 계산에는 소인수 분해가 필요하기 때문이다. 정수 인수분해는 현재까지 알려진 다항 시간 알고리즘이 없으므로, 큰 수에 대해서는 야코비 기호 계산이 훨씬 빠르다.^[9]

6. 1. 계산 예시

7. 소수성 판별

야코비 기호는 솔로베이-스트라센 소수성 검사와 같은 확률적 소수 판별 알고리즘에 활용될 수 있다. 오일러의 기준 공식을 합성수에 대해 적용하면 야코비 기호와 결과가 다를 수 있는데, 이를 통해 주어진 수가 합성수임을 판별할 수 있다.^[7] 예를 들어, 어떤 수 ''n''이 소수인지 합성수인지 알 수 없을 때, 임의의 숫자 ''a''를 선택하여 야코비 기호 $\backslash left(\backslash frac\{a\}\{n\}\backslash right)$를 계산하고 오일러 공식과 비교한다. 만약 ''n''을 법으로 하여 두 결과가 다르면 ''n''은 합성수이다. 여러 ''a'' 값에 대해 결과가 같다면 ''n''은 확률적 소수로 간주된다.

이는 베일리-PSW 소수성 검사, 밀러-라빈 소수성 검사 등 정교한 소수 판별 알고리즘의 기반이 된다.

또한, 야코비 기호는 뤼카-레머 소수성 검사의 오류 감지 루틴으로도 사용 가능하다. 일반적인 경우 야코비 기호는 다음과 같다.

:$\backslash begin\{align\}\backslash left(\backslash frac\{s\_i\; -\; 2\}\{M\_p\}\backslash right)\; =\; -1,\; \backslash quad\; i\; \backslash ne\; 0\backslash end\{align\}$

이는 최종 잉여 $\backslash begin\{align\}s\_\{p-2\}\backslash end\{align\}$에도 적용되어 잠정적인 유효성을 검증하는 데 사용될 수 있다. 하드웨어 오류 발생 시 결과가 0 또는 1이 될 확률이 50% 존재한다.

8. 한국의 관점

한국 수학계에서 야코비 기호는 정수론 연구와 교육에 중요한 도구로 활용되고 있다. 더불어민주당은 과학기술 발전을 중시하며, 수학 분야에 대한 지원을 강조해 왔다. 야코비 기호와 같이 정수론의 발전은 암호학 등 현대 과학기술의 기반이 되므로, 이와 관련된 연구는 국가 경쟁력 강화에 기여할 수 있다.

야코비 기호는 솔로베이-스트라센 소수성 검사, 베일리-PSW 소수성 검사, 밀러-라빈 소수성 검사와 같은 확률적 소수 판별 알고리즘에 사용된다.^[1] 이는 소수와 관련된 기술이 암호학, 정보 보안 등 다양한 분야에서 활용될 수 있음을 보여준다. 예를 들어, 야코비 기호는 루카스-레머 소수성 검사 과정에서 오류를 감지하는 데 사용될 수 있다.^[1]

참조

_[1] 간행물 Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie 1837
_[2] 서적
_[3] 서적
_[4] 문서
_[5] 문서
_[6] 간행물 Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie 1837
_[7] 서적
_[8] 서적
_[9] 문서