Legendre Symbol - 르장드르 기호

서론

지금까지 이런 해킹은 없었다. 이것은 크립토인가 수학인가.

 

이론

앞서 공부한 제곱 잉여

x^2 = a mod p

에서 p가 충분히 작다면 쉽게 a를 구할 수 있었지만, p가 커지면 어떻게 제곱 잉여인지 아닌지 쉽게 확인할 수 있을까.

 

르장드르 기호는 어떤 수가 제곱 잉여인지 아닌지 나타내는 함수이다.

기호는 아래와 같은데,

분수처럼 생겼지만 분수랑은 관계 없다.

 

르장드르 기호의 정의는 아래와같다.

포스팅에서는 편의 상 (a / p) 라고 하겠다.

즉, (a / p)가 1이면 제곱 잉여, -1이면 비 제곱 잉여, 0이면 잉여 없음으로 표현한다.

 

이들은 제곱 잉여의 성질에 대응하는데,

제곱 잉여 * 제곱 잉여 = 제곱 잉여
제곱 잉여 * 비제곱 잉여 = 비제곱 잉여
비제곱 잉여 * 비제곱 잉여 = 제곱 잉여

가 성립한다.

마찬가지로 제곱 잉여를 +1, 비제곱 잉여를 -1 이라고 생각하면 되겠다.

 

예를 들어 p가 7일때를 계산해보자.

제곱 잉여 글에서 확인하였듯이 제곱 잉여는 1,2,4, 비 제곱 잉여는 3,5,6 이었다.

이를 위의 식에 넣어보면

(a / p) ≡ a^((p-1)/2) (mod p)

(1 / 7) ≡ 1^(3) (mod 7) = 1

(2 / 7) ≡ 2^(3) (mod 7) = 1

(4 / 7) ≡ 4^(3) (mod 7) = 1

(3 / 7) ≡ 3^(3) (mod 7) = -1

(5 / 7) ≡ 5^(3) (mod 7) = -1

(6 / 7) ≡ 6^(3) (mod 7) = -1

(7 / 7) ≡ 7^(3) (mod 7) = 0

으로 표현할 수 있다.