高级密码学数论初步

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

第3部分数论初步

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

3.1素 数定义2.1( 整除、倍数、因数) 设a、b为整数， 若存在整数c,使b=ac,则称a可整除b。 记作a|b。 b叫做a的倍数，a叫做b的因数。 若不存在这样的整数c,则称a不能整除b。 记作a b。 例如30=2×15=3×10=5×6 我 们有2,3,5分别整除30。 或30被2,3,5分别整除。 记作分别记为：2|30,3|30, 5|30。 2,3,5都是30的因数，30是2,3,5的倍数。

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

又例如7|84,-7|84,5|20,19|171,13|0 3 8,5 12。 0是任何非零整数的倍数，1是任何整数的因数，任何非零 整数a是其自身的倍数。 由此我们可以得出这样的结论 如果a|1,则a=1 如果a|b、b|a,则a=b 如果b≠0,b则可整除0。 如果b|g、b|h,对于任何整数m和n,则满足b|(mg+nh)。 事实上，对于g=bⅹg1(g1为整数),有b|g。 对于h=bⅹh1(h1为整数),满足b|h。 所以有 mg+nh=mbg1+nbh1=bⅹ(mg1+nh1) 所以b能整除mg+nh。

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

例 b=7,g=14,h=63,m=3,n=2 , , , ,

7|14,7|63,必满足 ， ,必满足7|(3ⅹ14+2ⅹ63)。 ⅹ ⅹ 。 又由于( ⅹ 又由于(3ⅹ14+2ⅹ63)=7(3ⅹ2+2ⅹ9) ⅹ ) ⅹ ⅹ 所以有： 所以有：7|(3ⅹ14+2ⅹ63)=7|(7(3ⅹ2+2ⅹ9) ⅹ ⅹ ⅹ ⅹ

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

定义2.2 (公约数、最大公约数、素数、互素、两两互素)

设整数a,b,….l 若有整数d满足d|a,d|b,….,d|l,则称d为它们的公约数。 公约数中最大者成为它们的最大公约数。 记作：gcd(a,b,….,l) 如果gcd(a,b,….,l)=1,则说a,b,…l互素。 如果 a,b,….,l 中的每个数都与其它数互素，则称它们 两两互素。

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

关于公约数有以下性质： 性质1 若a是b的倍数，则gcd(a,b)=b。 性质2 若 a = bq + c 则gcd(a,b )=gcd(b,c) 定义2.3 (素数)只有1和自身为其因数的大于1的整数叫 素数。 显然除2外，所有素数都是奇数。 寻找素数的方法： 设n是一个正整数，如果对所有素数p<=根号n,都有p n,则 n一定是素数。性质1 若p为素数，则对任一整数a,

p|a

或P a

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

性质2 若p为素数，p|ab 则p|a 或 p|b 。 性质3 素数有无穷多个。

3.2 同余或按模计算定义2.5(同余)设n为一自然数，若a-b为n的倍数，即 (a-b)|n,则称a与b关于模n同余。

a mod n = ba mod n ≠ b

记为：a

≡b

(mod n)

若a与b关于模n不同余，则记作： a ≠ b (mod n)

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

39 ≡ 47|(39-4) 39mod7=4

(mod 7 )

性质1模n具有以下性质： (1)自反性 对任一整数a,有 a ≡ a (modn) 证：对任一正数a,我们有a=a+0 n,所以有：

a≡a

(mod n)

(2) 对称性 如果amodn=bmodn,则a≡b (modn)

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

证： 若a≡b(mod n)

a=b+kn 则存在整数k使得： 从而有： b=a+(-k)n 因此有b≡a (modn)

(3)传递性 若 则

a≡ b

(mod) , b ≡ c n

(modn)

a≡c

(mod n )

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

证: 若 a ≡ b (mod n) ,b ≡ c (mod n) 则分别存在整数k1,k2使得： b=c+k2n a=b+k1n 从而有 a=c+(k1+k2)n 因为k1+k2是

整数，所以有

a≡c

(mod n)(mod7),所以有

例3.3 传递性例子 39 ≡32 (mod7),32 ≡25 39 ≡25(mod7) 例3.4 自反性 39 ≡39 mod7

25 ≡25 mod7

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

例3.5 对称性 32 ≡39(mod7) 39 ≡32(mod7) 性质2 若ai ≡ bi 则：

(mod n)

(i = 1,2, , k )

∑a ≡ ∑bi =1 i i =1

K

k

i

(mod n)(mod n)

a ≡ bi i =1 i =1

k

k

i

根据以上性质，可得到以下两个重要的推论。 推论1 若 a≡b(mod n)

则 ak ≡ bk

(mod ) n

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完 …… 此处隐藏：3128字，全部文档内容请下载后查看。喜欢就下载吧 ……