# File timestamp (UTC): 2021-02-27T13:03:20.691
# NIST Circuit Complexity Project
# https://csrc.nist.gov/projects/circuit-complexity

begin circuit JPST17-4x4-GF16--rs=217

# Boolean Circuit for a linear system y = A.x defined by a 16x16 bit-matrix A
# Matrix A weights (W): totalW=77, adjW=61, minWInRow=4, maxWInRow=6, minWInCol=4, maxWICol=6
# Matrix represented as 16 rows: vecRows=UInt16[0xd211, 0x9422, 0x1844, 0x2388, 0x1d21, 0x2942, 0x4184, 0x8238, 0x21d1, 0x4292, 0x8414, 0x3828, 0x1112, 0x2224, 0x4448, 0x8883]
# Matrix represented as 16 columns: vecCols=UInt16[0x8111, 0x9222, 0x2444, 0x4888, 0x1781, 0x2892, 0x4124, 0x8348, 0x1178, 0x2289, 0x4412, 0x8834, 0x1817, 0x2928, 0x4241, 0x8483]
# The element in the i-th row and j-th col of A is A[i,j] = 1 & (vecRows[i]>>(j-1)) = 1 & (vecCols[j]>>(i-1))

# Matrix obtained from: https://github.com/rub-hgi/shorter_linear_slps_for_mds_matrices
# Tally: 16 inputs, 16 outputs, 40 gates (40 XOR)
# Depth: 6

Inputs: x1:x16
Outputs: y1:y16
Internal: t1:t24
GateSyntax: GateName Output Inputs

# Regex find gate in new format: XOR\s([ty]\d+)\s([tyx]\d+)\s([tyx]\d+).*$
# Regex replacing to old format: \1 = XOR\(\2,\3\)

begin SLP
XOR t1 x6 x9
XOR t2 x1 x10
XOR t3 x2 x5
XOR t4 x8 x14
XOR t5 x4 x12
XOR t6 x1 x16
XOR t7 x2 t6
XOR t8 x7 t2
XOR y15 x15 t8
XOR t9 x12 t3
XOR y6 t4 t9
XOR t10 x9 t6
XOR y1 x5 t10
XOR t11 x1 x3
XOR t12 x6 t7
XOR t13 x8 x11
XOR y16 t7 t13
XOR t14 t9 t11
XOR y12 t12 t14
XOR y13 x13 t14
XOR t15 x13 t2
XOR y2 t12 t15
XOR t16 x4 t8
XOR y8 t10 t16
XOR t17 x7 t4
XOR y10 t16 t17
XOR t18 x3 t1
XOR y7 x15 t18
XOR t19 x15 t5
XOR y4 x8 t19
XOR t20 t13 t17
XOR y3 x3 t20
XOR t21 t13 t15
XOR y5 x9 t21
XOR t22 t1 t5
XOR y14 x14 t22
XOR t23 y2 y8
XOR y9 t3 t23
XOR t24 x11 t3
XOR y11 x15 t24
end SLP
end circuit