p = 29
ints = [14, 6, 11]
for a in range(29):
b = pow(a,2,29)
if b in ints:
print(b,a)
두 개의 해 중 작은 값을 제출해야 하니
답은 8이다.
Legendre Symbol
문제 및 설명
이차잉여에서는 정수의 모듈로를 사용하여 제곱근을 취하는 것이 무엇을 의미하는지 배웠습니다. 또한, 제곱근을 구하는 것이 항상 가능한 것은 아니라는 것을 알았습니다.
이전의 경우에는 p = 29일 때, 가장 간단한 제곱근 계산 방법도 충분히 빠른 속도였지만, p가 커짐에 따라 이 방법은 극도로 비현실적이 됩니다.
다행히도, 우리에게는 르장드르의 도움을 받아 정수가 이차잉여인지를 확인하는 단일 계산 방법이 있습니다. 아래에서는 소수 p를 모듈로 하는 경우를 가정합니다.
르장드르 기호를 살펴보기 전에, 이차잉여의 흥미로운 특성을 간단히 살펴보겠습니다.
이차잉여 * 이차잉여 = 이차잉여 이차잉여 * 이차잉여가 아닌 수 = 이차잉여가 아닌 수 이차잉여가 아닌 수 * 이차잉여가 아닌 수 = 이차잉여
✍기억하기 쉬운 방법이 필요하신가요? "이차잉여"를 +1로 대체하고 "이차잉여가 아닌 수"를 -1로 대체하면, 이 세 결과는 모두 같습니다!
그럼 이 기술은 무엇일까요? 르장드르 기호는 홀수 소수 p를 모듈로 하는 정수가 이차잉여인지를 효율적으로 판별하는 방법을 제공합니다.
르장드르 기호: (a / p) ≡ a(p-1)/2 mod p가 다음을 따릅니다:
(a / p) = 1인 경우 a가 이차잉여이고, a ≢ 0 (mod p) (a / p) = -1인 경우 a가 이차잉여가 아닌 수이고, a (mod p) (a / p) = 0인 경우 a ≡ 0 (mod p)
즉, 어떤 정수 a가 주어지면 pow(a,(p-1)//2,p)를 계산함으로써 a가 이차잉여인지를 결정할 수 있습니다.
이제 플래그값을 찾아보겠습니다. 다음 1024비트 소수와 10개의 정수가 주어질 때, 이차잉여를 찾고 그 제곱근을 계산하세요. 제곱근이 플래그가 됩니다. 가능한 두 개의 해 중에서 더 큰 값을 제출하세요.
🧠르장드르 기호는 어떤 정수가 이차잉여인지를 알려줍니다. 하지만 제곱근은 어떻게 찾을까요?! 제공된 소수는 p = 3 (mod 4)를 따르므로, 우리는 쉽게 제곱근을 계산할 수 있습니다. 답은 인터넷에서 찾을 수 있지만, 페르마의 소정리에 대해 생각한다면 직접 찾아볼 수도 있습니다.
p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]
for a in ints:
q = pow(a,(p-1)//2,p)
if q == 1:
z = pow(a,(p+1)//4,p)
print(z)
