# File timestamp (UTC): 2021-01-26T08:59:59.958
# NIST Circuit Complexity Project
# https://csrc.nist.gov/projects/circuit-complexity

begin circuit C_BeiKraLea16_4x4_8--rs=18

# Boolean Circuit for a linear system y = A.x defined by a 32x32 bit-matrix A:
# Matrix represented as 32 rows: vecRows=UInt32[0x0102e901, 0x0204b102, 0x04080104, 0x08100208, 0x10200410, 0x20400820, 0x40801040, 0x80632080, 0x02e90101, 0x04b10202, 0x08010404, 0x10020808, 0x20041010, 0x40082020, 0x80104040, 0x63208080, 0xe9010102, 0xb1020204, 0x01040408, 0x02080810, 0x04101020, 0x08202040, 0x10404080, 0x20808063, 0x010102e9, 0x020204b1, 0x04040801, 0x08081002, 0x10102004, 0x20204008, 0x40408010, 0x80806320]
# Matrix represented as 32 columns: vecColsUInt32[0x07800101, 0x08810202, 0x10020404, 0x21040808, 0x42081010, 0x83902020, 0x01a04040, 0x03408080, 0x80010107, 0x81020208, 0x02040410, 0x04080821, 0x08101042, 0x90202083, 0xa0404001, 0x40808003, 0x01010780, 0x02020881, 0x04041002, 0x08082104, 0x10104208, 0x20208390, 0x404001a0, 0x80800340, 0x01078001, 0x02088102, 0x04100204, 0x08210408, 0x10420810, 0x20839020, 0x4001a040, 0x80034080]
# 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, 107 gates (107 XOR)
# Depth: 6

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