# File timestamp (UTC): 2021-02-25T00:33:12.202
# NIST Circuit Complexity Project
# https://csrc.nist.gov/projects/circuit-complexity

begin circuit M-8x8-GF256--rs=25

# Boolean Circuit for a linear system y = A.x defined by a 64x64 bit-matrix A
# Matrix A weights (W): totalW=976, adjW=912, minWInRow=14, maxWInRow=17, minWInCol=14, maxWICol=17
# Matrix represented as 64 rows: vecRows=UInt64[0x070b0301090c0204, 0x0e050602010b0408, 0x0f0a0c0402050803, 0x0d070b08040a0306, 0x70b0301090c02040, 0xe050602010b04080, 0xf0a0c04020508030, 0xd070b08040a03060, 0x09010c0b07030402, 0x01020b050e060804, 0x0204050a0f0c0308, 0x04080a070d0b0603, 0x9010c0b070304020, 0x1020b050e0608040, 0x204050a0f0c03080, 0x4080a070d0b06030, 0x020c0103040b0709, 0x040b020608050e01, 0x0805040c030a0f02, 0x030a080b06070d04, 0x20c0103040b07090, 0x40b020608050e010, 0x805040c030a0f020, 0x30a080b06070d040, 0x030407020c09010b, 0x06080e040b010205, 0x0c030f080502040a, 0x0b060d030a040807, 0x30407020c09010b0, 0x6080e040b0102050, 0xc030f080502040a0, 0xb060d030a0408070, 0x0c02090403070b01, 0x0b040108060e0502, 0x050802030c0f0a04, 0x0a0304060b0d0708, 0xc02090403070b010, 0xb040108060e05020, 0x50802030c0f0a040, 0xa0304060b0d07080, 0x010902070b04030c, 0x0201040e0508060b, 0x0402080f0a030c05, 0x0804030d07060b0a, 0x10902070b04030c0, 0x201040e0508060b0, 0x402080f0a030c050, 0x804030d07060b0a0, 0x04030b0c02010907, 0x0806050b0402010e, 0x030c0a050804020f, 0x060b070a0308040d, 0x4030b0c020109070, 0x806050b0402010e0, 0x30c0a050804020f0, 0x60b070a0308040d0, 0x0b07040901020c03, 0x050e080102040b06, 0x0a0f03020408050c, 0x070d060408030a0b, 0xb07040901020c030, 0x50e080102040b060, 0xa0f03020408050c0, 0x70d060408030a0b0]
# Matrix represented as 64 columns: vecCols=UInt64[0x090d06010b030804, 0x0b070a020d04090c, 0x060f05040a080209, 0x0c0e0b0805010402, 0x90d06010b0308040, 0xb070a020d04090c0, 0x60f05040a0802090, 0xc0e0b08050104020, 0x0603090b010d0408, 0x0a040b0d02070c09, 0x0508060a040f0902, 0x0b010c05080e0204, 0x603090b010d04080, 0xa040b0d02070c090, 0x508060a040f09020, 0xb010c05080e02040, 0x0801040d030b0906, 0x09020c07040d0b0a, 0x0204090f080a0605, 0x0408020e01050c0b, 0x801040d030b09060, 0x9020c07040d0b0a0, 0x204090f080a06050, 0x408020e01050c0b0, 0x01080b0906040d03, 0x02090d0b0a0c0704, 0x04020a0605090f08, 0x0804050c0b020e01, 0x1080b0906040d030, 0x2090d0b0a0c07040, 0x4020a0605090f080, 0x804050c0b020e010, 0x03060d0408090b01, 0x040a070c090b0d02, 0x08050f0902060a04, 0x010b0e02040c0508, 0x3060d0408090b010, 0x40a070c090b0d020, 0x8050f0902060a040, 0x10b0e02040c05080, 0x040b08030d010609, 0x0c0d090407020a0b, 0x090a02080f040506, 0x020504010e080b0c, 0x40b08030d0106090, 0xc0d090407020a0b0, 0x90a02080f0405060, 0x20504010e080b0c0, 0x0d0903080406010b, 0x070b04090c0a020d, 0x0f0608020905040a, 0x0e0c0104020b0805, 0xd0903080406010b0, 0x70b04090c0a020d0, 0xf0608020905040a0, 0xe0c0104020b08050, 0x0b0401060908030d, 0x0d0c020a0b090407, 0x0a0904050602080f, 0x0502080b0c04010e, 0xb0401060908030d0, 0xd0c020a0b0904070, 0xa0904050602080f0, 0x502080b0c04010e0]
# 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: 64 inputs, 64 outputs, 364 gates (364 XOR)
# Depth: 11

Inputs: x1:x64
Outputs: y1:y64
Internal: t1:t300
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 x3 x28
XOR t2 x51 x60
XOR t3 x19 x44
XOR t4 x11 x36
XOR t5 x20 x43
XOR t6 x52 x59
XOR t7 x12 x35
XOR t8 x4 x27
XOR t9 x56 x63
XOR t10 x16 x39
XOR t11 x24 x47
XOR t12 x8 x31
XOR t13 x7 x32
XOR t14 x23 x48
XOR t15 x15 x40
XOR t16 x55 x64
XOR t17 x5 x45
XOR t18 x13 x61
XOR t19 x33 x49
XOR t20 x17 x25
XOR t21 x21 x29
XOR t22 x37 x53
XOR t23 x9 x57
XOR t24 x1 x41
XOR t25 x38 x54
XOR t26 x10 x58
XOR t27 x14 x62
XOR t28 x34 x50
XOR t29 x18 x26
XOR t30 x6 x46
XOR t31 x22 x30
XOR t32 x2 x42
XOR t33 t9 t30
XOR t34 t15 t33
XOR t35 t6 t32
XOR t36 t4 t35
XOR t37 t10 t31
XOR t38 t16 t37
XOR t39 t5 t26
XOR t40 t1 t39
XOR t41 t12 t25
XOR t42 t14 t41
XOR t43 t7 t29
XOR t44 t2 t43
XOR t45 t3 t28
XOR t46 t8 t45
XOR t47 t13 t27
XOR t48 t11 t47
XOR t49 t21 t34
XOR t50 t23 t46
XOR t51 t17 t38
XOR t52 t18 t42
XOR t53 t19 t40
XOR t54 t20 t36
XOR t55 t24 t44
XOR t56 t22 t48
XOR t57 x7 t51
XOR t58 x3 t55
XOR t59 x35 t53
XOR t60 x63 t52
XOR t61 x14 x46
XOR t62 x11 t50
XOR t63 x19 t54
XOR t64 x26 x50
XOR t65 x4 x34
XOR t66 x43 t59
XOR t67 x23 t49
XOR t68 x55 t56
XOR t69 x24 x62
XOR t70 x31 t60
XOR t71 t63 t65
XOR t72 t57 t69
XOR t73 x18 x60
XOR t74 t59 t73
XOR t75 x41 t45
XOR t76 x6 x40
XOR t77 t60 t76
XOR t78 x9 t43
XOR t79 x45 t49
XOR t80 x13 x30
XOR t81 x25 t55
XOR t82 x42 x49
XOR t83 x5 x38
XOR t84 x53 t33
XOR t85 x17 x58
XOR t86 x61 t56
XOR t87 x33 t50
XOR t88 x29 t47
XOR t89 x44 t73
XOR t90 x32 t76
XOR t91 x48 t84
XOR t92 x52 t75
XOR t93 x16 t88
XOR t94 x28 t78
XOR t95 x1 x36
XOR t96 x21 x64
XOR t97 t2 t8
XOR t98 t11 t15
XOR t99 x22 t86
XOR t100 t10 t67
XOR t101 x54 t79
XOR t102 t12 t68
XOR t103 x10 t81
XOR t104 t6 t58
XOR t105 x2 t87
XOR t106 t5 t62
XOR t107 t53 t64
XOR t108 t52 t61
XOR t109 t18 t22
XOR t110 t33 t70
XOR t111 x39 t14
XOR t112 x59 t1
XOR t113 t19 t23
XOR t114 t43 t66
XOR t115 x49 t89
XOR t116 x13 t90
XOR t117 t24 t36
XOR t118 t21 t38
XOR t119 t16 t49
XOR t120 t4 t55
XOR t121 x4 x33
XOR t122 x2 x58
XOR t123 x42 t3
XOR t124 x24 x61
XOR t125 x22 x38
XOR t126 t67 t109
XOR t127 t93 t125
XOR t128 t58 t113
XOR t129 t92 t122
XOR t130 x30 t13
XOR t131 x12 x25
XOR t132 t51 t61
XOR t133 x20 t54
XOR t134 t64 t133
XOR t135 t1 t2
XOR t136 x57 t135
XOR t137 x10 t95
XOR t138 x45 x56
XOR t139 t23 t63
XOR t140 x54 t96
XOR t141 t14 t15
XOR t142 t22 t57
XOR t143 x37 t141
XOR t144 t20 t122
XOR t145 t94 t144
XOR t146 t91 t125
XOR t147 t17 t146
XOR t148 x59 t145
XOR t149 t62 t148
XOR t150 x28 t139
XOR t151 x39 t68
XOR t152 x30 t17
XOR t153 x64 t99
XOR y16 t111 t153
XOR t154 t83 t100
XOR y24 x8 t154
XOR t155 x27 t149
XOR y51 t44 t155
XOR t156 t72 t88
XOR y32 t98 t156
XOR t157 t74 t97
XOR y44 t78 t157
XOR t158 x52 t82
XOR y36 t106 t158
XOR t159 x21 t72
XOR y56 t9 t159
XOR t160 x16 t80
XOR y48 t102 t160
XOR t161 x37 t77
XOR y64 t13 t161
XOR t162 t105 t112
XOR y60 x36 t162
XOR t163 t77 t84
XOR y40 t98 t163
XOR t164 x57 t3
XOR y12 t74 t164
XOR t165 x1 t7
XOR y20 t71 t165
XOR t166 t75 t97
XOR y4 t71 t166
XOR t167 t85 t104
XOR y52 x20 t167
XOR t168 x53 t93
XOR t169 t16 t168
XOR y6 t108 t169
XOR t170 t89 t128
XOR t171 x17 t107
XOR y33 t170 t171
XOR t172 x60 t53
XOR t173 x43 t94
XOR t174 x41 t134
XOR y34 t173 t174
XOR t175 t34 t147
XOR t176 x47 t151
XOR y23 t175 t176
XOR t177 t4 t78
XOR t178 t103 t177
XOR y28 t173 t178
XOR t179 t110 t119
XOR t180 x62 t179
XOR y55 t116 t180
XOR t181 x9 t107
XOR t182 t4 t181
XOR y26 t92 t182
XOR t183 t69 t110
XOR t184 t79 t183
XOR y13 t109 t184
XOR t185 x48 t16
XOR t186 x31 t101
XOR y8 t185 t186
XOR t187 t85 t120
XOR t188 t121 t123
XOR y10 t187 t188
XOR t189 t12 t132
XOR t190 x29 t91
XOR y46 t189 t190
XOR t191 x31 t126
XOR t192 t105 t150
XOR t193 t137 t192
XOR y41 t82 t193
XOR t194 t28 t174
XOR t195 t24 t136
XOR y58 t194 t195
XOR t196 t115 t117
XOR t197 t62 t196
XOR y49 t28 t197
XOR t198 x36 t172
XOR t199 x10 t198
XOR y17 t145 t199
XOR t200 t29 t149
XOR t201 t115 t120
XOR t202 x34 t114
XOR y19 t201 t202
XOR t203 x5 t108
XOR t204 x40 t52
XOR t205 t90 t203
XOR y45 t126 t205
XOR t206 t27 y46
XOR t207 t191 t206
XOR y14 t18 t207
XOR t208 x4 t113
XOR t209 t202 t208
XOR y57 t81 t209
XOR t210 x21 t204
XOR t211 t140 t210
XOR y53 t147 t211
XOR t212 t121 t129
XOR t213 t82 t212
XOR y9 t133 t213
XOR t214 x15 t56
XOR t215 t127 t191
XOR y15 t214 t215
XOR t216 t27 t68
XOR t217 t116 t118
XOR y21 t216 t217
XOR t218 t83 t124
XOR t219 t130 t218
XOR y62 t119 t219
XOR t220 t128 t129
XOR t221 x43 t50
XOR t222 x51 t221
XOR y59 t220 t222
XOR t223 t32 t150
XOR t224 t26 t133
XOR t225 t200 t224
XOR y27 t223 t225
XOR t226 t50 t82
XOR t227 t135 t226
XOR t228 t131 t227
XOR y2 x58 t228
XOR t229 t112 t172
XOR t230 x27 t139
XOR t231 t171 t229
XOR y43 t230 t231
XOR t232 x18 t71
XOR t233 t131 t232
XOR t234 t106 t233
XOR y11 t45 t234
XOR t235 t11 t80
XOR t236 x32 t37
XOR t237 t235 t236
XOR y38 t101 t237
XOR t238 x44 t82
XOR t239 t35 t103
XOR t240 t8 t238
XOR y42 t239 t240
XOR t241 t22 t140
XOR t242 t130 t241
XOR t243 x63 t191
XOR y47 t242 t243
XOR t244 x41 y26
XOR t245 t145 t200
XOR t246 x1 t245
XOR y50 t244 t246
XOR t247 t77 t218
XOR t248 t154 t247
XOR t249 x14 t9
XOR y31 t248 t249
XOR t250 t56 t80
XOR t251 x38 t250
XOR t252 t141 t251
XOR y30 t138 t252
XOR t253 x48 t140
XOR t254 t99 t253
XOR t255 t80 t254
XOR y37 t142 t255
XOR t256 t9 t83
XOR t257 t41 t256
XOR t258 x40 t257
XOR y54 t99 t258
XOR t259 x50 t121
XOR t260 t74 t259
XOR t261 t7 t260
XOR y3 t104 t261
XOR t262 x47 t204
XOR t263 t142 t203
XOR t264 t262 t263
XOR y39 t111 t264
XOR t265 x60 t85
XOR t266 t7 t39
XOR t267 t265 t266
XOR y18 t105 t267
XOR t268 t47 t102
XOR t269 x6 t268
XOR t270 t138 t269
XOR y63 t72 t270
XOR t271 x8 t80
XOR t272 t51 t124
XOR t273 t127 t272
XOR y61 t271 t273
XOR t274 t42 t152
XOR t275 t143 t274
XOR t276 x16 t275
XOR y29 t110 t276
XOR t277 t66 t137
XOR t278 t58 t123
XOR t279 t40 t278
XOR y35 t277 t279
XOR t280 x56 t61
XOR t281 t69 t280
XOR t282 t118 t281
XOR t283 x39 t86
XOR y5 t282 t283
XOR t284 t96 t108
XOR t285 t11 t30
XOR t286 x37 t10
XOR t287 t285 t286
XOR y22 t284 t287
XOR t288 t53 t136
XOR t289 t20 t114
XOR t290 x33 t288
XOR t291 t289 t290
XOR y1 t158 t291
XOR t292 x59 t64
XOR t293 t87 t292
XOR t294 x12 t293
XOR t295 t65 t294
XOR y25 t117 t295
XOR t296 t151 t256
XOR t297 x5 x7
XOR t298 t15 t296
XOR t299 x31 t297
XOR t300 t275 t299
XOR y7 t298 t300
end SLP
end circuit