CMT16.txt : Multiplication circuit for binary polynomials of degree 15.

Date: July 2011.

input polynomials are A = f0 + f1*X + f2*X^2 + ... + f15*X^15 and B = g0 + g1*X + g2*X^2 + ... + g15*X^15.

output polynomial is the product A*B = h0 + h1*X + h2*X^2 + ... + h30*X^30.
Coefficients are over GF2.

Size : 349
Depth : 8

SLP:

h30 = f15 x g15
t2 = f15 x g12
t3 = f15 x g13
t4 = f15 x g14
t5 = f12 x g15
t6 = f13 x g15
t7 = f14 x g15
t8 = f14 x g14
t9 = f14 x g12
t10 = f14 x g13
t11 = f12 x g14
t12 = f13 x g14
t13 = f13 x g13
t14 = f13 x g12
t15 = f12 x g13
t16 = f12 x g12
t26 = f11 x g11
t27 = f11 x g8
t28 = f11 x g9
t29 = f11 x g10
t30 = f8 x g11
t31 = f9 x g11
t32 = f10 x g11
t33 = f10 x g10
t34 = f10 x g8
t35 = f10 x g9
t36 = f8 x g10
t37 = f9 x g10
t38 = f9 x g9
t39 = f9 x g8
t40 = f8 x g9
t41 = f8 x g8
t51 = f7 x g7
t52 = f7 x g4
t53 = f7 x g5
t54 = f7 x g6
t55 = f4 x g7
t56 = f5 x g7
t57 = f6 x g7
t58 = f6 x g6
t59 = f6 x g4
t60 = f6 x g5
t61 = f4 x g6
t62 = f5 x g6
t63 = f5 x g5
t64 = f5 x g4
t65 = f4 x g5
t66 = f4 x g4
t76 = f3 x g3
t77 = f3 x g0
t78 = f3 x g1
t79 = f3 x g2
t80 = f0 x g3
t81 = f1 x g3
t82 = f2 x g3
t83 = f2 x g2
t84 = f2 x g0
t85 = f2 x g1
t86 = f0 x g2
t87 = f1 x g2
t88 = f1 x g1
t89 = f1 x g0
t90 = f0 x g1
h0 = f0 x g0
t110 = g8 + g12
t111 = g9 + g13
t112 = g10 + g14
t113 = g11 + g15
t114 = f8 + f12
t115 = f9 + f13
t116 = f10 + f14
t117 = f11 + f15
t118 = t117 x t113
t119 = t117 x t110
t120 = t117 x t111
t121 = t117 x t112
t122 = t114 x t113
t123 = t115 x t113
t124 = t116 x t113
t125 = t116 x t112
t126 = t116 x t110
t127 = t116 x t111
t128 = t114 x t112
t129 = t115 x t112
t130 = t115 x t111
t131 = t115 x t110
t132 = t114 x t111
t133 = t114 x t110
t143 = g0 + g4
t144 = g1 + g5
t145 = g2 + g6
t146 = g3 + g7
t147 = f0 + f4
t148 = f1 + f5
t149 = f2 + f6
t150 = f3 + f7
t151 = t150 x t146
t152 = t150 x t143
t153 = t150 x t144
t154 = t150 x t145
t155 = t147 x t146
t156 = t148 x t146
t157 = t149 x t146
t158 = t149 x t145
t159 = t149 x t143
t160 = t149 x t144
t161 = t147 x t145
t162 = t148 x t145
t163 = t148 x t144
t164 = t148 x t143
t165 = t147 x t144
t166 = t147 x t143
t205 = g4 + g12
t206 = g5 + g13
t207 = g6 + g14
t208 = g7 + g15
t209 = g0 + g8
t210 = g1 + g9
t211 = g2 + g10
t212 = g3 + g11
t213 = f4 + f12
t214 = f5 + f13
t215 = f6 + f14
t216 = f7 + f15
t217 = f0 + f8
t218 = f1 + f9
t219 = f2 + f10
t220 = f3 + f11
t221 = t220 x t212
t222 = t220 x t209
t223 = t220 x t210
t224 = t220 x t211
t225 = t217 x t212
t226 = t218 x t212
t227 = t219 x t212
t228 = t219 x t211
t229 = t219 x t209
t230 = t219 x t210
t231 = t217 x t211
t232 = t218 x t211
t233 = t218 x t210
t234 = t218 x t209
t235 = t217 x t210
t236 = t217 x t209
t246 = t216 x t208
t247 = t216 x t205
t248 = t216 x t206
t249 = t216 x t207
t250 = t213 x t208
t251 = t214 x t208
t252 = t215 x t208
t253 = t215 x t207
t254 = t215 x t205
t255 = t215 x t206
t256 = t213 x t207
t257 = t214 x t207
t258 = t214 x t206
t259 = t214 x t205
t260 = t213 x t206
t261 = t213 x t205
t271 = t209 + t205
t272 = t210 + t206
t273 = t211 + t207
t274 = t212 + t208
t275 = t217 + t213
t276 = t218 + t214
t277 = t219 + t215
t278 = t220 + t216
t279 = t278 x t274
t280 = t278 x t271
t281 = t278 x t272
t282 = t278 x t273
t283 = t275 x t274
t284 = t276 x t274
t285 = t277 x t274
t286 = t277 x t273
t287 = t277 x t271
t288 = t277 x t272
t289 = t275 x t273
t290 = t276 x t273
t291 = t276 x t272
t292 = t276 x t271
t293 = t275 x t272
t294 = t275 x t271
T1R1 = t120 + t123
T1R2 = t153 + t156
T1R3 = t16 + t28
T1R4 = t223 + t226
T1R5 = t228 + t261
T1R6 = t248 + t251
T1R7 = t281 + t284
T1R8 = t3 + t6
T1R9 = t31 + t33
T1R10 = t41 + t53
T1R11 = t56 + t58
T1R12 = t66 + t78
T1R13 = t81 + t83
T1R14 = T1R1 + t125
T1R15 = T1R10 + T1R11
T1R16 = T1R12 + T1R13
T1R17 = T1R2 + t158
T1R18 = T1R3 + T1R9
T1R19 = T1R4 + T1R5
T1R20 = T1R6 + t253
T1R21 = T1R7 + t286
h28 = T1R8 + t8
X1X12 = T1R16 + h0
h4 = t166 + X1X12
X1X14 = T1R18 + h28
h24 = T1R14 + X1X14
X1X16 = T1R15 + T1R17
X1X17 = T1R15 + t133
X1X18 = T1R20 + X1X14
h20 = X1X17 + X1X18
X1X20 = t236 + X1X12
h8 = X1X16 + X1X20
X1X22 = T1R14 + T1R16
X1X23 = T1R19 + X1X16
X1X24 = X1X18 + X1X22
X1X25 = X1X23 + X1X24
X1X26 = T1R18 + T1R19
X1X27 = t166 + t294
X1X28 = X1X20 + X1X26
X1X29 = X1X27 + X1X17
h12 = X1X29 + X1X28
h16 = X1X25 + T1R21
T2R1 = t121 + t124
T2R2 = t131 + t132
T2R3 = t14 + t15
T2R4 = t154 + t157
T2R5 = t164 + t165
T2R6 = t224 + t227
T2R7 = t234 + t235
T2R8 = t249 + t252
T2R9 = t259 + t260
T2R10 = t282 + t285
T2R11 = t29 + t32
T2R12 = t292 + t293
T2R13 = t39 + t40
h29 = t4 + t7
T2R15 = t54 + t57
T2R16 = t64 + t65
T2R17 = t79 + t82
h1 = t89 + t90
T2R19 = T2R11 + T2R3
T2R20 = T2R13 + T2R15
T2R21 = T2R16 + T2R17
T2R22 = T2R6 + T2R9
X2X12 = h29 + T2R19
h25 = T2R1 + X2X12
X2X14 = h1 + T2R21
h5 = T2R5 + X2X14
X2X16 = T2R2 + T2R20
X2X17 = T2R20 + T2R4
X2X18 = T2R7 + X2X14
h9 = X2X17 + X2X18
X2X20 = T2R8 + X2X12
h21 = X2X16 + X2X20
X2X22 = T2R1 + T2R21
X2X23 = T2R22 + X2X17
X2X24 = X2X20 + X2X22
X2X25 = X2X23 + T2R10
X2X26 = T2R19 + T2R22
X2X27 = T2R5 + X2X16
X2X28 = X2X18 + X2X26
X2X29 = X2X27 + T2R12
h17 = X2X25 + X2X24
h13 = X2X29 + X2X28
T3R1 = t11 + t13
T3R2 = t126 + t128
T3R3 = t159 + t161
T3R4 = t221 + t254
T3R5 = t229 + t231
T3R6 = t256 + t258
T3R7 = t26 + t9
T3R8 = t287 + t289
T3R9 = t34 + t36
T3R10 = t38 + t51
T3R11 = t59 + t61
T3R12 = t63 + t76
T3R13 = t84 + t86
T3R14 = T3R1 + T3R7
T3R15 = T3R10 + T3R9
T3R16 = T3R11 + T3R12
h2 = T3R13 + t88
T3R18 = T3R2 + t130
T3R19 = T3R3 + t163
T3R20 = T3R4 + T3R6
T3R21 = T3R5 + t233
T3R22 = T3R8 + t291
X3X12 = T3R14 + h30
h26 = t118 + X3X12
X3X14 = T3R16 + h2
h6 = T3R19 + X3X14
X3X16 = T3R15 + T3R18
X3X17 = T3R15 + t151
X3X18 = T3R21 + X3X14
h10 = X3X17 + X3X18
X3X20 = t246 + X3X12
h22 = X3X16 + X3X20
X3X22 = T3R14 + T3R19
X3X23 = T3R20 + X3X16
X3X24 = X3X18 + X3X22
X3X25 = X3X23 + X3X24
X3X26 = T3R16 + T3R20
X3X27 = t118 + t279
X3X28 = X3X20 + X3X26
X3X29 = X3X27 + X3X17
h14 = X3X25 + T3R22
h18 = X3X29 + X3X28
T4R1 = t10 + t12
T4R2 = t119 + t122
T4R3 = t127 + t129
T4R4 = t152 + t155
T4R5 = t160 + t162
T4R6 = t2 + t5
T4R7 = t222 + t225
T4R8 = t230 + t232
T4R9 = t247 + t250
T4R10 = t255 + t257
T4R11 = t27 + t30
T4R12 = t280 + t283
T4R13 = t288 + t290
T4R14 = t35 + t37
T4R15 = t52 + t55
T4R16 = t60 + t62
T4R17 = t77 + t80
T4R18 = t85 + t87
h27 = T4R1 + T4R6
T4R20 = T4R10 + T4R9
T4R21 = T4R11 + T4R14
T4R22 = T4R12 + T4R13
T4R23 = T4R15 + T4R16
h3 = T4R17 + T4R18
T4R25 = T4R2 + T4R3
T4R26 = T4R4 + T4R5
T4R27 = T4R7 + T4R8
X4X8 = h27 + T4R21
h23 = T4R25 + X4X8
X4X10 = T4R23 + h3
h7 = T4R26 + X4X10
X4X12 = T4R20 + T4R23
h19 = X4X8 + X4X12
X4X14 = T4R21 + T4R27
h11 = X4X10 + X4X14
X4X16 = T4R20 + T4R27
X4X17 = h23 + h7
X4X18 = X4X16 + T4R22
h15 = X4X18 + X4X17