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

begin circuit LW16-4x4-GF256--rs=572

# Boolean Circuit for a linear system y = A.x defined by a 32x32 bit-matrix A:
# Matrix represented as 32 rows: vecRows=UInt32[0x01010140, 0x02020280, 0x04040410, 0x08080821, 0x10101002, 0x20202004, 0x40404020, 0x80808008, 0x81400101, 0x04800202, 0x40100404, 0x02210808, 0x20021010, 0x01042020, 0x48204040, 0x10088080, 0x40018101, 0x80020402, 0x10044004, 0x21080208, 0x02102010, 0x04200120, 0x20404840, 0x08801080, 0x01814001, 0x02048002, 0x04401004, 0x08022108, 0x10200210, 0x20010420, 0x40482040, 0x80100880]
# Matrix represented as 32 columns: vecColsUInt32[0x01010108, 0x02020210, 0x04040420, 0x08080880, 0x10101004, 0x20202048, 0x40404001, 0x80808002, 0x08210101, 0x10080202, 0x20020404, 0x80400808, 0x04801010, 0x48102020, 0x01444040, 0x02018080, 0x21010801, 0x08021002, 0x02042004, 0x40088008, 0x80100410, 0x10204820, 0x44400140, 0x01800280, 0x01082101, 0x02100802, 0x04200204, 0x08804008, 0x10048010, 0x20481020, 0x40014440, 0x80020180]
# 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: 32 inputs, 32 outputs, 100 gates (100 XOR)
# Depth: 6

Inputs: x1:x32
Outputs: y1:y32
Internal: t1:t68
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 x7 x23
XOR t2 x1 x25
XOR t3 x15 x31
XOR t4 x9 x17
XOR t5 x2 x18
XOR t6 x4 x25
XOR y1 t4 t6
XOR t7 x15 x24
XOR t8 x20 x23
XOR t9 x8 x18
XOR t10 x4 x20
XOR t11 x10 x24
XOR t12 x14 x28
XOR t13 x4 x28
XOR y28 t7 t13
XOR t14 x12 t10
XOR t15 x22 t13
XOR t16 x5 x10
XOR t17 x6 t8
XOR t18 x7 t3
XOR t19 x3 x29
XOR t20 x17 x26
XOR t21 x30 t17
XOR y30 x13 t21
XOR t22 x6 x31
XOR t23 x13 x28
XOR y18 t5 t23
XOR t24 x9 x31
XOR t25 x16 t10
XOR y20 x31 t25
XOR t26 x5 x21
XOR t27 t1 t24
XOR y23 x27 t27
XOR t28 x20 x29
XOR t29 x15 t1
XOR t30 y1 t15
XOR y9 t2 t30
XOR t31 x2 x10
XOR y10 t28 t31
XOR t32 x3 x27
XOR t33 x20 t2
XOR t34 x19 x26
XOR t35 x19 t29
XOR y15 x25 t35
XOR t36 t13 t14
XOR y4 x8 t36
XOR t37 x23 t3
XOR y7 x1 t37
XOR t38 x11 t26
XOR y21 x32 t38
XOR t39 x30 t12
XOR t40 x18 x26
XOR y2 t16 t40
XOR t41 x16 t20
XOR y16 x8 t41
XOR t42 t3 t22
XOR t43 x14 t33
XOR y25 x9 t43
XOR t44 x17 t36
XOR t45 x6 x19
XOR t46 x2 x12
XOR t47 x18 x30
XOR t48 x3 t34
XOR y19 x14 t48
XOR t49 x16 x19
XOR t50 x11 t18
XOR y31 x17 t50
XOR t51 x16 x24
XOR t52 x13 t19
XOR y5 x21 t52
XOR t53 x2 t51
XOR y8 x32 t53
XOR t54 t12 t22
XOR y14 x21 t54
XOR t55 x13 x24
XOR t56 x10 x22
XOR y27 t32 t56
XOR t57 x22 t42
XOR t58 x9 x32
XOR y32 t9 t58
XOR t59 x5 t55
XOR y13 x27 t59
XOR t60 x8 x25
XOR y24 t11 t60
XOR t61 x7 t39
XOR y6 t15 t61
XOR t62 x32 t14
XOR y12 t8 t62
XOR t63 x3 t47
XOR y11 x11 t63
XOR t64 x5 t49
XOR y29 x29 t64
XOR t65 x12 x29
XOR y22 t57 t65
XOR t66 x26 t46
XOR y26 x21 t66
XOR t67 x11 x27
XOR y3 t45 t67
XOR t68 t43 t44
XOR y17 t39 t68
end SLP
end circuit