[CryptoHack] Legendre Symbol (르장드르 기호)

이전 강의(Quadratic Residues, 제곱 잉여)에서는

모듈로 체계에서 이차 잉여가 존재하지만 모든 수가 그렇진 않다는 것을 배웠다.

 

이번 강의에서는 Legendre Symbol(르장드르 기호)에 대해 설명한다.

르장드르 기호는 어떤 수가 제곱 잉여인지 여부를 판단할 때 사용한다.

위키의 설명은 다음과 같다.

wikipedia

wikipedia

 

또 다음과 같은 식도 성립한다고 한다.

제곱 잉여(1) * 제곱 잉여(1) = 제곱 잉여(1)
제곱 잉여(1) * 제곱 비잉여(-1) = 제곱 비잉여(-1)
제곱 비잉여(-1) * 제곱 비잉여(-1) = 제곱 잉여(1)

 

 

크립토핵에선 르장드르 기호를 다음과 같이 정리해준다.

[정의]
(a / p) = 1 (모듈러 p에서 a가 제곱 잉여이고, a ≢ 0 mod p)
(a / p) = -1 (모듈러 p에서 a가 제곱 비잉여)
(a / p) = 0 (a ≡ 0 mod p)

[성질을 이용한 제곱 잉여 여부 판별]
(a / p) ≡ a^((p-1)/2) mod p
-> pow(a,(p-1)//2,p) == 1 (제곱 잉여)
-> pow(a,(p-1)//2,p) != 1 (제곱 비잉여)

 

---

연습문제는 다음과 같다.

소수 p와 정수 10개가 주어진다.

정수 10개 중 이차 잉여인 수를 찾고 해당 수의 모듈로 제곱근을 구하면 된다.

(힌트로 페르마의 소정리를 이용하라고 하는 것 같다)

 

제곱 잉여의 여부 파악은 쉽다.

하지만 제곱근을 구하는 과정이 어려웠다.

풀이를 찾아봤는데 푸는 과정이 신기했다.

x^2 = a (mod p)

a^((p-1)/2) = 1 (mod p)
a^((p+1)/2) = a (mod p)
a^((p+1)/4) = x (mod p)

일단 제곱 잉여를 판단하는 식은 다음과 같다.

a^((p-1)/2) = 1 (mod p)

 

여기서 양변에 a를 곱하게 되면 다음과 같다.
a^((p+1)/2) = a (mod p)

 

제곱 잉여이므로 a = x^2를 만족할 것이며

양변에 루트를 씌우면 제곱근을 구할 수 있다.
a^((p+1)/4) = x (mod p)

 

(이해는 잘 안 되지만 p = 3 (mod 4)를 만족해서 계산이 더 쉬웠다는 것 같다..)

 

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139

ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]

for a in ints:
    if pow(a,(p-1)//2,p) == 1:
        print('제곱잉여:',a)
        print('제곱근:',pow(a,(p+1)//4,p))

 

---

레퍼런스

https://cryptohack.org/courses/modular/root1/

CryptoHack – Home

https://ko.wikipedia.org/wiki/%EB%A5%B4%EC%9E%A5%EB%93%9C%EB%A5%B4_%EA%B8%B0%ED%98%B8

르장드르 기호 - 위키백과, 우리 모두의 백과사전

https://thfist-1071.tistory.com/262

[CryptoHack] Legendre Symbol