[CryptoHack] Modular Square Root (Tonelli-Shanks algorithm)

Legendre Symbol에서 우리는 숫자가 제곱근 모듈로 소수인지 여부를 확인하는 빠른 방법을 배웠다.

더 나아가서 이러한 근을 효율적으로 계산하는 알고리즘이 있다.

실제로 가장 좋은 것은 Tonelli-Shanks라고 불리며, 19세기에 이탈리아인에 의해 처음 기술되었고

1970년대에 Daniel Shanks에 의해 독립적으로 재발견되었다는 사실에서 이러한 이름을 얻었다.

 

2가 아닌 모든 소수는 p ≡ 1 mod 4 또는 p ≡ 3 mod 4 형식이다.

p ≡ 3 mod 4의 경우 제곱근을 계산하기 위한 정말 간단한 공식은 페르마의 소정리에서 직접 도출할 수 있다.

여전히 p ≡ 1 mod 4 경우가 남아 있으므로 보다 일반적인 알고리즘이 필요하다.

 

Tonelli-Shanks 알고리즘은 r^2 ≡ a mod p에서 r을 계산한다.

Tonelli-Shanks는 소수가 아닌 모듈로 p 체계에서 작동하지 않는다.

제곱근 모듈로 조합을 찾는 것은 계산적으로 정수 분해와 동일하다.

(어려운 문제라고 한다)

이 알고리즘의 주요 사용 사례는 타원 곡선 좌표를 찾는 것이다.

 

크립토핵에서 알고리즘의 동작이 복잡하여 설명을 따로 해주지 않았다.

(따로 찾아봤지만 이해가 어려워서 나중에 이해가 될 때 정리해보겠다)

---

연습 문제는 다음과 같다.
a (mod 2048비트 소수 p)의 제곱근을 구하라.

(두 개의 근 중 더 작은 것이 답이다)

 

Tonelli-Shanks 알고리즘이 구현된 파이썬 코드를 검색해서 답을 구했다.

(SageMath를 이용하는 방법도 있다고 한다)

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
    print(tonelli_shanks(a, p))

 

---

레퍼런스

https://cryptohack.org/courses/modular/tonelli-shanks/

CryptoHack – Home

https://sean9892.github.io/2020/11/20/TONELLI-SHANKS/

Tonelli-Shanks 알고리즘 구현