¡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
double linked list:
(Sparse matrix)
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: N2 "*"
¡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