\\ (C) 2007 Marco Bodrato \\ This code is released under the GNU-GPL 2.0 licence. U0=u0*Mod(1,2);U1=u1*Mod(1,2);U2=u2*Mod(1,2);U3=u3*Mod(1,2); V0=v0*Mod(1,2);V1=v1*Mod(1,2);V2=v2*Mod(1,2);V3=v3*Mod(1,2); U = U3*Y^3 + U2*Y^2*X + U1*Y*X^2 + U0*X^3 V = V3*Y^3 + V2*Y^2*X + V1*Y*X^2 + V0*X^3 \\ P(X,Y): P0=(1,0); P1=(x+1,1); P2=(x,1); P3=(1,1); P4=(1,x); P5=(1,x+1); P6=(0,1) \\Evaluation phase: 13*2 add, 7*2 shift, 2Smul; 7 mul (n) W1 = U0 + U1 + U2 + U3 ; W2 = V0 + V1 + V2 + V3 W0 = U1 +(U2 + U3*x)*x ; W6 = V1 +(V2 + V3*x)*x W4 = W1 +(W0 + U3*(x+1))*x; W3 = W2 +(W6 + V3*(x+1))*x W0 = W0*x + U0 ; W6 = W6*x + V0 W5 = W4 * W3 ; W4 = W0 * W6 W3 = W1 * W2 W0 =(U2 +(U1 + U0*x)*x)*x ; W6 =(V2 +(V1 + V0*x)*x)*x W1 = W1 + W0 + U0*(x^2+x) ; W2 = W2 + W6 + V0*(x^2+x) W0 = W0 + U3 ; W6 = W6 + V3 W1 = W1 * W2 ; W2 = W0 * W6 W6 = U3 * V3 ; W0 = U0 * V0 \\Interpolation: 22 add, 4 shift, 5 Smul, 4 div (2n) d1=(x^4+x)*Mod(1,2) ; d1== (x)^1*(x+1)^1*(x^2+x+1)^1 *Mod(1,2) d2=(x^4+x^2)*Mod(1,2) ; d2== (x)^2*(x+1)^2*(x^2+x+1)^0 *Mod(1,2) W1 = W1 + W2 + W0*(x^4+x^2+1) W5 =(W5 + W4 + W1 + W6*(x^4+x^2+1))/d1 W2 = W2 + W6 + W0*(x^6) W4 = W4 + W2 + W0 + W6*(x^6) W4 =(W4 + W5*(x^5+x))/d2 W3 = W3 + W0 + W6 W1 = W1 + W3 W2 = W2 +(W1 + W3*x)*x W3 = W3 + W4 + W5 W1 =(W1 + W3*(x^2+x))/d1 W5 = W5 + W1 W2 =(W2 + W5*(x^2+x))/d2 W4 = W4 + W2 \\Recomposition W = W6*Y^6 + W5*Y^5*X + W4*Y^4*X^2+ W3*Y^3*X^3+ W2*Y^2*X^4+ W1*Y*X^5 + W0*X^6 W == U*V \\ Reference: http://bodrato.it/papers/#WAIFI2007 \\ Marco BODRATO,"Towards Optimal Toom-Cook Multiplication for \\ Univariate and Multivariate Polynomials in Characteristic 2 \\ and 0"; "WAIFI'07 proceedings" (C.Carlet and B.Sunar, eds.) \\ LNCS#4547, Springer, Madrid, Spain, June 2007, pp. 116-133.