문제

Quadratic Residues에서 우리는 제곱근 모듈로 정수를 취하는 것이 무엇을 의미하는지 배웠습니다. 또한 제곱근을 구하는 것이 항상 가능한 것은 아니라는 것도 알았습니다.

앞의 경우 p = 29일 때는 제곱근을 계산하는 가장 간단한 방법도 충분히 빨랐지만, p가커질수록 이 방법은 매우 어려워집니다.

다행히도 Legendre 덕분에 한 번의 계산으로 정수가 이차 잉여인지 확인할 수 있는 방법이 있습니다. 아래에서는 모듈로 소인수 p를 계산한다고 가정하겠습니다.

Legendre의 기호를 살펴보기 전에 이차 (비)잉여의 흥미로운 속성을 잠시 살펴봅시다.

이차 잉여 * 이차 잉여 = 이차 잉여
이차 잉여 * 이차 비잉여 = 이차 비잉여
이차 비잉여 * 이차 비잉여 = 이차 잉여

이를 쉽게 기억하고 싶으신가요? 2차 잉여를 +1로, 2차 비잉여를 -1로 바꾸면 세 가지 결과가 모두 동일합니다!

그렇다면 비결은 무엇일까요? 르장드르 기호는 정수가 이차 잔차 모듈로 홀수 소수인 p를 곱한 값인지 여부를 효율적으로 확인할 수 있는 방법을 제공합니다.

르장드르 기호 (a / p) ≡ a(p-1)/2 mod p 다음과 같습니다:

(a / p) = 1 만약 a가 이차 잉여고 a가 ≢ 0 mod p인 경우
(a / p) = -1 a가 이차 비잉여 mod p이면 -1
(a / p) = 0 a ≡ 0 mod p인 경우

즉, 정수 a가 주어졌을 때 pow(a,(p-1)//2,p) 를 계산하면 a가 이차 잉여인지 확인할 수 있습니다.

다음 1024비트 소수와 10개의 정수가 주어지면 이차 잉여를 구한 다음 그 제곱근을 계산하고, 이 제곱근이 플래그입니다. 두 가지 가능한 근 중 더 큰 근을 답으로 제출하세요.

르장드르 기호는 어떤 정수가 이차 잔차인지 알려주지만, 제곱근은 어떻게 찾을 수 있을까요? 제공된 소수는 p = 3 mod 4를 따르므로 제곱근을 쉽게 계산할 수 있습니다. 정답은 온라인에 있지만 페르마의 작은 정리를 생각하면 직접 알아낼 수 있습니다.

풀이

a^2 = ints mod p

제공된 output.txt 파일에 p, ints 가 제공됩니다. ints가 이차 잉여인지 아닌지 판별하고 이차잉여면 제곱근(a)을 찾으면 됩니다.

제곱근 구하는 식은 아래를 참고했습니다.

if pow(a, (p-1)//2, p) = 1 && p ≡ 3 mod 4
a^2 = x mod p 에서 a = pow(x, (p+1)//4, p)

def check_quadratic_residue(a, p):
    quadratic_residue = pow(a, (p - 1) // 2, p)

    if quadratic_residue == 1 or quadratic_residue == 0:
        return quadratic_residue
    else:
        return quadratic_residue - p

if __name__=="__main__":
    with open("output.txt", 'r') as file:
        lines = file.readlines()

    p = None
    ints = []

    # 값 가져오기
    for line in lines:
        if line.startswith("p = "):
            p = int(line.split('=')[1].strip())
        elif line.startswith('ints ='):
            ints_str = line.split('=')[1].strip()[1:-1]
            ints = [int(x.strip()) for x in ints_str.split(',')]

    # QR 검증 and 제곱근 구하기
    for i in ints:
        if check_quadratic_residue(i, p) == 1:
            print(i, "is qr")
            if p%4 == 3:
                print(pow(i, (p+1)//4, p))