高级密码学数论初步

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

第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

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

推论2 (mod n) 则 ka ≡ kb (mod n) 若 a≡b 定义2.6 (同余类) 全体整数按照对模n的同余关系可分为n类，使得同类之数 关于模n同余，不同类之数关于模n不同余。 整数a,b模同余的充要条件是a,b被n除的余数相同。 这样划分的类叫做模n同余类。 全体整数对模n可划分为n个同余类。 定义2.6 (完全剩余系) 在模n的每个同余类中取出一个数作为代表构成的集合叫 做模n的完全剩余系。

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

能被n所整除 其余数为0的为一个剩余类。 其余数为1的为一个剩余类， 余数为2的为一个剩余类，….,余数为n-1为一个剩余类， 被分成n个不同的剩余类，这就是模n的一个完全剩余系。

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

例：设 正数n=10,对任意a的集合 C0={a+10k} 是模n=10的剩余类。 0,1,2,3,4,5,6,7,8,9为模10的一个完全剩余 系。 1,2,3,4,5,6,7,8,9,10为模10的一个完全剩余 系。 0,-1,-2,-3,-4,-5,-6,-7,-8,-9为模10的一个完 全剩余系。

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

集合 {0,1,2 , n 1} 叫模n的最小非负完全剩余系。 集合 {0,1, 1,2, 2, } 叫模n的绝对最小剩余系。 定义3.7 缩剩余系. 从模n的n个同类中取出与n互素的同余类，从中各取一个 代表构成的集合叫模n的缩剩余系。 若n为素数，则它的缩剩余系使n-1个元素的集合。 由于0能被任何数整除，所以它永远不会是素剩余系中的 元素。 定义3.8 (Euler函数) 设n唯一自然数，数列与n互素的个数叫n的Euler函数， 记作ø(n)。 显然模n的素剩余系含有ø(n)。

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

由于两个数很大，在运算时可能遇到困难，更重要的是 会产生溢出。 为此我们引出以下定理 定理3.1 (按模计算原理) 令a1和a2为整数， OP代表操作符+、-、ⅹ,则

(a1opa2 ) modn = [(a1 modn)op(a2 modn)] modn有了这个定理，使得参与运算的两个数在参与算时，各 自先求一次模运算，使得在对整个取模运算时整个数据 变小，从而在一定程度上解决以上问题 下面对op为“+”进行证明

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

证令

a1 = k1 n + r1 , a 2 = k 2 n + r 2对加法，有：

(r1 , r2 ∈ (0, n 1))

(a1 + a2 ) mod n = ((k1n + r1 ) + (k 2 n + r2 )) mod n

n = ((k1 +k2)n+(r +r2))mod 1对于乘法

= (r1 + r2 ) modn = ((a1 mod ) +(a2 mod ))mod n n n

(a1 × a2 ) mod n = ((k1n + r1 ) × (k 2 n + r2 )) mod n

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

= (( k1k 2 n + r1k 2 + r2 k1 ) n + r1r2 ) mod n = (r1 × r2 ) mod n = ((a1 mod n) × (a2

mod n)) mod n

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

[(11mod8)+(15mod8)]mod8=10mod8=2 验证： (11+15)mod8=26mod8=2 [(11mod8)ⅹ (15mod8)]mod8=21mod8=5 验证： (11ⅹ15)mod8=165mod8=5

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

a m = p1a1 p 2 2 ptat 定理3.2对于任给证数m>1,有 其中 p1、p2、….、pt ,p1>p2>….Pt ,ai>0

例3.7 91=7ⅹ13,11011=7ⅹ112ⅹ13 利用按模计算原理也可以用于形如t i =1

a

t

( a t mod n = ( a t 1 mod n) × a mod n = (∏ ( a mod n)) mod n

有了这公式，对于较高指数运算，可以将一个较复杂的 运算，变为较简单的运算。下面具一个例子来说明。 例2.8 求 35 mod 7 解, 按最普通的算法，首先计算3的次方，然后对结果作取 模运算。

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

(1)3的平方

3× 3 = 9

(2)再次平方 9 × 9 = 81 (3)再乘以3 81 × 3 = 243 (4)取模运算 243 mod 7 = 5 利用按模计算原理，即对每次计算的中间结果作取模运算。 (1)3的平方 3 × 3 mod 7 = 2 3 × 3 mod 7 = 2 (2)再次平方2 × 2 mod 7 = 4 (3)再乘以3 4 × 3 mod 7 = 5 对于上式指数运算作取模运算时，我们必须要小心，不 能冒然作取指数运算，因为

(a

t mod n

) mod n 一般不等于 a mod n

t

本文来源：https://www.bwwdw.com/article/hfym.html