개념 설명
르장드르 기호
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
이차잉여 오일러 판정법
01. 이차잉여 오일러 판정법 02. 이차잉여 오일러 판정법 예제 여러분의 자그만한 후원이 저에게 큰 도움이 됩니다ㅜㅜ클릭▶ 투네이션 후원링크
j1w2k3.tistory.com
이차 잉여인지 판별하는 방법은
르장드르 기호 $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))
오일러 판별법으로 이차 잉여인지 판별하고
이차 잉여를 대상으로 제곱근을 구한다.
개념 설명
르장드르 기호
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
이차잉여 오일러 판정법
01. 이차잉여 오일러 판정법 02. 이차잉여 오일러 판정법 예제 여러분의 자그만한 후원이 저에게 큰 도움이 됩니다ㅜㅜ클릭▶ 투네이션 후원링크
j1w2k3.tistory.com
이차 잉여인지 판별하는 방법은
르장드르 기호 $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))
오일러 판별법으로 이차 잉여인지 판별하고
이차 잉여를 대상으로 제곱근을 구한다.
