# File timestamp (UTC): 2021-02-02T16:17:21.552
# NIST Circuit Complexity Project
# https://csrc.nist.gov/projects/circuit-complexity

begin circuit LS16-4x4-GF256--rs=3933

# Boolean Circuit for a linear system y = A.x defined by a 32x32 bit-matrix A:
# Matrix represented as 32 rows: vecRows=UInt32[0x01029101, 0x0204e102, 0x04080104, 0x08100208, 0x10200410, 0x20400820, 0x40801040, 0x80c32080, 0x02910101, 0x04e10202, 0x08010404, 0x10020808, 0x20041010, 0x40082020, 0x80104040, 0xc3208080, 0x91010102, 0xe1020204, 0x01040408, 0x02080810, 0x04101020, 0x08202040, 0x10404080, 0x208080c3, 0x01010291, 0x020204e1, 0x04040801, 0x08081002, 0x10102004, 0x20204008, 0x40408010, 0x8080c320]
# Matrix represented as 32 columns: vecColsUInt32[0x07800101, 0x08810202, 0x10020404, 0x20040808, 0x41081010, 0x82102020, 0x02a04040, 0x03c08080, 0x80010107, 0x81020208, 0x02040410, 0x04080820, 0x08101041, 0x10202082, 0xa0404002, 0xc0808003, 0x01010780, 0x02020881, 0x04041002, 0x08082004, 0x10104108, 0x20208210, 0x404002a0, 0x808003c0, 0x01078001, 0x02088102, 0x04100204, 0x08200408, 0x10410810, 0x20821020, 0x4002a040, 0x8003c080]
# 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, 109 gates (109 XOR)
# Depth: 5

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