mimc_fp2.py

# Let (L, R) = x, 0
# for i in range(128): (L, R) = (L, R) ** 3 + (k_i1, k_i2) (interpreting the two values as an element of some quadratic field over F_p,
# so the # actual equations are newL = L**3 + 3*q*L*R**2 + k_i1, newR = 3*L**2*R + q*R**3 + k_i2, 


from random import randint

q = 21888242871839275222246405745257275088696311157297823662689037894645226208583
q = 199

assert q % 4 == 3

k = (31371609233742916972193927528442068949060707271767911581026644231358880993764 % q,
	 53003166826344520661315078973306633185256605680202576081853632080398341582881 % q)


# From: https://pdfs.semanticscholar.org/3e01/de88d7428076b2547b60072088507d881bf1.pdf

def fp2_mul_sb(q, a, b, beta):
	"""Schoolbook multiplication"""
	c0 = (a[0]*b[0] + beta*a[1]*b[1]) % q
	c1 = (a[0]*b[1] + a[1]*b[0]) % q
	return (c0, c1)

def fp2_mul_kara(q, a, b, beta):
	"""Karatsuba multiplication"""
	v0 = (a[0]*b[0])%q
	v1 = (a[1]*b[1])%q
	c0 = (v0 + (beta*v1)) % q
	c1 = ((a0 + a1)*(b0 + b1) − v0 − v1) % q
	return (c0, c1)

def fp2_sq_kara(q, a, b, beta):
	"""Karatsuba squaring"""
	v0 = pow(a[0], 2, q)
	v1 = pow(a[1], 2, q)
	c0 = (v0 + (beta*v1)) % q
	c1 = (pow(a0 + a1, 2, q) − v0 − v1) % q
	return (c0, c1)

def fp2_sq_cm(q, a, b, beta):
	c0 = ((a0 + a1)*(a0 + (beta*a1)) − v0 − (beta*v0)) %q
	c1 = (2*v0) %q
	return (c0, c1)

def fp2_add(q, a, k):
	return ((a[0]+k[0]) % q, (a[1]+k[1]) % q)

def mimc_fp2(q, r, x, k, nr):
	# 6 constraints per-round
	e = (x, 0)
	for i in range(r):
		esq = fp2_mul(q, e, e, nr)		# e^2
		ecub = fp2_mul(q, esq, e, nr)	# e^3
		e = fp2_add(q, ecub, k)			# e^3 + k
	return e

# Find non-residue
for nr in range(1, q):
	x = (pow(nr, (q+1)//4, q)**2) % q
	if (x**2 % q) != x:
		break

print(q%4)

found = set()
for i in range(0, q):
	result = mimc_fp2(q, 4, i, k, nr)
	if result in found:
		print('Error!', i, '=', result)
	else:
		found.add(result)