르장드르의 기호를 소개하면서, 소수에 대해 모듈로를 사용하여 제곱근이 있는지를 빠르게 판별하는 방법을 알아보았습니다. 더 나아가서, 이러한 제곱근을 효율적으로 계산하기 위한 알고리즘도 있습니다. 실제로 가장 좋은 알고리즘은 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에 대한 제곱근을 찾으세요. 두 개의 해 중에서 작은 값을 답으로 제출하세요.
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))
