[CryptoHack] Legendre Symbol

 

개념 설명

---

르장드르 기호

 

2차 잉여에서 우리는 제곱근 정수 모듈러를 취하는 것이 무슨 의미인지 배웠다...

우리는 또한 제곱근을 가지는 것이 항상 가능한 것은 아니라는 것을 알았다.

 

이전의 경우 $p = 29$일때 간단한 루트 계산으로도? 충분히 빨랐지만 p가 커질수록 이 방법은 엄청나게 불합리해진다.

다행히도 르장드르 덕분에 정수가 한 번의 계산으로 2차 잉여인지 확인할 수 있는 방법이 있다. 다음에서 우리는 소수 p에 대한 모듈러 작업을 한다고 가정할 것이다.

 

르장드르 기호를 살펴보기 전에 2차 잉여의 흥미로운 성질을 보기 위해 잠시 돌아가보자.

 

이차 잉여 * 이차 잉여 = 이차 잉여
이차 잉여 * 이차 비잉여 = 이차 비잉여
이차 비잉여 * 이차 비잉여 = 이차 잉여

! 이것을 쉽게 기억하는 방법은 이차 비잉여를 -1로 이차 잉여를 +1로 대치하면 결과가 동일하다.

그래서 이 트릭이 뭘까? 르장드르 기호는 홀수인 소수 p에 대해 이차 잉여인지 판별하는 효율적인 방법을 제공한다.

르장드르 기호 $: (a / p) \equiv a^{(p-1)/2} \mod p$는 다음과 같다.

(a / p) = 1 만약 모듈러 p에 대해 a가 이차잉여이고 a ≢ 0 이면
(a / p) = -1 만약 a는 모듈러 p에 대해 비이차잉여이면
(a / p) = 0 a는 모듈러 p에 대해 0

즉 임의의 정수 a가 주어지면 pow(a, (p-1)//2, p)를 계산하면 a가 이차잉여인지 판별하기에 충분하다.

 

이제 플래그를 위해, 다음 1024비트 소수와 10개의 정수가 주어지면 가능한 이차 잉여를 찾은 다음 제곱근을 계산하라.제곱근은 플래그이다. 가능한 두 제곱근 중에서 더 큰 제곱근을 답으로 제출하라.

 

! 그렇다면 르장드르 기호는 어떤 정수가 이차잉여인지 알려주지만 어떻게 제곱근을 찾을 수 있을까? 제공된 소수는 $p = 3 mod 4$를 따르므로 제곱근을 쉽게 계산할 수 있습니다. 답은 온라인이지만..? 페르마의 소정리를 따르면 스스로 알아낼 수 있다.

 

풀이

---

오일러 판정법 (르장드르 기호) 증명: https://j1w2k3.tistory.com/1366

이차잉여 오일러 판정법

 

이차 잉여인지 판별하는 방법은

르장드르 기호 $a/p = a^{(p-1)/2} \mod p$가 1인지만 보면 되니까 쉬운데

그 제곱근을 구하는 과정이 쉽지가 않았다.

 

제곱근을 구하기 위해서는 위 오일러 판별법을 알고 오는 것이 좋은 것 같다.

 

이차 잉여이면 $a/p = 1\mod p$임을 증명하기 위해서..

$x^2 \equiv a \equiv 1 \mod p$라는 것이 깔리고

이미 오일러 판정을 통해 이차잉여라는 것을 안 상태로 제곱근x 를 구하는 것이다.

$\therefore a/p = a^{(p-1)/2} \equiv 1 \mod p$ 합동식은 양 변에 같은 숫자를 곱해도 동일하므로 양 변에 a를 곱하면

$a^{(p+1)/2} \equiv a \mod p$ 양 변에 루트를 씌우면 x를 구할 수 있다. 이차 잉여이므로..

$a^{(p+1)/4} \equiv x \mod p$

근데 여기서 $(p+1)/4$가 유효한 정수인가..?를 말하기 위해서 $p \equiv 3 \mod 4$라는 식을 주었다. 위에서 한글로 번역해서 잘 몰랐는데. 그냥 이 식의 설명으로 제곱근을 쉽게 계산하기 위해서 줬다고 한다.

$p \equiv 3 \mod 4$로 인해서 p+1은 4의 배수이고 /4를 해도 정수이므로 $a^{(p+1)/4} \equiv x \mod p$ 만으로 계산이 가능하다.

 

그렇지 않다면..?

Tonelli-Shanks algorithm을 보야아 하는 것으로 보인다.

 

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139

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

for i in ints :
	if (pow(i, (p-1)//2, p) == 1) :
		print(i, 'is qr')
		print(pow(i, (p+1)//4, p))

 

오일러 판별법으로 이차 잉여인지 판별하고

이차 잉여를 대상으로 제곱근을 구한다.