内容发布更新时间 : 2024/11/15 4:19:54星期一 下面是文章的全部内容请认真阅读。

《数论算法》 第二章 同余运算

第 2 章 同余运算

内容 1. 同余概念 2. 性质 3. 剩余类→整数分类 4. 模幂运算 5. 一次不定方程 同余及其计算 要点

应用：

? 密码学

? 公钥密码学

【例】 RSA公钥算法：

准备：选大素数p、q，记n＝pq，φ(n)＝(p－1)(q－1)，再选正整数e，满足

（e，φ(n)）≡1（mod n）

并求d，满足 ed＝1（mod φ(n)）

加密：明文串P编码为数字M，则密文C≡Me （mod n） 解密： M≡Cd（mod n），再将数字M解码得明文串P

2.1 同余的概念及基本性质

(一) 同余概念

【定义2.1.1】给定一个正整数m，两个整数a、b叫做模m同余，如果a－b被m整除，即m|a?b，记作a≡b（mod m）；否则叫做模m不同余，记作ab（mod m）

【注】 ∵ m|a?b??m|a?b

1/57

《数论算法》 第二章 同余运算

∴ a≡b（mod m）?a≡b（mod －m）

假定：模m?1。

判断同余的方法一：利用定义

【例1】 7│28＝29－1，故29≡1（mod 7）； 7│21＝27－6，故27≡6（mod 7）； 7│28＝23－（－5），故23≡－5（mod 7）； (二) 性质

【性质1】设m是一个正整数，a、b是两个整数，则a≡b（mod m）?存在整数k，使得a＝b＋km。

（证）a≡b（mod m） ? m|a?b

? 存在k，使得 a－b＝km，即a＝b＋km

【性质2】同余是一种等价关系。即 （i） 自反性：a≡a（mod m）

（ii） 对称性：a≡b（mod m）? b≡a（mod m） （iii） 传递性：a≡b（mod m）且b≡c（mod m）

a≡c（mod m） （证）（i）m│0＝a－a

?

? a≡a（mod m）

（ii）a≡b（mod m）? m│a－b ? m│b－a＝－(a－b) ? b≡a（mod m）

（iii）a≡b（mod m），b≡c（mod m）? m│a－b，m│b－c

? m│(a－b)＋ (b－c)＝a－c ? a≡c（mod m）

【例3】

2/57

《数论算法》 第二章 同余运算

【性质3】（等价定义）整数a、b模m同余?a、b被m除的余数相同。

（证）由欧几里得除法，存在q，r，q?，r?，使得

a＝qm＋r，b＝q?m＋r?

即 a－b＝(q－q?)m＋(r－r?) 或 （r－r?）＝(a－b)－(q－q?)m 故 m│(a－b) 故 m│(a－b)

? m│(r－r?)

? r－r?＝0

? r－r?＝0，即r＝r?

但 0?│r－r?│＜m且m│(r－r?)

【性质4】设m为正整数，a、b、c、d为整数，若

a≡b（mod m）， c≡d（mod m）

则

（i） a＋c≡b＋d（mod m）； （ii） ac≡bd（mod m）。

（证）已知a≡b（mod m）且 c≡d（mod m）

? a＝b＋hm且c＝d＋km

? a＋c＝(b＋hm)＋( d＋km)＝(b＋d)＋(h＋k)m，

ac＝(b＋hm)( d＋km)＝bd＋(hd＋kb＋hkm)m

? 由性质1即得结论。

一般情形：ai?bi （mod m）（i＝1, 2, …, k），则 （i）

?ai??bi（mod m）

i?1ki?1ki?1i?1kk（ii）

?ai??bi（mod m）

【推论1】a≡b（mod m）? na≡nb（mod m），其中n为正整数。

3/57