新書推薦：
《
国术健身 易筋经
》
售價：HK$
34.3
《
古罗马800年
》
售價：HK$
193.2
《
写出心灵深处的故事：踏上疗愈之旅（修订版）（创意写作书系）
》
售價：HK$
67.9
《
控制权视角下的家族企业管理与传承
》
售價：HK$
89.7
《
冯友兰和青年谈心系列
》
售價：HK$
171.8
《
利他主义的生意：偏爱“非理性”的市场（英国《金融时报》推荐读物！）
》
售價：HK$
79.4
《
认知行为疗法：心理咨询的顶层设计
》
售價：HK$
102.4
《
FANUC工业机器人装调与维修
》
售價：HK$
102.4
|
| 編輯推薦： |
|
数学与应用数学专业、信息与计算科学专业和信息安全专业的本科生，密码学与信息安全专业的研究生
|
| 內容簡介： |
|
《数论基础及其应用》为数学与密码学交叉学科的特色教材，内容包括整除理论、同余、连分数、同余方程、原根。《数论基础及其应用》以数论知识为主线，有机地融入数论应用（主要是在密码学中的应用）的内容，理论与应用的知识的广度和深度都适度。《数论基础及其应用》可作为数学与应用数学专业、信息与计算科学专业和信息安全专业的本科生基础教材，也可作为密码学与信息安全专业的研究生教材。
|
| 目錄：
|
目录
前言
第1章整除理论1
1.1带余数除法1
1.2辗转相除法4
1.3**公约数的性质8
1.4*小公倍数11
1.5算术基本定理16
第2章同余20
2.1同余的基本性质20
2.2计算星期几24
2.3循环比赛27
第3章简单密码31
3.1仿射加密31
3.2矩阵加密39
第4章剩余系49
4.1完全剩余系49
4.2简化剩余系54
4.3Euler定理，Fermat定理59
4.4数论函数69
第5章不定方程70
5.1一次不定方程70
5.2方程x2+y2=z276
第6章同余方程82
6.1同余方程的基本概念82
6.2孙子定理87
6.3模p.的同余方程92
6.4素数模的同余方程98
第7章公钥密码103
7.1公钥密码系统103
7.2RSA加密110
第8章二次剩余115
8.1素数模的二次同余方程115
8.2Legendre符号，二次互反律120
8.3Jacobi符号126
第9章原根132
9.1指数及其基本性质132
9.2原根与指标136
9.3伪素数142
第10章实数的表示148
10.1连分数的基本性质148
10.2实数的连分数表示153
10.3循环连分数158
10.4实数的b进制表示163
第11章平方和.169
11.1二平方之和169
11.2四平方之和174
附录179
|
| 內容試閱：
|
第1章整除理论
1.1带余数除法
在本书中，以Z表示全体整数的集合，N表示全体正整数的集合，除特别声明外，字母a;b;c;￠￠￠等均表示整数.
设b是一个正整数.那么，互不相交的区间[bq;bq+1q=0;§1;§2;￠￠￠的和集是实轴，因此，任何整数a必落在**的一个区间[bq;bq+1中，即存在**的整数q，bq6abq+1，于是a=qb+r，其中r=a.bq是**的，并且06rb.因此，我们有如下结论.
定理1.1.1带余数除法设a;b2Z;b0，则存在**的一对整数q;r，使得
注1在定理1.1.1中，称q是b除a的商，r是b除a的余数.
定义1.1.1设a;b2Z;b6=0，若jbj除a的余数是0，则称b整除a记作bja，称b是a的约数因数，或因子，a是b的倍数;否则，称a不被b整除记为b6ja;若bja，1jbjjaj，则称b是a的真约数.
由定义1.1.1可知，a与.a有相同的约数，§1与§a显然是它们的约数.
下面的定理是显然的.
定理1.1.2下面的结论成立：
1若bja，则b除a的商是**的;
2b6=0的所有倍数是0;§b;§2b;￠￠￠;
3bja;cjbcja;
4bja;a6=0jbj6jaj;
5bja，且jajjbja=0;
6bja1;bja2;m1;m22Zbja1m1+a2m2.¤
定义1.1.2一个大于1的整数，若除了数1和它自身外，没有另外的约数，则称为素数．除了1和它自身外，还有其他约数的数称为合数．
由这个定义我们知道，一个大于1的整数，要么是素数，要么是合数.
如果整数aa6=0;§1是合数，那么，a的正约数只有有限个，故必有*小的，设为d.若d不是素数，则有真约数d1;d11;d1jd;dd1，而且d1ja.这与d的*小性矛盾，故d必是素数.因此，存在整数q，使得a=dq，于是jajd2，即d6pjaj.因此，有如下结论.
定理1.1.3任一整数aa6=0;§1的大于1的*小约数d是素数;若d6=a，则d6pjaj.¤
定理1.1.3告诉我们一个判定整数素性的方法：如果一个整数a不被不超过pjaj的素数整除，它一定是素数.
例1.1.1判定97是否是素数.
解由于不超过p97的素数2，3，5，7都不能整除97，所以97是素数.
利用定理1.1.2还可以逐个列出素数.这就是Eratosthenes筛法.下面是一个具体的例子.
例1.1.2写出不超过100的所有的素数.
解将不超过100的正整数排列如下：
按以下步骤进行：
i删去1，剩下的后面的**个数是2，2是素数;
ii删去2后面的被2整除的数，剩下的2后面的**个数是3，3是素数;
iii再删去3后面的被3整除的数，剩下的3后面的**个数是5，5是素数;
iv再删去5后面的被5整除的数，剩下的5后面的**个数是7，7是素数;
照以上步骤可以依次得到不超过100的所有的素数2，3，5，7，11，￠￠￠，97.
要指出的是，Eratosthenes筛法在理论上是可行的;但在实际应用中，由于需要大量的计算，是不可取的.
定理1.1.1虽然简单，却是数论的基础.下面我们给出它的一个应用.
设b1是整数.那么，对于任何正整数a，由定理1.1.1，有整数k，使得
a=q1b+a0;06a06b.1;q1b;
q1=q2b+a1;06a16b.1;q2b;
qk.1=qkb+ak.1;06ak.16b.1;0qk6b.1;
其中诸ai与qi都是**确定的.记qk=ak，则0ak6b.1，并且
a=q1b+a0=q2b+a1b+a0=q2b2+a1b+a0
=q3b+a2b2+a1b+a0=q3b3+a2b2+a1b+a0
=akbk+ak.1bk.1+￠￠￠+a1b+a0:
因此，有如下结论.
定理1.1.4设b是大于１的整数，则任何正整数a都可以写成
a=akbk+ak.1bk.1+￠￠￠+a1b+a0
的形式，其中ak6=0，ai06i6k是在0与b.1之间**确定的整数.
定义1.1.3设b是正整数，n是正整数，并且
其中ak6=0;06ai6b.106i6k，则称ak;ak.1;￠￠￠;a1;a0b是n的b进制表示，称n是k+1位b进制数，k+1是n的b进制位数，ai06i6k是n的b进制表示的第i+1个位数码或第i+1位数.
为了叙述方便，今后，对于十进制表示的数，将仍使用常规的写法.
注2以[x]表示不超过x的**整数.若n=ak;ak.1;￠￠￠;a1;a0b;ak6=0，则
bk6nbk+1;k6logbnk+1;
即k＝[logbn].
例1.1.3若n是整数，则n2被8除的余数只可能是0，1，或4.
解整数n只可能是n=8q+r的形式，其中r=0，1，2，￠￠￠，或7.直接计算即可得到结论.
习题1.1
1.证明定理1.1.2的结论5.
2.设p是n的*小素约数，n=pn1，n11;证明：若pp3n，则n1是素数.
3.设b是大于1的整数，.是小于1的正实数.证明下面的结论：
1对于任意的正整数k，存在**的整数ai，06ai6b.106i6k及实数.k;06.k1;使得
2如果总是.k6=0k1，则无穷级数收敛于.;
3如果对于任意的正整数m，都有某个nm，使得an6=b.1，则结论2中的的级数表示是**的.
如果级数是有限项，那么结论3还成立吗？
4.设a与b是正整数，证明在1;2;￠￠￠;a中能被b整除的整数恰有habi个.
1.2辗转相除法
定义1.2.1整数a1，a2，￠￠￠，ak的公共约数称为a1，a2，￠￠￠，ak的公约数.不全为零的整数a1，a2，￠￠￠，ak的公约数中**的一个称为a1，a2，￠￠￠，ak的**公约数或**公因数，记为a1，a2，￠￠￠，ak.
由于每个非零整数的约数的个数是有限的，所以**公约数是存在的，并且是正整数.
定义1.2.2如果a1，a2，￠￠￠，ak=1，则称a1，a2，￠￠￠，ak是互素的或互质的;如果
ai;aj=1;16i;j6k;i6=j;
则称a1，a2，￠￠￠，ak是两两互素的或两两互质的.
显然，a1，a2，￠￠￠，ak两两互素可以推出a1，a2，￠￠￠，ak=1;反之则不然，例如3，6，4=1，6，4=2.
设a，q，r和b是整数，a=bq+r，那么，由定理1.1.2，如果dja，djb，则有djr=a.bq，反之，若djb，djr，则dja=bq+r.因此a与b的全体公约数的集合就是b与r的全体公约数的集合，这两个集合中的**正数当然相等，即a，b=b，r.由此得到下面定理1.2.1的结论v，这个定理的其他结论是显然的.
定理1.2.1下面的结论成立：
ia1，a2，￠￠￠，ak=ja1j，ja2j，￠￠￠，jakj;
iia，1=1，a，0=jaj，a，a=jaj;
iiia，b=b，a;
iv若p是素数，a是整数，则p，a=1或pja;
v若a=bq+r，则a，b=b，r.¤
注1由定理1.2.1可知，在讨论a1，a2，￠￠￠，an时，不妨假设a1，a2，￠￠￠，an是正整数，以后我们就维持这一假设.
设a和b是整数，b6=0，由定理1.2.1可知，如果
a=bq1+r1;0r1jbj;
则a，b=b;r1.若又有
b=r1q2+r2;0r2r1;
则b;r1＝r1，r2，等等.这样，如果不断地把带余数除法做下去，我们得到下面的一组除法：
根据上面的分析，我们知道
a;b=b;r1=r1;r2=￠￠￠=rn.1;rn=rn:
这是一个计算**公约数的有效方法.上面的这一组算式称为辗转相除法，或辗转相除算法算式.
由1.2.1中的式子，我们看到，
假设对于km16m6n有aQk.bPk=.1k.1rk，那么，由1.2.1就得到
这样，由归纳法得到如下结论.
定理1.2.2使用式1.2.1中的记号，记
我们已经知道rn=a;b，所以又有如下结论.
定理1.2.3存在整数x和y，使得a;b=ax+by.
下面，我们要对1.2.1中所包含的等式的个数，即要做的带余数除法的次数进行估计.
设a，b2N;ab.在组式1.2.1中，我们见到
rk.1=rkqk+1+rk+1;16k6n.1;
其中rn1;qn+12;qi116i6n.
现在，用下面的方式定义Fibonacci数列fFng：
F1=F2=1;Fn=Fn.1+Fn.2;n3;1:2:3
那么，由组式1.2.1，见到
另一方面，我们知道，
由式1.2.3和1.2.5得到
即
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
