《数学基础第二章网络幻灯片.ppt》由会员分享，可在线阅读，更多相关《数学基础第二章网络幻灯片.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学基础第二章网络1第1页，共38页，编辑于2022年，星期六2.1数论基础v数论是一个用数学方法研究证书性质的古老数论是一个用数学方法研究证书性质的古老的数学分支，是近代密码学的重要理论基础的数学分支，是近代密码学的重要理论基础之一。之一。2第2页，共38页，编辑于2022年，星期六2.1.1 因子v约定：字母约定：字母N表示全体自然数集合，表示全体自然数集合，Z表示全体整数表示全体整数集合，即集合，即 N=0，1，2，Z=，-2，-1，0，1，2，v定义定义2.1.1 设设a,b Z，a0，k Z，使得，使得b=ka，则称，则称a整除整除b，并称，并称a是是b的的因子因子或者约数，或者约数
2、，b是是a的的倍数倍数，记为记为a|b。v定义定义2.1.2 设设a,b,c Z，a，b不全为不全为0，如果，如果c|a且且c|b，则称，则称c为为a和和b的的公因子公因子。特别地，把。特别地，把a和和b的所有的所有公因子中最大的，称为公因子中最大的，称为a和和b的的最大公因子最大公因子（Greatest Common Divisors），记为），记为gcd(a,b)或者或者(a,b)。3第3页，共38页，编辑于2022年，星期六v定义定义2.1.3 设设a,b,c Z，如果，如果a|c且且b|c，c1，则称，则称c为为a和和b的公倍数。特别地，把的公倍数。特别地，把a和和b的所有公倍数的所有
3、公倍数中最小的，称为中最小的，称为a和和b的的最小公倍数最小公倍数，记作，记作lcm(a,b)。v可以证明可以证明a和和b的最大公因子必然存在，且唯一；的最大公因子必然存在，且唯一；a和和b的最小公倍数一定存在，且唯一。的最小公倍数一定存在，且唯一。v例如：例如：gcd(12，60)=12，lcm(15，20，30)=60 4第4页，共38页，编辑于2022年，星期六2.1.2素数v定义定义2.1.4 整数整数p（1）是）是素数素数（Prime Number），当），当且仅当且仅当p只有因子只有因子1和和p，否则，否则p为为合数合数。v例如：例如：7=17，7没有没有1和和7以外的因数，因此以
4、外的因数，因此7是素数；是素数；6=23，6有因数有因数2和和3，因此，因此6是合数。是合数。v从此定义可知，正整数集合可分为三类：素数、合数和从此定义可知，正整数集合可分为三类：素数、合数和1。v定义定义2.1.5 如果两个整数如果两个整数a和和b有有gcd(a,b)=1，则称，则称a与与b互互素素。1与任何整数互素。与任何整数互素。5第5页，共38页，编辑于2022年，星期六v定义定义2.1.6 Euler（欧拉欧拉）函数是定义在正整数上的函数，）函数是定义在正整数上的函数，它在正整数它在正整数m的值等于的值等于1，2，.，i，.，m-1中与中与m互素互素的数的个数，记作的数的个数，记作(
5、m)。v例如例如m=6，1，2，3，4，5中与中与m互素的数为互素的数为1，5，则有：则有：(m)=(6)=2v定理定理2.1.1 设正整数设正整数m的标准分解形式为：的标准分解形式为：m=p1e1p2e2pnen 则则(m)=m(1-1/p1)(1-1/p2)(1-1/pn)v例如例如m=6，其标准分解形式为其标准分解形式为6=2131因此，因此，(m)=(6)=6(1-1/2)(1-1/3)=2。6第6页，共38页，编辑于2022年，星期六v定理定理2.1.2 Euler（欧拉）定理（欧拉）定理 若整数若整数a和和m互素，则互素，则a(m)1(mod m)v例如例如a=3，m=10由定理由
6、定理2.1.1，10=2151，因此，因此 (m)=(10)=10(1-1/2)(1-1/5)=4代入定理代入定理2.1.2公式中有：公式中有：a(m)=34=811(mod 10)1(mod m)v定理定理2.1.3（算术基本定理）任何一个整数（算术基本定理）任何一个整数m（1），都存在唯一的因数分解形式：，都存在唯一的因数分解形式：m=p1e1p2e2pnen 其中其中ei N，pi均为素数且均为素数且p1p20，则存在，则存在唯一的整数唯一的整数q和和r，使得：，使得：a=qb+r 0r0，反复使用带余数除法，得等式如下：，反复使用带余数除法，得等式如下：a=bq1+r1 0r1bb=r
7、1q2+r2 0r2r1r1=r2q3+r3 0r3r2 rn-2=rn-1qn+rn 0rn1的常数的常数)，则称该算法是，则称该算法是指数时间算法指数时间算法。v2、问题的复杂性、问题的复杂性v计算复杂性理论按照解决问题的算法对问题进行分类。能够用多项计算复杂性理论按照解决问题的算法对问题进行分类。能够用多项式时间算法解决的问题称之为式时间算法解决的问题称之为易解的易解的；不能在多项式时间内解决的；不能在多项式时间内解决的问题称之为问题称之为难解的难解的。32第32页，共38页，编辑于2022年，星期六v定义定义2.3.1 P类问题类问题：在多项式时间内可以完成的问题；：在多项式时间内可以
8、完成的问题；NP类问题类问题：在多项式时间内可以验证的问题；：在多项式时间内可以验证的问题；v在在NP类问题中，有一类问题称为类问题中，有一类问题称为NP完全类问题完全类问题(记为记为NPC)，所有，所有NP类问类问题都可以转换为题都可以转换为NP完全类问题。因此完全类问题。因此NP完全类问题只要有一个问题有完全类问题只要有一个问题有多项式求解算法，则整个多项式求解算法，则整个NP类问题都属于类问题都属于P类问题（即可在多项式时间类问题（即可在多项式时间内完成）。内完成）。v把把P类问题称为易解问题，类问题称为易解问题，NP类问题称为难解问题。由于类问题称为难解问题。由于NP完全完全类问题类问
9、题(NPC问题问题)目前不存在有效的算法，若想破译一密码相当于解决目前不存在有效的算法，若想破译一密码相当于解决一个一个NP完全类问题，显然该密码是计算安全的。因此说完全类问题，显然该密码是计算安全的。因此说NP完全类问题是完全类问题是密码学的基础之一。密码学的基础之一。33第33页，共38页，编辑于2022年，星期六v3、三个、三个NP完全类问题：完全类问题：（1）整数分解问题）整数分解问题求两个大素数的乘积是容易进行的，但要分解两个大素数的乘积求两个大素数的乘积是容易进行的，但要分解两个大素数的乘积N=pq，求出它的素因子，求出它的素因子p和和q则是非常困难的。则是非常困难的。但如果给定素
10、因子但如果给定素因子p和和q，则可很容易验证，则可很容易验证N=pq是否成立。是否成立。（2）背包问题）背包问题将背包问题抽象为数学模型：设长度为将背包问题抽象为数学模型：设长度为n的向量的向量B=(b1,b2,bn)，任意，任意给定一个正整数给定一个正整数S，寻找有没有一些，寻找有没有一些bi的和恰好等于的和恰好等于S，即求方程：，即求方程：的解向量的解向量x=(x1,x2,xn)，其中，其中xi=0或或xi=1。当。当n较大时，很难求得较大时，很难求得解向量。解向量。v但如果给定向量但如果给定向量x=(x1,x2,xn)，那么可以很容易验证它是否为，那么可以很容易验证它是否为背包问题的解。
11、背包问题的解。34第34页，共38页，编辑于2022年，星期六（3）离散对数问题）离散对数问题设设g，x，p是正整数。已知是正整数。已知g，x和和p，可以很快地求出：，可以很快地求出：y gx(mod p)反过来，如果已知反过来，如果已知y，g和和p，求，求x使得：使得：y gx(mod p)成立，此即成立，此即离散对数问题离散对数问题。当。当y，g和和p较大时，求较大时，求x非常困非常困难。难。但如果给定一个整数但如果给定一个整数x，那么可以很容易验证它是否为，那么可以很容易验证它是否为y gx(mod p)的解。的解。35第35页，共38页，编辑于2022年，星期六2.4本章总结本章总结（
12、1）数论的有关基本定义）数论的有关基本定义（2）Euclid算法算法（3）同余概念）同余概念（4）二次剩余概念）二次剩余概念（5）熵和互信息的概念）熵和互信息的概念（6）三个）三个NP-完全类问题完全类问题36第36页，共38页，编辑于2022年，星期六2.5思考及作业题v1、列出小于、列出小于30的素数。的素数。v2、（、（1）整数）整数39和和63是否互素？是否互素？（2）用欧几里德算法求出）用欧几里德算法求出gcd39，63，并给出其线性组合的表示。，并给出其线性组合的表示。v3、用欧几里德算法求出、用欧几里德算法求出gcd1997，57和和gcd24140，16762，并，并分别给出其线性组合的表示。分别给出其线性组合的表示。v4、利用定理、利用定理2.1.1计算以下欧拉函数的值：计算以下欧拉函数的值：(41)、(27)、(231)、(440)。v5、用中国剩余定理求解同余方程组：、用中国剩余定理求解同余方程组：x 1(mod5)x 5(mod6)x 4(mod7)x 10(mod11)37第37页，共38页，编辑于2022年，星期六 第二章完第二章完38第38页，共38页，编辑于2022年，星期六