Modular Math

Quadratic Residues

Suppose modulo p = 29. Take a = 11 and we can calculate that a^2 mod 29 = 121 mod 29 = 5. Here, the square root of 5 is 11.

How about the square root of 18? Let's try brute-forcing a starting from 0 to p-1.

p = 29
possible_a_squared = []
for a in range(p):
	res = pow(a, 2, p)
	possible_a_squared.append(res)

print(18 in possible_a_squared)
print(sorted(set(possible_a_squared)))

# False
# [0, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28]

As we can see, 18 has no square root. In fact, not all elements of modulo 29 have a square root. Roughly, only half of them have one. This actually means that the elements can have more than one root.

In the list printed above, which shows the elements of the modulo which do have square roots, are called the "quadratic residues". Inversely, the elements that do not have square roots are called "quadratic non-residues".

Note:

• x is a Quadratic Residue if there exists an a such that a^2 ≡ mod p. If there is no such solution, then the integer a^2 is a Quadratic Non-Residue.

• If a^2 = x then (-a)^2 = x. So if x is a quadratic residue in some finite field, then there are always two solutions for a.

Now onto the challenge. We are given p = 29 and ints = [14,6,11]. One of the integer in ints is a quadratic residue. We have to submit the smaller root of that integer.

To answer this, we can brute-force all possible roots.

p = 29
ints = [14, 6, 11]
for a in range(p):
	if (pow(a,2,p)) in ints:
		print(f"Found {a} to be the root of {pow(a,2,p)}")
		break

# Found 8 to be the root of 6

Flag: 8

Legendre Symbol

Rather than using a brute-force approach, there is a single operation in which we can decide whether an integer is a quadratic residue, which is called Legendre Symbol.

This is a property of quadratic residues:

• Quadratic Residue * Quadratic Residue = Quadratic Residue

• Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue

• Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue

Legendre Symbol: (a/p) ≡ a^(p−1)/2 mod p

(a/p) = 1 if a is a quadratic residue and a ≢ 0 mod p
(a/p) = -1 if a is a quadratic non-residue mod p
(a/p) = 0 if a ≡ mod p

To check of residue: calculate a^(p−1)/2 mod p.

To compute the square root, given that the prime p obeys p ≡ 3 mod 4, we can do this:

a^(p−1)/2 ≡ (a/p) mod p 	--> for quadratic residue, (a/p) is 1
a^(p−1)/2 ≡ 1 mod p 		--> multiply both by a
a^((p-1)/2)+1) ≡ a mod p 
a^(p+1)/2 ≡ a mod p 		--> take the square root of both
a^(p+1)/4 ≡ a^(1/2) mod p 	--> final formula

Here's the solver for the challenge.

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139

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

# Get the Quadratic Residue
for i in ints:
	is_residue = pow(i, (p-1)//2, p)
	if is_residue == 1:
		print(f"{i} is a quadratic residue")
		a = i
		break

# Get the roots
root1 = pow(a, (p+1)//4, p)
root2 = pow(-a, (p+1)//4, p)

print(max(root1, root2))

# 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771 is a quadratic residue
# 93291799125366706806545638475797430512104976066103610269938025709952247020061090804870186195285998727680200979853848718589126765742550855954805290253592144209552123062161458584575060939481368210688629862036958857604707468372384278049741369153506182660264876115428251983455344219194133033177700490981696141526

Flag: 93291799125366706806545638475797430512104976066103610269938025709952247020061090804870186195285998727680200979853848718589126765742550855954805290253592144209552123062161458584575060939481368210688629862036958857604707468372384278049741369153506182660264876115428251983455344219194133033177700490981696141526

Modular Square Root

Previously, we calculate the square root on the condition that p ≡ 3 mod 4. The generelized algorithm, which also works for p ≡ 1 mod 4, is called Tonelli-Shanks.

Tonelli-Shanks only works for prime moduli. For composite moduli, there is no efficient way to calculate the modular square root.

Main use of Tonelli-Shanks: finding elliptic curve coordinates.

Onto the challenge, here is the solver script.

from sage.all import *

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

root1 = mod(a,p).sqrt()
root2 = -root1 % p

print(min(root1, root2))

Flag: 2362339307683048638327773298580489298932137505520500388338271052053734747862351779647314176817953359071871560041125289919247146074907151612762640868199621186559522068338032600991311882224016021222672243139362180461232646732465848840425458257930887856583379600967761738596782877851318489355679822813155123045705285112099448146426755110160002515592418850432103641815811071548456284263507805589445073657565381850521367969675699760755310784623577076440037747681760302434924932113640061738777601194622244192758024180853916244427254065441962557282572849162772740798989647948645207349737457445440405057156897508368531939120

Chinese Remainder Theorem

Given these congruences where the moduli are coprime:

x ≡ a1 mod n1
x ≡ a2 mod n2
...
x ≡ ai mod ni

There is a unique solution x ≡ a mod N where N = n1*n2*...*ni.

For the challenge, we have to find a such that x ≡ a mod 935.

x ≡ 2 mod 5
x ≡ 3 mod 11
x ≡ 5 mod 17

Solving by hand (reference):

# initial guess
x = 11*17 + 5*17 + 5*11

# mod 5
11*17 mod 5 = 2 		--> DONE

# mod 11
5*17 mod 11 = 8 		--> get the inv. of 8 (7)
5*17*7 mod 11 = 1 		--> mul. with desired number (3)
5*17*7*3 mod 11 = 3 	--> DONE

# mod 17
5*11 mod 17 = 4 		--> get the inv. of 4 (13)
5*11*13 mod 17 = 1 		--> mul. with desired number (5)
5*11*13*5 mod 17 = 5 	--> DONE

# final answer
x = 11*17 + 5*17*7*3 + 5*11*13*5
x = 5547 --> 5547 mod 935 = 872
x ≡ 872 mod 935

Flag: 872