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

begin circuit M-8x8-GF256-inv--rs=21

# Boolean Circuit for a linear system y = A.x defined by a 64x64 bit-matrix A
# Matrix A weights (W): totalW=1144, adjW=1080, minWInRow=15, maxWInRow=21, minWInCol=15, maxWICol=21
# Matrix represented as 64 rows: vecRows=UInt64[0x0a0c0b0e0107090d, 0x070b050f020e0109, 0x0e050a0d040f0201, 0x0f0a0709080d0402, 0xa0c0b0e0107090d0, 0x70b050f020e01090, 0xe050a0d040f02010, 0xf0a0709080d04020, 0x0e020c09060c0b09, 0x0f040b010c0b0501, 0x0d0805020b050a02, 0x09030a04050a0704, 0xe020c09060c0b090, 0xf040b010c0b05010, 0xd0805020b050a020, 0x9030a04050a07040, 0x0a06010604050c07, 0x070c020c080a0b0e, 0x0e0b040b0307050f, 0x0f050805060e0a0d, 0xa06010604050c070, 0x70c020c080a0b0e0, 0xe0b040b0307050f0, 0xf050805060e0a0d0, 0x060c070a05040601, 0x0c0b0e070a080c02, 0x0b050f0e07030b04, 0x050a0d0f0e060508, 0x60c070a050406010, 0xc0b0e070a080c020, 0xb050f0e07030b040, 0x50a0d0f0e0605080, 0x0d0e0a030a06090e, 0x090f0706070c010f, 0x010d0e0c0e0b020d, 0x02090f0b0f050409, 0xd0e0a030a06090e0, 0x90f0706070c010f0, 0x10d0e0c0e0b020d0, 0x2090f0b0f0504090, 0x0e090d0a07010c0b, 0x0f0109070e020b05, 0x0d02010e0f04050a, 0x0904020f0d080a07, 0xe090d0a07010c0b0, 0xf0109070e020b050, 0xd02010e0f04050a0, 0x904020f0d080a070, 0x090b090e0c06020c, 0x0105010f0b0c040b, 0x020a020d050b0805, 0x040704090a05030a, 0x90b090e0c06020c0, 0x105010f0b0c040b0, 0x20a020d050b08050, 0x40704090a05030a0, 0x03090e0d060a0e0a, 0x06010f090c070f07, 0x0c020d010b0e0d0e, 0x0b040902050f090f, 0x3090e0d060a0e0a0, 0x6010f090c070f070, 0xc020d010b0e0d0e0, 0xb040902050f090f0]
# Matrix represented as 64 columns: vecCols=UInt64[0x0a060b0e010d0307, 0x0f0a0d0302070408, 0x0e050a07040f0801, 0x0d0b050f080e0103, 0xa060b0e010d03070, 0xf0a0d03020704080, 0xe050a07040f08010, 0xd0b050f080e01030, 0x0e0806030c060b03, 0x03090a04050a0d04, 0x070205080b050a08, 0x0f040b01060b0501, 0xe0806030c060b030, 0x3090a04050a0d040, 0x70205080b050a080, 0xf040b01060b05010, 0x0a0c010c0405060d, 0x0f0502050c0e0a07, 0x0e0b040b090d050f, 0x0d060806020a0b0e, 0xa0c010c0405060d0, 0xf0502050c0e0a070, 0xe0b040b090d050f0, 0xd060806020a0b0e0, 0x0c060d0a05040c01, 0x050a070f0e0c0502, 0x0b050f0e0d090b04, 0x060b0e0d0a020608, 0xc060d0a05040c010, 0x50a070f0e0c05020, 0xb050f0e0d090b040, 0x60b0e0d0a0206080, 0x070e0a090a0c030e, 0x08030f0b0f050403, 0x01070e060e0b0807, 0x030f0d0c0d06010f, 0x70e0a090a0c030e0, 0x8030f0b0f0504030, 0x1070e060e0b08070, 0x30f0d0c0d06010f0, 0x0e03070a0d01060b, 0x0304080f07020a0d, 0x0708010e0f04050a, 0x0f01030d0e080b05, 0xe03070a0d01060b0, 0x304080f07020a0d0, 0x708010e0f04050a0, 0xf01030d0e080b050, 0x030b030e060c0806, 0x040d04030a05090a, 0x080a0807050b0205, 0x0105010f0b06040b, 0x30b030e060c08060, 0x40d04030a05090a0, 0x80a0807050b02050, 0x105010f0b06040b0, 0x09030e070c0a0e0a, 0x0b040308050f030f, 0x060807010b0e070e, 0x0c010f03060d0f0d, 0x9030e070c0a0e0a0, 0xb040308050f030f0, 0x60807010b0e070e0, 0xc010f03060d0f0d0]
# 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, 368 gates (368 XOR)
# Depth: 12

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