快速数论变换PDF电子书下载

第一章 初等数论 1

1．整数的分解 1

2．同余式 12

3．二次剩余 26

第二章 卷积运算和快速变换 45

1．卷积运算 45

2．DFT 46

3．FFT 48

4．素数幂变换 50

5．WFTA 55

第三章 数论变换的理论基础 60

1．数论变换和快速数论变换 60

2．数论变换的具体构造 63

3．Fermat数变换 67

4．用快速数论变换计算循环卷积 68

5．三项式变换 70

6．二维数论变换 73

7．用二维快速数论变换计算一维卷积 77

8．多维数论变换 84

9．用孙子定理减少字长 87

第四章 Fermat数变换实现中的若干问题 89

1．流向图与蝶件 89

2．计算机上模Ft运算的实现 94

3．字长与序列长度间的关系 106

4．用快速Fermat数变换与FFT计算卷积运算量的比较 111

第五章 代数数论初步 115

1．环和域 115

2．代数数和代数数域 116

3．R（θ）的基底和整底 123

4．整除性和素数 128

5．理想数，同余 129

6．二次域R（？） 135

7．属于不同域的理想数 144

8．素理想数的一些性质 146

9．［p］的分解 148

10．在分圆域上［p］的分解 152

第六章 二次域和分圆域内的DFT构造 160

1．计算复整数序列的卷积 160

2．在二次域R（？m ）里计算卷积 165

3．在分圆域里计算卷积 175

第七章 任意环上具有循环卷积性质的可逆变换 181

1．引言 181

2．任意环上的CRT 181

3．ZM上的CRT 188

4．二维CRT 194

第八章 数论变换在其他方面的应用 199

1．GF（pn）上的多项式相乘 199

2．大整数相乘 200

3．F＝GF（p）上的多项式的除法 200

4．计算序列的相关函数 201

参考文献 204