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

begin circuit SS17-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=744, adjW=680, minWInRow=9, maxWInRow=18, minWInCol=9, maxWICol=16
# Matrix represented as 64 rows: vecRows=UInt64[0x0204e102e1910601, 0x0408010401e10c02, 0x0810020802011804, 0x1020041004023008, 0x2040082008046010, 0x408010401008c020, 0x80c3208020104340, 0xc34540c340208680, 0x04e102e191060101, 0x08010401e10c0202, 0x1002080201180404, 0x2004100402300808, 0x4008200804601010, 0x8010401008c02020, 0xc320802010434040, 0x4540c34020868080, 0xe102e19106010102, 0x010401e10c020204, 0x0208020118040408, 0x0410040230080810, 0x0820080460101020, 0x10401008c0202040, 0x2080201043404080, 0x40c34020868080c3, 0x02e1910601010291, 0x0401e10c020204e1, 0x0802011804040801, 0x1004023008081002, 0x2008046010102004, 0x401008c020204008, 0x8020104340408010, 0xc34020868080c320, 0xe191060101029101, 0x01e10c020204e102, 0x0201180404080104, 0x0402300808100208, 0x0804601010200410, 0x1008c02020400820, 0x2010434040801040, 0x4020868080c32080, 0x9106010102910191, 0xe10c020204e102e1, 0x0118040408010401, 0x0230080810020802, 0x0460101020041004, 0x08c0202040082008, 0x1043404080104010, 0x20868080c3208020, 0x06010102910191a9, 0x0c020204e102e191, 0x18040408010401e1, 0x3008081002080201, 0x6010102004100402, 0xc020204008200804, 0x4340408010401008, 0x868080c320802010, 0x010102910191a903, 0x020204e102e19106, 0x040408010401e10c, 0x0808100208020118, 0x1010200410040230, 0x2020400820080460, 0x40408010401008c0, 0x8080c32080201043]
# Matrix represented as 64 columns: vecCols=UInt64[0x810f070107800101, 0x8310080208810202, 0x0620100410020404, 0x0c41200820040808, 0x1882411041081010, 0x3005822082102020, 0xe004024002a04040, 0x4007038003c08080, 0x0f07010780010140, 0x10080208810202c1, 0x2010041002040483, 0x4120082004080806, 0x824110410810100c, 0x0582208210202018, 0x04024002a0404070, 0x07038003c08080a0, 0x0701078001014007, 0x080208810202c108, 0x1004100204048310, 0x2008200408080620, 0x4110410810100c41, 0x8220821020201882, 0x024002a040407002, 0x038003c08080a003, 0x0107800101400703, 0x0208810202c10804, 0x0410020404831008, 0x0820040808062010, 0x10410810100c4120, 0x2082102020188241, 0x4002a04040700281, 0x8003c08080a00301, 0x0780010140070380, 0x08810202c1080481, 0x1002040483100802, 0x2004080806201004, 0x410810100c412008, 0x8210202018824110, 0x02a04040700281a0, 0x03c08080a00301c0, 0x8001014007038003, 0x810202c108048104, 0x0204048310080208, 0x0408080620100410, 0x0810100c41200820, 0x1020201882411041, 0xa04040700281a081, 0xc08080a00301c001, 0x01014007038003c0, 0x0202c10804810440, 0x0404831008020881, 0x0808062010041002, 0x10100c4120082004, 0x2020188241104108, 0x4040700281a081d0, 0x8080a00301c00160, 0x014007038003c080, 0x02c1080481044081, 0x0483100802088102, 0x0806201004100204, 0x100c412008200408, 0x2018824110410810, 0x40700281a081d0a0, 0x80a00301c00160c0]
# 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, 418 gates (418 XOR)
# Depth: 9

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