[CryptoHack] MATHEMATICS (Modular Square Root)

Modular Square Root

문제 및 설명

르장드르의 기호를 소개하면서, 소수에 대해 모듈로를 사용하여 제곱근이 있는지를 빠르게 판별하는 방법을 알아보았습니다. 더 나아가서, 이러한 제곱근을 효율적으로 계산하기 위한 알고리즘도 있습니다. 실제로 가장 좋은 알고리즘은 Tonelli-Shanks라고 불리며, 이는 19세기에 이탈리아인에 의해 처음으로 기술되었으며, 1970년대에 Daniel Shanks에 의해 독립적으로 재발견되었습니다. 2가 아닌 모든 소수는 p ≡ 1 mod 4 또는 p ≡ 3 mod 4 형태입니다. 왜냐하면 모든 홀수는 이러한 합동식을 따르기 때문입니다. 이전의 도전에서 암시한 대로, p ≡ 3 mod 4 경우에는 페르마의 소정리로부터 직접적으로 계산 가능한 매우 간단한 공식을 얻을 수 있습니다. 이에 반해 p ≡ 1 mod 4 경우, 보다 일반적인 알고리즘이 필요합니다. r² ≡ a mod p 형태의 합동식에서, Tonelli-Shanks는 r을 계산합니다. ✍Tonelli-Shanks는 합성 (소수가 아닌) 모듈 연산에는 작동하지 않습니다. 합성 수를 모듈 연산로하여 제곱근을 찾는 것은 정수 인수 분해와 계산적으로 동등한 문제입니다. 즉, 어려운 문제입니다. 이 알고리즘의 주요 사용 사례는 타원 곡선 좌표를 찾는 것입니다. 그 동작은 다소 복잡하기 때문에 세부 사항을 논의하지는 않겠지만, 구현은 쉽게 찾을 수 있으며 Sage에는 내장된 기능이 있습니다. a 모듈러의 2048비트 소수 p에 대한 제곱근을 찾으세요. 두 개의 해 중에서 작은 값을 답으로 제출하세요.

풀이

output.txt

tonelli shanks 알고리즘은 제곱잉여와 제곱 비잉여에 대한 이산 로그를 계산하는 알고리즘이고,

즉 이차잉여인 a와 소수 p가 주어 질때 제곱근 x를 찾는것 이다.

그리고 실제로 sage를 통해 이러한 tonelli shanks 알고리즘을 사용할 수 있다고 하지만,

sage를 불러올 수 가 없어

tonelli_shanks알고리즘을

해당 블로그에서 가지고 오게 되었다.

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

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

print(tonelli_shanks(a,p))

답은 위의 수이다.