# Barrett And Montgomery of Polynomials

## Barrett reduction of polynomials

f

,

g

Z

p

[

x

]

f,g in Z_p[x]

f,gZp[x]，其中

p

p

p是素数。那么：

f

m

o

d

g

=

f

f

g

g

f mod g = f - lfloor frac{f}{g} rfloor g

fmodg=fgfg

1

/

g

{

f

g

f

,

g

Z

p

[

x

]

}

1/g in { dfrac{f}{g} | f,g in Z_p[x] }

1/g{gff,gZp[x]}

m

Z

p

[

x

]

m in Z_p[x]

mZp[x]，使得：

1

g

=

m

R

frac{1}{g} = frac{m}{R}

g1=Rm

R

=

x

k

Z

p

[

x

]

R=x^k in Z_p[x]

R=xkZp[x]

k

k

k是某个正整数

m

=

R

g

Z

p

[

x

]

m = lfloor frac{R}{g} rfloor in Z_p[x]

m=gRZp[x]

e

=

1

g

R

g

R

e = frac{1}{g} - dfrac{lfloor frac{R}{g} rfloor}{R}

e=g1RgR

f

m

o

d

g

f

f

m

R

g

f mod g approx f - lfloor frac{f cdot m}{R} rfloor g

fmodgfRfmg

k

k

k，使得

f

e

f cdot e

fe的系数足够小，那么：

f

m

o

d

g

=

f

(

(

f

m

)

k

)

g

Z

p

[

x

]

f mod g = f - ((f cdot m) gg k) g in Z_p[x]

fmodg=f((fm)k)gZp[x]

gg

(

i

=

0

n

1

a

i

x

i

k

)

:

=

i

=

k

n

1

a

i

x

i

k

(sum_{i=0}^{n-1}a_i x^i gg k) := sum_{i=k}^{n-1}a_i x^{i-k}

(i=0n1aixik):=i=kn1aixik

## Montgomery multiplication of polynomials

f

,

g

,

h

Z

p

[

x

]

f,g,h in Z_p[x]

f,g,hZp[x]，其中

p

p

p是素数。计算：

f

g

m

o

d

h

f cdot g mod h

fgmodh

R

=

x

k

Z

p

[

x

]

R=x^k in Z_p[x]

R=xkZp[x]，其中

k

k

k是某个正整数，使得

g

c

d

(

R

,

h

)

=

1

gcd(R,h)=1

gcd(R,h)=1

h

1

h

1

m

o

d

R

R

1

R

1

m

o

d

h

h^{-1} cdot h equiv 1 mod R\ R^{-1} cdot R equiv 1 mod h\

h1h1modRR1R1modh

f

=

f

R

m

o

d

h

g

=

g

R

m

o

d

h

overline{f} = f R mod h\ overline{g} = g R mod h\

f=fRmodhg=gRmodh

f

g

=

f

g

R

=

f

g

R

1

m

o

d

h

overline{f g} = f g R = overline{f} cdot overline{g} cdot R^{-1} mod h

fg=fgR=fgR1modh

T

=

f

g

T = overline{f} cdot overline{g}

T=fg，则

f

g

=

T

R

1

overline{f g} = TR^{-1}

fg=TR1

m

Z

p

[

x

]

m in Z_p[x]

mZp[x]，使得

R

T

+

m

h

R mid T+mh

RT+mh

T

+

m

h

0

m

o

d

R

T+mh equiv 0 mod R

T+mh0modR

m

=

T

h

1

m

o

d

R

m = -Th^{-1} mod R

m=Th1modR

f

g

(

T

+

m

h

)

R

1

=

(

T

(

T

h

1

m

o

d

R

)

h

)

R

1

m

o

d

h

overline{f g} equiv (T+mh)R^{-1} = (T-(Th^{-1} mod R) cdot h) cdot R^{-1} mod h

fg(T+mh)R1=(T(Th1modR)h)R1modh

R

=

x

k

R=x^k

R=xk，所以

f

g

=

(

T

L

o

w

k

(

T

h

1

)

h

)

k

overline{f g} = (T-Low_k(Th^{-1}) cdot h) gg k

fg=(TLowk(Th1)h)k

L

o

w

k

(

i

=

0

n

1

a

i

x

i

)

:

=

i

=

0

min

(

k

,

n

)

1

a

i

x

i

Low_k(sum_{i=0}^{n-1}a_i x^i) := sum_{i=0}^{min(k,n)-1}a_i x^i

Lowk(i=0n1aixi):=i=0min(k,n)1aixi

f

g

=

f

g

R

1

m

o

d

h

fg = overline{f g} R^{-1} mod h

fg=fgR1modh，计算方法与上述的计算

T

R

1

m

o

d

h

TR^{-1} mod h

TR1modh的过程相同。其实叫做：Montgomery reduction

k

k

k值，结果都是正确的。但如果

k

<

n

k<n

k<n，计算出的结果可能是冗余的。

### 总结

• Barrett reduction of polynomials：将多项式取模运算，转化为多项式乘法以及“右移”。
• Montgomery multiplication of polynomials：将多项式模乘运算，转化为多项式乘法、“截断”以及“右移”。

THE END