网络安全-08：数论入门.pptVIP

Chapter8

数论入门《密码编码学与网络平安》

2025/4/12西安电子科技大学计算机学院2§8.1素数数论主要关心的是素数整数p1是素数，当且仅当它只有因子±1和±p。素数不能写作其它数的乘积1是素数，但一般对它没兴趣例如：2,3,5,7是素数，4,6,8,9,10不是素数200以内的素数: 2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199

2025/4/12西安电子科技大学计算机学院3907

2025/4/12西安电子科技大学计算机学院4素数的个数

2025/4/12西安电子科技大学计算机学院5素因子分解算数根本定理：任意整数a1都可以唯一地因子分解为

a=p1a1p2a2…ptat，其中，pi均是素数，且p1p2…pt,且每一个ai0如.91=7×13;3600=24×32×52确定一个大数的素因子分解不是一件容易的事

2025/4/12西安电子科技大学计算机学院6互素和最大公因子两个数a,b互素，如果它们没有除1以外的公因子如GCD(8,15)=1最大公因子如:300=22×31×5218=21×32因此GCD(18,300)=21×31×50=6

2025/4/12西安电子科技大学计算机学院7§8.2Fermat定理和Euler定理ap-1≡1(modp)条件：p是素数，GCD(a,p)=1例：a=2,p=3,22mod3=1.Fermat小定理ap≡a(modp)p是素数，a是任意整数。〔不要求a,p互素〕例：p=5,a=10ap=105≡10(mod5)在公钥密码中很有用Fermat〔费马〕定理

2025/4/12西安电子科技大学计算机学院8小于n且与n互素的正整数的个数如n=10,{0,1,2,3,4,5,6,7,8,9}，{1,3,7,9}?(10)=4素数p ?(p)=p-1素数p,q，有?(pq)=(p-1)×(q-1)如：?(37)=36?(21)=(3–1)×(7–1)=2×6=12约定：?(1)=1Euler〔欧拉〕函数?(n)

2025/4/12西安电子科技大学计算机学院9定理：设n=p1e1p2e2…prer，pi≠pj,pi为素数，ei≥1,那么?(n)=n(1-p1-1)(1-p2-1)…(1-pr-1)例如：12=22*3?(12)=12*(1-2-1)*(1-3-1)=4

2025/4/12西安电子科技大学计算机学院10

2025/4/12西安电子科技大学计算机学院11a?(n)≡1(modn)对任意a,n，gcd(a,n)=1另一种表示：a?(n)+1≡a(modn)对任意a,n如：a=3;n=10;?(10)=4; 那么34=81≡1mod10a=2;n=11;?(11)=10; 那么210=1024≡1mod11Fermat定理是Euler定理的推论，或者说，Euler定理是Fermat定理的更一般化形式。Euler定理

2025/4/12西安电子科技大学计算机学院12与RSA有关的结果两个素数p和q，整数m和n，n=pq,0mn,那么有m?(n)+1=m(p-1)(q-1)+1≡m(modn)另一种表示：mk?(n)+1≡m(modn)Euler定理

2025/4/12西安电子科技大学计算机学院13§8.3素性测试常常需要找到大的素数试除法例如，用小于该数平方根的所有数去试除对较小数有效基于素数性质的有选择的统计方法所有素数均应满足素数的性质但某些合数〔可称作伪素数〕也满足素数的性质确定素性的测试

2025/4/12西安电子科技大学计算机学院14MillerRabin算法基于Fermat定理算法如下:TEST(n)is:1.找出整数k,q,其中k0,q是奇数