# File timestamp (UTC): 2021-02-22T06:50:58.855
# NIST Circuit Complexity Project
# https://csrc.nist.gov/projects/circuit-complexity

begin circuit LS16-8x8-GF256--rs=7

# Boolean Circuit for a linear system y = A.x defined by a 64x64 bit-matrix A
# Matrix A weights (W): totalW=752, adjW=688, minWInRow=9, maxWInRow=16, minWInCol=9, maxWICol=14
# Matrix represented as 64 rows: vecRows=UInt64[0x0102e108e001a901, 0x0204011003029102, 0x040802200604e104, 0x081004400c080108, 0x1020088018100210, 0x204010c330200420, 0x4080204560400840, 0x80c3408ac0801080, 0x02e108e001a90101, 0x0401100302910202, 0x0802200604e10404, 0x1004400c08010808, 0x2008801810021010, 0x4010c33020042020, 0x8020456040084040, 0xc3408ac080108080, 0xe108e001a9010102, 0x0110030291020204, 0x02200604e1040408, 0x04400c0801080810, 0x0880181002101020, 0x10c3302004202040, 0x2045604008404080, 0x408ac080108080c3, 0x08e001a9010102e1, 0x1003029102020401, 0x200604e104040802, 0x400c080108081004, 0x8018100210102008, 0xc330200420204010, 0x4560400840408020, 0x8ac080108080c340, 0xe001a9010102e108, 0x0302910202040110, 0x0604e10404080220, 0x0c08010808100440, 0x1810021010200880, 0x30200420204010c3, 0x6040084040802045, 0xc080108080c3408a, 0x01a9010102e108e0, 0x0291020204011003, 0x04e1040408022006, 0x080108081004400c, 0x1002101020088018, 0x200420204010c330, 0x4008404080204560, 0x80108080c3408ac0, 0xa9010102e108e001, 0x9102020401100302, 0xe104040802200604, 0x0108081004400c08, 0x0210102008801810, 0x0420204010c33020, 0x0840408020456040, 0x108080c3408ac080, 0x010102e108e001a9, 0x0202040110030291, 0x04040802200604e1, 0x08081004400c0801, 0x1010200880181002, 0x20204010c3302004, 0x4040802045604008, 0x8080c3408ac08010]
# Matrix represented as 64 columns: vecCols=UInt64[0x0f01026003800101, 0x100206a004810202, 0x20040c4008020404, 0x4108188110040808, 0x8210300220081010, 0x0520610441102020, 0x0440c16881a04040, 0x078081b001c08080, 0x010260038001010f, 0x0206a00481020210, 0x040c400802040420, 0x0818811004080841, 0x1030022008101082, 0x2061044110202005, 0x40c16881a0404004, 0x8081b001c0808007, 0x0260038001010f01, 0x06a0048102021002, 0x0c40080204042004, 0x1881100408084108, 0x3002200810108210, 0x6104411020200520, 0xc16881a040400440, 0x81b001c080800780, 0x60038001010f0102, 0xa004810202100206, 0x400802040420040c, 0x8110040808410818, 0x0220081010821030, 0x0441102020052061, 0x6881a040400440c1, 0xb001c08080078081, 0x038001010f010260, 0x04810202100206a0, 0x0802040420040c40, 0x1004080841081881, 0x2008101082103002, 0x4110202005206104, 0x81a040400440c168, 0x01c08080078081b0, 0x8001010f01026003, 0x810202100206a004, 0x02040420040c4008, 0x0408084108188110, 0x0810108210300220, 0x1020200520610441, 0xa040400440c16881, 0xc08080078081b001, 0x01010f0102600380, 0x0202100206a00481, 0x040420040c400802, 0x0808410818811004, 0x1010821030022008, 0x2020052061044110, 0x40400440c16881a0, 0x8080078081b001c0, 0x010f010260038001, 0x02100206a0048102, 0x0420040c40080204, 0x0841081881100408, 0x1082103002200810, 0x2005206104411020, 0x400440c16881a040, 0x80078081b001c080]
# 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, 427 gates (427 XOR)
# Depth: 9

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