书名：快速数论变换
定价：48.0
ISBN：9787030464071
作者：孙琦，郑德勋，沈仲琦
版次：1
出版时间：2016-06

内容提要：
本书主要介绍快速数论变换的理论、方法、应用及其*新进展。
　　数论变换是把数论应用到数字处理中而得到的一种计算方法。其特点是：（1）没有舍入误差；（2）其中某些变换比快速傅里叶变换还快。它不仅在数字处理中有用，还可以应用到多项式、大整数相乘等方面的计算中去。



目录：
目录
**章 初等数论 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. 三项式变换 夕0
6. 二维数论变换 73
7. 用二维快速数论变换计算一维卷积 77
8. 多维数论变换 84
9. 用孙子定理减少字长 87
第四章 Fermat数变换实现中的若干问题价 89
1. 流向图与蝶件 89
2. 计算机上模F运算的实现 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里计算卷积 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

在线试读：
**章 初等数论
　　1. 整数的分解
　　数论是研究数的规律，特别是整数的规律的数学分支-整除是数论中的基本概念，本节从这个概念出发，引进带余除法和辗转相除法，证明了数论中*基本的定理——**分解定理以及介绍这个定理的一些应用。
　　1.1. 整除性我们知道两个整数的和、差、积仍然是整数，但是用一个不等于零的整数去除另一个整数所得的商却不-定是整数，因此，我们引进整除的概念。
　　定义.设a，b是任意两个整数，其中b≠0，如果存在一个整数q使得等式a=bq（1）成立，我们就说b整除a或a被b整除，记作b|a，此时我们把b叫作a的因数，把a叫作b的倍数。
　　如果（1）里的整数q不存在，我们就说b不能整除。或a不能被b整除，记作b|a。
　　由整除的定义出发，下面几个性质是明显的。
　　（i）如果b|a，c|b，则C|a。
　　（ii）如果b|a，则cb|ca。
　　（iii）如果c|a，c|b，则对任意的整数m，n，有c|ma+nb。以上三条性质中，我们总假定，b≠0，c≠0。
　　在一般的情形下，有下面的定理。
　　定理1.设a，b是两个整数，其中b＞0，则存在两个**的整数q及r，使得a=bq+r，0≤r＜b（2）成立。
　　证.作整数序列
　　…，-3b，-2b，-b，0，b，2b，3b，…
　　则a必在上述序列的某两项之间，即存在一个整数q使得qb≤a＜（q+1）b成立。令a-qb=r，则（2）成立。
　　设q1，r1，是满足（2）的另一对整数，因为bq1+r1=bq+r，于是b（q-q1）=r1-r2故b|q-q1|=|r1-r|。由于r及r1都是小于b的正整数，所以上式右边是小于b的。如果q≠q1，则上式左边）b，这是不可能的。因此q=q1，r=r1。证完。
　　我们把（2）中的q叫做。被b所除得的不完全商，r叫做a被b除所得到的余数，常记（a）b=r。
　　1.2. *大公因数与辗转相除法 我们用带余数除法，研究整数的*大公因数的存在问题和实际求法。
　　定义.设a1，a2，a3，…，an是n个整数。若整数d是它们之中每一个的因数，那么d就叫作a1，a2，…，an的一个公因数。整数a1，a2，…，an的公因数中*大的一个叫作*大公因数，记作（a1，a2，…，an），若（a1，a2，…，an）=1，我们说a1，a2，…，an互素。我们有下面的定理。
　　定理1.设a，b，c是任意三个不全为零的整数，且a=bq+c，其中q是整数，则（a，b）=（b，c）。
　　证.因为（a，b）|a，（a，b）|b，则有（a，b）|c，因而（a，b）≤（b，c），同法可证（b，c）≤（a，b），于是得到（a，b）=（b，c），证完。
　　因为显然有（a|，a2，…，an）=（a1|，|a2|，…，|an|）和b＞0，（0，b）=b，所以下面我们只讨论两个正整数的*大公因数的求法，即辗转相除法，并借此推出*大公因数的若干性质。
　　设a，b是任意两个正整数，由带余除法，有下列等式：
　　a=bq1+r1，0＜r1＜b，
　　b=r1q2+r2，0＜r2＜r1，（1）
　　rn-2=rn=1qn+rn，0＜rn＜rn-1，rn-1=rnqn+1+rn+1，rn+1=0，因为b＞r1＞r2＞r3＞…，故经有限次带余除法后，总可以得到一个余数是零，即（1）中rn+1=0。
　　现在我们证明定理2.
　　定理2.若a，b是任意两个正整数，则（a，b）就是（1）中*后一个不等于零的余数，即（a，b）=rn。
　　证.由定理1即得rn=（0，rn）=（rn，rn-1）=…=（r2，r1）=（r1，b）=（a，b），证完。
　　我们从（1）中顺次由**个等式解出，后代入第二个式子得r2=-aq2+b（1+q1q2），再代人第三个式子解出r3，然后代人第四个式子，这样作下去，*后可得rn=ma+nb，这里的m，n是两个整数。于是得到定理3。
　　定理3.若a，b是任意两个正整数，则存在两个整数m，n使得（a+b）=ma+mb。
　　定理4.若a≠0，a|bc，（a，b）=1，则a|c。
　　证.若c≠0，由（a，b）=1知存在两个整数m，n使ma+nb=1，故mac+nbc=c，由a|bc，知a|c，若c=0，结论显然成立。证完。
　　例.求323和221的*大公因数。
　　故（323，221）=17。再从**个式子解出102代人第二个式子得17=（-2）×323+3×221，即得定理3中的m=-2，n=-3。
　　现在来研究两个以上整数的*大公因数。不妨假设a1，a2，…，an是任意n个正整数。令（a1，az）=d2，（d2，a3）=d3，？，（dn-1，an）=dn，于是有下面的定理。
　　定理5.若a1，a2，？，an是n个正整数，则（a1，a2，？，an）=dn。
　　证.由1.1.节中的（ii）知，由此类推，*后得到便有dn≤（a1，a2，…，an），另一方面，设（a1，a2，？，an）=d，由1.1.节中的（ii）和定理3可得故d＜dn，于是得到（a1，a2，？，an）=dn。证完。
　　1.3. *小公倍数
　　定义.设a1，a2，…，an是n个整数（n≥2），若m是这n个数中每一个数的倍数，则m就叫作这n个数的一个公倍数。在a1，a2，？，an的一切公倍数中的*小正数叫作*小公倍数，记作[a1，a2，…，an]。
　　因为乘积a1a2…an就是a1，a2，…，an的一个公倍数，故*小公倍数是存在的。
　　由于任何正整数都不是零的倍数，故讨论整数的*小公倍数时，总假定这些整数都不是零。
　　和*大公因数一样，显然有[a1，a2，…，an]=[ |a1|，|a2|，…，|an|]，所以只需对正整数讨论它们的*小公倍数。
　　我们先研究两个正整数的*小公倍数。
　　定理1.设a，b是任意两个正整数，则（i）a，b的所有公倍数就是[a，b]的所有倍数；（ii）[a，b]=ab/（a，b）。
　　证.设m是a，b的任一公倍数，m=ak=bk，令a=a1（a，b）和b=b1（a，b），代入上式得a1k=b1k，由于（a1，b1）=1，故（1）可以表示a，b的一切公倍数。令t=1，即得*小的正数，故（a，b）=ab/（a，b）。即证明了（ii）；又由（1），（i）亦得证。
　　现在讨论两个以上整数的*小公倍数。设a1，a2，…，an是 n个正整数，令（2）我们有定理2。
　　定理2.若a1，a2，…，an是n（n≥2）个正整数，则[a1，a2，？，an]=mn。
　　证.由（2）知，mi|mi+1，i=2，3，…，n-1，且a1|m2，故mn是a1，a2，？，an的又一公倍数，又设m是a1，a2，？，an的任一公倍数，故由定理1的（i），依此类推，*后得mn |m。因此mn≤|m|。故mn=[a1，a2，…，an]。
　　我们已经讲了*大公因数的求法，因此上面两个定理给出了*小公倍数的求法。
　　1.4. 素数，**分解定理在正整数里，1的因数就只有它本身。任一个大于1的整数都至少有两个正因数，即1和它本身。
　　定义.一个大于1的整数，如果它的正因数只有1和它本身，就叫作素数，否则就叫作复合数。
　　本节的主要目的就是要证明任何一个大于1的整数，如果不论次序，能**地表示成素数的乘积。
　　定理1. 设a是任一大于1的整数，则a的除1以外的*小正因数q是素数，并且当a是复合复数时，q≤a。
　　证.假定q不是素数，由定义，q除1和它本身外还有一正因数q1，因而1＜q1＜q，但q|a，所以q1|a，这与q是*小正因数矛盾，故q是素数。
　　当a是复合数时，则a=a1q且q≤a1，故q≤a。证完。
　　定理2.若p是一素数，a是任一整数，则有p|a或（p，a）=1
　　证.因为（p，a）|p，故（p，a）=1或（p，a）=p。即（p，a）=1或p|a。证完。