Polynomials & Matrices

¡EPolynomial:    P(x)=X4+4X3+3X+1
array:    P[0...4]=[1,3,0,4,1]            P[i]¡ö¡÷PiXi

¡EMatrix:
array:    M[i,j]¡ö¡÷Mij

Polynomials    p(x)=anxn+...+a1x+a0

x1                 y=p(x1)
x2     p(x)      y=p(x2)
¡G    ¡X¡÷      ¡G
¡G                  ¡G
xN                 y=p(xN)

¡Ecompute    y:    evaluation
p:    interpolation
x:    find root    :Newton's method...

Evaluation    y=p(x)=2x4+3x3-6x2+2x+1
¡EBrute-force:
2x4, 3x3, (-6)x2, ...    "*": 4+3+2+1=N(N+1)/2
(x4+3x3)+...                 "+": 4             =N

problems:    x3, x4 ­«½Æ­pºâ

¡EHorner's rule:
p(x)=x*(x*(x*(x*2+3)-6)+2)+1    :4"*"+4"+"

¡EFFT(Fast Fourier Transforms in Chap.41)
can evaluate at N points with NlogN "*"

¡EXN only :

X55 =X[ 1 1 0 1 1 1] 2
=X32 * X16 * X4 * X2 * X1
=X2^5+2^4+0*2^3+2^2+2^1+1
=X((((1*2+1)*2+0)*2+1)*2+1)*2+1
=(((((12 * X)2  * X)2 *1 )2 *X )2 *X)2 *X

55=[   1 , 1 , 0 , 1 ,1 , 1  ] 2
Xa*b =( Xa )b
Xa+b  =Xa* Xb

Interpolation    :p(x)=?
such that p(x1)=y1, ... , p(xN)=yN

¡ELagrange method:

Example:    p(1)=3, p(2)=7, p(3)=13
p(x)=3*(x-2)(x-3)     +    7*(x-1)(x-3)     +    13*(x-1)(x-2)
(1-2)(1-3)               (2-1)(2-3)                (3-1)(3-2)
=X2+ X + 1

p(1)=3*1+7*0+13*0
p(2)=3*0+7*1+13*0
p(3)=3*0+7*0+13*1

¡EO(N2)    operations

Multiplication
P (x) = P0 +   P1X + .....+PN-1 XN-1
Q(x) = Q0 +  Q1X +.....+QN-1 XN-1

P(x) * Q(x) =?

¡EBrute-force: N  "*"

¡EDivide + Conquer
P(x)=(P0 + P1X+...+PN/2-1 XN/2-1)+X N/2(PN/2 + PN/2+1X+...+PN-1XN/2-1)
=Pl(x)+XN/2 Ph(x)
Q(x)=Ql(x)+XN/2Qh(x)

=>P(x)*Q(x)=Pl*Ql+(PlQh+Ph*Ql)XN/2+(Ph*Qh)XN

¡· PlQh+Ph*Ql=(Pl+Ph)*(Ql+Qh)-PlQl-PhQh

¡EM(N) = # "* " for P(x)*Q(x)
M(N)=3M(N/2)           N=2n
=3M(2n-1)
=32M(2n-2)
.
.
=3nM(20)
=3n=(2log23 )n = (2n)log23
=N1.58

Example :
P(x)=1+x+3x -4x = (1+x) + x2 (3-4x)=Pl  +x2Ph
Q(x)=1+2x-5x -3x = (1+2x) + x2 (-5-3x)=Ql   +x2Qh

Large numbers

¡Ep=0 1 2 0 2 0 0 1 0 3 1 1 0 0 0 1 2 0 0 0 0 4 0 1 2 3 1 4
p(x)=x26+2x25+2x24+...+x4+2x3+3x2+x+4 | x=10
P(x)=120x6+2001x5+311x4+x3+2000x2+401x+2314 | x=10000

¡E p*q=p(x)*q(x) |x=10
=P(x)*Q(x) |x=10000

Example:    p=4385                        q=6857
p(x)=4x3+3x2+8x+5     q(x)=6x3+8x2+5x+7
p(x)*q(x)=24x6+50x5+92x4+137x3+101x2+81x+35
60  106  147  109    84
p*q=    30      0      6      7      9      4      5

¡E (p*q) mod N    (pk mod N)
Theorem: (x+y) mod N = x mod N + y mod N    mod N
(x*y) mod N = (x mod N) + (y mod N)    mod N
P mod N
= 120 (x6 mod N) + 2001( x5 mod N) + 311 (x4 mod N) +
(x3 mod N) + 2000(x2 mod N) + 401(x mod N) + 2314
mod N