문제

르장드르 기호에서는 소수에 대한 모듈러 제곱근이 있는지를 판단하는 빠른 방법을 소개했습니다. 더 나아가서, 이러한 제곱근을 효율적으로 계산하는 알고리즘도 있습니다. 실제로 가장 효율적인 알고리즘은 19세기에 이탈리아인에 의해 처음으로 설명되었으며 1970년대에 다니엘 샹크스에 의해 독립적으로 재발견되어 그의 이름을 따서 토넬리-샹크스(Tonelli-Shanks) 알고리즘이라고 합니다.

2가 아닌 모든 소수는 p ≡ 1 mod 4 또는 p ≡ 3 mod 4 형태입니다. 왜냐하면 모든 홀수는 이러한 합동식을 따르기 때문입니다. 앞의 도전 과제에서 암시한 대로, p ≡ 3 mod 4인 경우에는 페르마 소정리로부터 진짜 간단한 공식으로 제곱근을 계산할 수 있습니다. 그러나 p ≡ 1 mod 4인 경우에는 더 일반적인 알고리즘이 필요합니다.

$r^2 ≡ a\,mod\,p$와 같은 합동식에서, 토넬리-샹크스는 r을 계산합니다.

토넬리-샹크스는 합성(비소수) 모듈로에서 작동하지 않습니다. 합성수에 대한 제곱근을 찾는 것은 정수 인수 분해와 계산적으로 동등하기 때문에, 이것은 어려운 문제입니다.

이 알고리즘의 주요 사용 사례는 타원 곡선 좌표를 찾는 것입니다. 그 동작은 다소 복잡하기 때문에 세부 사항에 대해 논의하지 않겠지만, 구현은 쉽게 찾을 수 있으며 Sage에는 내장된 기능이 있습니다.

2048비트 소수 p에 대한 제곱근 a를 찾으세요. 두 개의 루트 중에서 작은 값을 답으로 제공하세요.

풀이

$a^2 ≡ x\,mod\,p$

위 식에서 a 값을 찾아야 합니다. 먼저 Legendre Symbol로 2차 잉여인지 아닌지 판별했습니다.

Legendre Symbol
if a^((p-1)/2) mod p = 1 이면 2차 잉여

그 이후 토넬리 샹크스 알고리즘으로 값을 계산합니다.

토넬리 샹크스 알고리즘
$a^2 ≡ x\,(mod\,p)$ 를 만족하는 a를 찾는 알고리즘입니다. 이 알고리즘은 p에 대해 $p ≡ 1\,(mod\,4)$인 경우에 사용됩니다.

def tonelli_shanks(n,p):
    def isQR(x,p):
        return pow(x,(p-1)//2,p)==1
    if not isQR(n,p):
        return -1
    Q,S=p-1,0
    while Q%2==0:
        S+=1
        Q//=2
    z=None
    for x in range(2,p):
        if not isQR(x,p):
            z=x
            break
    M,c,t,R=S,pow(z,Q,p),pow(n,Q,p),pow(n,(Q+1)//2,p)
    while True:
        if t==0:
            return 0
        elif t==1:
            return R
        k=t*t%p
        ii=None
        for i in range(1,M):
            if k==1:
                ii=i
                break
            k*=k
            k%=p
        b=pow(c,2**(M-i-1),p)%p
        M=ii%p
        c=b*b%p
        t=t*c%p
        R=R*b%p

if __name__=="__main__":
    a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
    p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

    if pow(1, (p-1)//2, p) == 1: # Legendre Symbol
        print(f"p ≡ {p%4} mod 4")
        result = tonelli_shanks(a, p)
        print(result)