개념 설명
제곱 잉여
우리는 모듈러 연산에서 곱셈과 나눗셈에 대해서 살펴보았다. 그러나 제곱근 모듈러를 정수로 취하는 것은 뭘 의미할까?
해당 논의를 위해 모듈러 $p = 29$를 사용해보자. 우리는 정수 $a = 11$을 취하여 $a^2 = 5 \mod 29$ 임을 계산할 수 있다.
$a = 11, a^2 = 5$로서 우리는 5의 제곱근이 11이라고 말한다.(?)
기분은 좋지만, 이제 18의 제곱근에 대해서 생각해보자. 위에서, 우리는 $a^2 = 18$인 정수 a를 찾을 필요가 있다는 것을 안다.
첫번째 아이디어는 $a=1$부터 시작하여 $a=p-1$까지 루프를 도는 것이다. 이 논의에서 p가 너무 크지 않으면 우리는 빨리 찾아낼 수 있을 것이다.
시도해보자. 이것을 코딩해보고 무엇을 찾는지 보자. 올바르게 코딩했다면 모든 $a \in F_p*$에 대해 $a^2 = 18$을 만족하는 a를 찾을 수 없을 것이다.
우리가 보고 있는 것은 $F*_p$의 원소들에 대해 모든 원소들이 제곱근을 가지는 것은 아니라는 것이다. 사실, 우리가 발견한 것은 $F_p*$ 원소의 거의 절반에 대해 제곱근이 없다는 것이다. (https://ko.wikipedia.org/wiki/%EC%A0%9C%EA%B3%B1_%EC%9E%89%EC%97%AC)
! 우리는 $a^2 = x \mod (p)$를 만족하는 a 가 존재한다면 정수 x를 제곱잉여(이차 잉여)라고 말한다. 그렇지 않으면 제곱비잉여(이차 비잉여)라고 한다.
즉, x의 제곱근을 모듈러 정수 p로 취할 수 있을 때 x를 제곱잉여라고 한다.
아래 리스트에는 2개의 제곱 비잉여와 한 개의 제곱 잉여가 있다.
제곱 잉여를 찾고 그것의 제곱근을 계산하라. 가능한 두 제곱근 중 작은 제곱근을 flag로 제출하라.
풀이
설명을 봐도 뭔 문제인지 잘 모르겠는데
chat gpt한테 물어봤다.
합동식의 성질을 까먹었다.. 이해가 안 가던 부분은 왜 위에서 a=1부터 시작해서 p-1까지 돌아도 모든 제곱 잉여를 검사할 수 있는가였다.
근데 제곱잉여 관련해서 제곱근이라는 말이 chat gpt가 하는 말은.. 이해가 안가는데.. 이건 잘못된거 같다. 3 모듈러에서 제곱잉여는 1뿐이다.
암튼, 제곱 잉여를 p-1까지 왜 봐도 되냐면 p 이후부터 다시 모듈러의 특징으로 숫자가 반복된다.
그리고 합동식의 성질 중에서
$a \equiv b \mod(m)$이면 자연수 k에 대해 $a^k \equiv b^k \mod(m)$라는 성질이 있어서 성립한다.
예를 들어 법 3에 대해서 1이나 4나 7이나 모두 모듈러로는 1이다. 그리고 그걸 제곱해도 그대로 합동식이 성립한다.
2, 5 8에 대해서도 2와 합동이다. 제곱해도 합동이다.
궁금한 점 : 0은 모든 자연수의 이차잉여인가?
위에서 말한 제곱근이라는 말은 $x^2 \equiv a \mod(m)$에서 이차 잉여 a를 만족하게 하는 x를 의미하는 말 같다.
흠.. 이제 어느정도 이해가 된 것 같으니
리스트에서 제곱 잉여를 찾고 그것의 제곱근을 계산해야 한다.
p에 대해서 1부터 p-1까지 순회하면서 제곱 잉여를 찾아보자.
p = 29
qr = []
for i in range(p) :
if pow(i, 2, p) not in qr:
qr.append(pow(i, 2, p))
qr.sort()
for q in qr :
print(q)0부터 p-1까지 순회하면서 i^2 % p 가 qr에 없으면 그 숫자를 추가했다.
그리고 정렬해서 출력했는데
이 숫자들이 29의 제곱잉여인듯..?
문제의 리스트에서 여기에 해당하는 제곱 잉여는 6이고
어떤 수를 제곱해야 6을 제곱 잉여로 가질까
p = 29
ints = [14, 6, 11]
for i in ints :
for j in range(p) :
if (pow(j, 2, p) == i) :
print(i,'is qudratic_residues', j,'is its sqrt')다시 코드를 작성해서
ints에 있는 수를 하나 잡고 p 내에서 어떤 수를 제곱해야 ints에 있는 수가 나오는지 보면
6 is qudratic_residues 8 is its sqrt
6 is qudratic_residues 21 is its sqrt
라는 결과가 나온다. 21과 8 중에서 작은 수는 8이다.
$8^2 \equiv 6 \mod(29)$라는 뜻이고 8이 정답이 된다. 두 제곱근 중 작은 수를 flag로 제출하라고 하였으니.
휴
