密码学数学基础第三讲 同余式(2)

第 3 章 同余方程（一） 内容：● 同余方程概念● 解同余方程● 解同余方程组（二） 重点● 解同余方程（三） 应用● 密码学，公钥密码学3.1 基本概念及一次同余方程(一) 同余方程（1） 同余方程【定义3.1.1】（定义1）设m 是一个正整数，f(x)为n 次多项式()0111a x a x a x a x f n n n n ++++=--Λ其中i a 是正整数（n a ≠0（mod m ）），则f (x)≡0（mod m ） （1） 叫做模m 的（n 次）同余式（或模m 的（n 次）同余方程），n 叫做f(x)的次数，记为deg f 。

（2） 同余方程的解若整数a 使得 f (a)≡0（mod m ）成立，则a 叫做该同余方程的解。

（3） 同余方程的解数若a 是同余方程（1）的解，则满足x ≡a （mod m ）的所有整数都是方程（1）的解。

即剩余类a C ＝{x ｜x ∈Z ，x ≡a （mod m ）}中的每个剩余都是解。

故把这些解都看做是相同的，并说剩余类a C 是同余方程(1)的一个解，这个解通常记为x ≡a （mod m ）当21,c c 均为同余方程(1)的解，且对模m 不同余时，就称它们是同余方程(2)的不同的解，所有对模m 的两两不同余的解的个数，称为是同余方程（1）的解数，记作()m f T ;。

显然()m f T ;≤m（4） 同余方程的解法一：穷举法任意选定模m 的一组完全剩余系，并以其中的每个剩余代入方程（1），在这完全剩余系中解的个数就是解数()m f T ;。

【例1】（例1）可以验证，x ≡2，4（mod 7）是同余方程15++x x ≡0（mod 7）的不同的解，故该方程的解数为2。

50＋0＋1＝1≡3 mod 751＋1＋1＝3≡3 mod 752＋2＋1＝35≡0 mod 753＋3＋1＝247≡2 mod 754＋4＋1＝1029≡0 mod 755＋5＋1＝3131≡2 mod 756＋6＋1＝7783≡6 mod 7【例2】求同余方程122742-+x x ≡0（mod 15）的解。

数论中的同余定理与同余方程的解法数论是研究整数性质和整数运算规律的数学分支。

同余定理和同余方程是数论中重要的概念和工具。

本文将介绍同余定理的基本思想和应用，以及解决同余方程的常见方法。

一、同余定理同余是指两个整数除以同一个数所得的余数相等。

同余定理是数论中的一个基本理论，用于刻画整数之间的关系。

设a、b和n都是整数，n>0，我们称a与b关于模n同余，记作a≡b(mod n)，当且仅当n|(a-b)。

同余定理可以分为以下几条：1. 同余的基本性质（1）自反性：a≡a(mod n)（2）对称性：若a≡b(mod n)，则b≡a(mod n)（3）传递性：若a≡b(mod n)，b≡c(mod n)，则a≡c(mod n)2. 同余的运算性质（1）加法：若a≡b(mod n)，c≡d(mod n)，则a+c≡b+d(mod n)（2）减法：若a≡b(mod n)，c≡d(mod n)，则a-c≡b-d(mod n)（3）乘法：若a≡b(mod n)，c≡d(mod n)，则a*c≡b*d(mod n)3. 同余的整除性质若a≡b(mod n)，则m|a的充分必要条件是m|b。

同余定理不仅在数论中有重要应用，还广泛用于密码学、计算机科学等领域。

二、同余方程的解法同余方程是形如ax≡b(mod n)的方程，其中a、b和n为已知整数，x 为未知整数。

解同余方程可以通过以下几种方法：1. 借助同余定理直接解法：若gcd(a,n)|b，方程ax≡b(mod n)存在解。

具体解法为，求出gcd(a,n)的一个解d，然后将方程两边同时除以d，得到新方程a'x≡b' (mod n')，其中a'、b'和n'为新方程的系数，满足gcd(a',n')=1，然后再求解新方程，最后合并得到原方程的所有解。

2. 中国剩余定理：中国剩余定理是解决同余方程组的一种有效方法。

第三章 数学基础近代密码学用到数学之多，遍及许多数学分支，如概率统计、信息论、数论、有限域理论、复杂性理论，甚至于代数、几何等都在近代密码学中扮演重要角色。

所以，数学是近代密码学不可或缺的工具。

3.1 数论3.1.1 数的m 进制表示1. 十进制表示十进制是最方便的一种整数表示法。

例： 7108109101198723+∙+∙+∙=110210710310553721234+∙+∙+∙+∙=2. m 进制表示实际上，使用任何进制表示一个数都是可以的。

定理 设m 是大于的正整数，则每一个正整数n 可唯一地表示为0111c m c m c m c n k k k k ++++=--其中),,2,1,0(k j c j =是整数，且0,0≠<≤k j c m c 。

记作：m k k c c c c n )(011 -=。

3. m 进制表示的具体做法将一个正整数n 表示成m 进制时，主要是要确定k k c c c c ，，，，110- 。

若用⎥⎦⎥⎢⎣⎢m n 表示n 除以m 后，取其整数部分（也就是比m n 小的最大整数），确定k k c c c c ，，，，110- 的方法如下：1. 令01c r =，n n =0，则有1221101c m c m c m c m n n k k k k ++++=⎥⎦⎥⎢⎣⎢=---2. 令12c r =，则有2331212c m c m c m c m n n k k k k ++++=⎥⎦⎥⎢⎣⎢=---3. 令23c r =， ……4. 若m n i >，令 ,2,1,0,1==+i c r i i122111++-----+++++=⎥⎦⎥⎢⎣⎢=i i i k k i k k i i c m c m c m c m n n5. 直到110++==⎥⎦⎥⎢⎣⎢=k k k k r c m n n ， 即m n k <为止。

4. 举例例 5389==m n ， 解 令 3890==n n则有34342323121201013 0 5350 3 55152 15577547753895c r n n c r n n c r n n c r n n ===⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢====⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢====⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢====⎥⎦⎥⎢⎣⎢=⎥⎦⎥⎢⎣⎢=，，，，故5123)4203(4525053389=+∙+∙+∙=例 2389==m n ， 解 令 3890==n n⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦1 12121 12320 32620 621220 1222420 42 24821 84 29720 97219421 19423892889778667556445334223112001====================================c n n c n n c n n c n n c n n c n n c n n c n n c n n ，，，，，，，，， 故2278)101000011(1222389=+++=第六次课截止于此3.1.2 数的因数分解素数 只能被1和其自身除尽的正整数称为素数（1,2,3,5,7, 11,13,17,…）。

同余运算原理同余运算原理是数论中一个重要的概念，它描述了两个整数之间的一种等价关系。

在数学中，同余运算是指两个整数除以同一个正整数所得的余数相等。

这个概念在密码学、计算机科学和其他领域中都有广泛的应用。

本文将从同余运算的定义、性质、应用以及相关定理等方面进行介绍。

同余运算的定义很简单，对于给定的整数a、b和正整数m，如果a和b除以m所得的余数相等，即(a mod m) = (b mod m)，则称a与b在模m下同余，记作a ≡ b (mod m)。

其中mod是取模运算的符号，表示取余数的操作。

同余运算可以理解为将整数集合划分为若干个等价类，每个等价类中的整数与模m下的余数相等。

同余运算具有以下几个重要的性质：传递性、反射性、对称性和合并性。

传递性指如果a ≡ b (mod m)且b ≡ c (mod m)，则a ≡ c (mod m)。

反射性指a ≡ a (mod m)，即任意整数与自身在模m下同余。

对称性指如果a ≡ b (mod m)，则b ≡ a (mod m)。

合并性指如果a ≡ b (mod m)且c ≡ d (mod m)，则a + c ≡ b + d (mod m)和a - c ≡ b - d (mod m)。

同余运算在密码学中有广泛的应用，特别是在公钥密码学中。

RSA 加密算法就是基于同余运算原理设计的一种非对称加密算法。

在该算法中，两个大质数的乘积被用作模数m，并选择一个与欧拉函数值互质的整数作为加密密钥e。

通过对明文进行加密运算得到密文，密文再通过解密运算得到原始的明文。

RSA算法的安全性基于大整数分解的困难性，即将大整数因式分解的难题。

除了密码学，同余运算还在计算机科学中起到重要的作用。

在计算机中，同余运算常常用于计算哈希函数的值。

哈希函数将任意长度的输入数据映射为固定长度的哈希值，而同余运算可以将哈希值映射到一个较小的范围内。

这在数据索引、数据校验和数据完整性验证等方面都具有重要的应用。

揭开密码的神秘面纱——同余运算PartIII [遇见数学] 核心成员: 蘑菇长颈鹿一枚数学系的大学生，喜欢数学文化的小视频，翻译中如有问题，请多指正~密码学中的同余运算 III欧几里得算法(Euclidean algorithm)，又称辗转相除法，是求最大公约数的算法。

它最早出现在欧几里得的《几何原本》中，而在我国可以追溯至东汉出现的《九章算术》。

欧几里得算法根据明确定义的规则来执行计算过程，是最常用的最古老算法之一。

欧几里得算法我们先来回忆一个刚才我们提到的数论中的重要概念——最大公约数(Greatest Common Divisor ())，它是表示可以同时整除两个整数和的最大整数。

由于在确定逆的存在性时常常会用到 ,下面我们来探索一种算法来帮助我们快速的找到。

欧几里得算法(The Euclidean Algorithm)就为我们提供了一种快速找到两个整数之间的方法。

具体方法如下：•若，那么，同理，若，那么。

•将写成带余除法形式。

•由于，利用欧几里得算法找到即为所求。

•若仍不容易得到，则循环第三步至得出所求。

下面我们通过一个简单的例子来进一步的理解欧几里得算法。

假设我们要寻找与之间的。

令 , 由于 , 且 ,而后我们有因此，。

也可以观看下面图像演示的过程：两条线段长分别可表示和，则其中每一小分段长代表最大公约数。

如动画所示，只要辗转地从大数中减去小数，直到其中一段的长度为，此时剩下的一条线段的长度就是和的最大公因数。

欧几里得算法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数的五倍。

法国数学家加布里埃尔·拉梅于 1844 年证明了这点，同时这也标志着计算复杂性理论的开端。

通过上面的例子我们可以看出，欧几里得算法主要是应用了以下几个性质：•及。

•若 ,并且 ,那么这里为整数，为到之间的整数。

其中，第一个性质告诉我们当其中一个数是时怎样找，而第二个性质则告诉我们如何将数字大、计算困难的，转化为数字小，简单的来计算。

同余方程x2=a(modp2)的公式解法
模恰好计算机有着许多简单的求解方法，其中一种求解方法就是求解同余方程。

同余方程是一类常见的代数方程，它是模糊性数学中最有用的工具，广泛应用于密码学和信息安全领域。

特别是对于二次模方程x^2=a(mod p^2),其为特殊的二次模同余方程。

我们可以使用以下步骤来求解二次模方程：
1）首先找出与所要求的模(即p2)互素的质数p1，且p1满足
p1=1(mod 4)
2）设a=b2 mod p2其中b2 mod p2的平方根为b1，那么
b2=b12(mod p2)和b2=b12(mod p1)
3）将幂p1记为P，b12=b1P (mod p2)
4）用欧拉函数找到一个整数x，使得xP=1 (mod p1), 那么假设记b12= c，则c1/x就是x2=a (mod p2)的一个解
上述就是求解同余方程x2=a(modp2)的公式解法，它提供了一种有效的方法来求解二次模方程。

通过求解该同余方程，我们可以实现多种复杂的计算，如生成指定长度的随机整数和求解特定长度密码中所存在的运算问题等。

由此可见，求解同余方程可以大大提高计算机的效率，节省算力，也大大方便了计算机科学家们开展相关研究。

因此，在计算机科学领域，求解同余方程扮演着重要的角色。

同余定理及其应用同余定理是数论中的一个重要定理，广泛应用于代数、密码学、编码理论等领域。

它的核心思想是两个整数除以一个正整数所得的余数相同，则这两个整数被称为同余数。

本文将深入探讨同余定理的理论基础以及在实际应用中的具体应用案例。

一、同余定理的理论基础同余定理的理论基础建立在欧拉定理的基础之上。

欧拉定理表明，若a和n互质（即a与n没有公共因子），则a的φ(n)次方与1模n同余，其中φ(n)表示小于n且与n互质的正整数的个数。

而同余定理则扩展了欧拉定理的应用范围，使得即使a与n不互质，也可以进行同余运算。

同余定理可以形式化地表示为：若两个整数a和b满足a ≡ b (mod n)，其中n为正整数，则a与b除以n所得的余数相同。

二、同余定理的应用案例1. 哈希函数在密码学和信息安全领域，哈希函数被广泛用于将任意长度的输入映射为固定长度的输出。

同余定理可以用于设计哈希函数的压缩函数，通过对输入取模的方式生成哈希值。

同余定理保证了不同输入产生的哈希值在模运算下具有统一的分布特征，从而提高了哈希函数的均匀性和唯一性。

2. 线性同余发生器线性同余发生器是一种常见的伪随机数发生器，通过递推公式生成伪随机数序列。

递推公式的关键就是同余定理。

通过不断对前一项取模，可以生成满足特定分布特征的伪随机数序列。

线性同余发生器被广泛应用于模拟实验、密码学算法以及其他需要随机数的场景。

3. 错误检测与纠正码在编码理论中，同余定理可以用于错误检测与纠正码的设计。

通过巧妙地选择同余定理中的模数，并进行恰当的编码映射，可以实现对输入码字的差错检测和纠正。

这种应用广泛应用于数据传输和存储中，提高了数据的可靠性和完整性。

4. 中国剩余定理同余定理的一个重要应用是中国剩余定理。

中国剩余定理是一种用于求解一组同余方程的方法，即给定一组同余方程，通过对同余定理的灵活应用，可以找到满足全部方程的最小正整数解。

中国剩余定理在数学研究中有广泛的应用，同时也在信息安全和密码学中发挥着重要作用。

同余方程在密码学中的应用与破解密码学是一门研究如何保护信息安全的学科。

在密码学中，同余方程是一种重要的数学工具，被广泛应用于密码算法的设计和密码破解的攻击。

本文将探讨同余方程在密码学中的应用与破解，并介绍一些相关的数学概念和算法。

一、同余方程的基本概念同余方程是指形如a ≡ b (mod m)的方程，其中a、b和m都是整数。

这个方程的意思是a与b在模m下同余，即它们除以m所得的余数相等。

同余方程在密码学中的应用主要涉及到模运算和模反演。

在密码学中，模运算是一种常见的操作，它可以将一个数限制在一个固定的范围内。

例如，在RSA加密算法中，模运算被用来限制明文和密文的取值范围，从而保证计算结果不会溢出。

模反演是指找到一个整数x，使得ax ≡ 1 (mod m)。

在密码学中，模反演被广泛应用于公钥密码算法的密钥生成过程中。

例如，在RSA算法中，模反演被用来生成私钥d，从而实现公钥加密和私钥解密的功能。

二、同余方程在密码算法中的应用1. 公钥密码算法公钥密码算法是一种使用不同的密钥进行加密和解密的算法。

其中，公钥用于加密，私钥用于解密。

同余方程在公钥密码算法中的应用主要涉及到密钥生成和加密解密过程。

例如，RSA算法中的密钥生成过程就是基于同余方程的模反演。

在这个过程中，选择两个大素数p和q，计算它们的乘积n=p*q，并选择一个整数e，使得e与(p-1)*(q-1)互质。

然后，找到一个整数d，使得d*e ≡ 1 (mod (p-1)*(q-1))。

其中，e是公钥，(p,q)是私钥。

通过这个过程，可以得到一对公钥和私钥，用于加密和解密。

2. 散列函数散列函数是一种将任意长度的输入映射为固定长度输出的函数。

在密码学中，散列函数被广泛应用于消息认证码和数字签名等领域。

同余方程在散列函数中的应用主要涉及到数据压缩和冲突检测。

例如，MD5算法是一种常用的散列函数，它将任意长度的输入映射为128位的输出。

MD5算法的设计基于同余方程，利用模运算和模反演来实现数据的压缩和冲突检测。

同余方程与密码学密码学是研究如何保护信息安全的一门学科。

在密码学中，同余方程是一种重要的数学工具，用于设计和破解密码算法。

本文将探讨同余方程在密码学中的应用及其原理。

一、同余方程的基本概念同余方程是数论中的一种基本运算，表示两个数之间在模n下的等价关系。

若两个整数a和b除以一个正整数m所得的余数相等，则称a 与b对模m同余，记作a≡b (mod m)。

其中，≡是同余符号。

二、同余方程的运算性质同余关系具有一些运算性质，方便我们在密码学中进行计算和推导。

1. 传递性：若a≡b (mod m)，b≡c (mod m)，则有a≡c (mod m)。

2. 对称性：若a≡b (mod m)，则有b≡a (mod m)。

3. 反身性：对于任意整数a，都有a≡a (mod m)。

4. 同余关系可以加减：若a≡b (mod m)，c≡d (mod m)，则有a+c≡b+d (mod m)，a-c≡b-d (mod m)。

5. 同余关系可以乘除：若a≡b (mod m)，c≡d (mod m)，则有ac≡bd (mod m)，若c和d互为模m的乘法逆元，则a/c≡b/d (mod m)。

三、同余方程在密码学中的应用同余方程在密码学中有多种应用，其中最重要的是在设计和分析密码算法时使用。

1. RSA算法RSA算法是一种常用的非对称加密算法，使用两个大质数p和q来生成公钥和私钥。

同余方程在RSA算法中起到了至关重要的作用。

在生成RSA的公钥和私钥时，需要解决求解同余方程的问题。

2. 模重构攻击模重构攻击是密码学中的一种攻击方法，即根据已知的加密文本和密钥信息，通过解同余方程来破解密码算法。

这种攻击方法主要利用了同余方程的可逆性，通过对同余方程进行逆向推导，找到加密算法的密钥信息。

3. 凯撒密码凯撒密码是一种替换密码，通过将明文的每个字母按照一定的位移规则进行替换来实现加密。

同余方程在凯撒密码中用于计算字符的移位位置，实现文本的加密和解密。

同余定理同余定理是关于模运算的一个重要理论，它能解决很多与模运算相关的问题。

在数学和计算机科学中，同余定理经常被用于计算和密码学中。

同余定义和符号同余是一个抽象的数学概念，用来描述两个整数之间的关系。

当两个整数除以另一个整数得到的余数相同时，它们被称为同余的。

在数学符号上，同余用符号≡表示，如下所示：a ≡b (mod m)其中a、b、m是整数，称为同余方程，其中mod表示“模”。

实际上，同余定理是一个等式，它表示：对于给定的模数m，如果两个整数a和b满足模数m时的余数相同（即a mod m = b mod m），那么这两个整数就是同余的。

例如，我们可以把它简写成a = b (mod m)，这意味着a和b在模m下有相同的余数。

同余定理的三种形式同余定理有三种形式：基本形式、加法形式和乘法形式。

每种形式都有其独特的特点和用途。

1. 基本形式最常见的同余定理形式是基本形式，也被称为恒等式。

它表示：如果a和b在模m下有相同的余数，那么它们是同余的。

a≡b(mod m) ⇔ a mod m = b mod m2. 加法形式加法形式表示：如果a、b、c在模m下同余，那么a+b、b+c、a+c在模m下也同余。

如果 a ≡ b (mod m) 且 c ≡ d (mod m)，则a + c ≡b + d (mod m)证明：根据同余定义，我们有：a ≡b (mod m)那么，我们可以将a和b分别表示出来：a =b + km其中k是一个整数。

同样地，我们也有：c ≡d (mod m)c =d + lm将它们相加，得到：a + c =b + km + d + lm = b + d + (k + l)m 将其转化为同余符号，得到：a + c ≡b + d (mod m)这证明了加法形式的同余定理。

3. 乘法形式乘法形式表示：如果a、b、c在模m下同余，那么ab和bc在模m下也同余。

如果 a ≡ b (mod m) 且 c ≡ d (mod m)，则ac ≡ bd (mod m)证明：根据同余定义，我们有：a ≡b (mod m)那么，我们可以将a和b分别表示出来：a =b + km其中k是一个整数。

同余定理的定义与应用同余定理（Congruence theorem）是数论中一种重要的工具，用于描述整数之间“除以某个数的余数相同”的关系。

它在密码学、代数、组合数学等领域都有广泛的应用。

本文将从同余定理的定义和基本性质入手，介绍其在数论和应用领域的具体应用。

一、同余定理的定义在数论中，同余定理指的是：对于任意整数a、b和正整数n，如果a与b除以n的余数相同，即a ≡ b (mod n)，则称a与b在模n下是同余的。

同余关系具有以下几个性质：1. 自反性：a ≡ a (mod n)；2. 对称性：若a ≡ b (mod n)，则b ≡ a (mod n)；3. 传递性：若a ≡ b (mod n)，b ≡ c (mod n)，则a ≡ c (mod n)。

二、同余定理的基本性质1. 同余的运算性质（1）同余的和与差性质：若a ≡ b (mod n)，c ≡ d (mod n)，则a+c ≡ b+d (mod n)，a-c ≡ b-d (mod n)；（2）同余的积性质：若a ≡ b (mod n)，c ≡ d (mod n)，则a·c ≡ b·d (mod n)。

2. 模运算的唯一性对于每一个正整数n，模n同余关系分割整数集合Z成了n个完全的互不相交的子集，即[Z] ≡ [0],[1],[2],...,[n-1]。

任何整数都可以唯一地属于其所对应的整数集合。

三、同余定理在数论中的应用1. 同余方程的求解对于形如ax ≡ b (mod n)的同余方程，可以利用同余定理来求解。

设d是a与n的最大公约数，若b能被d整除，方程有解；否则方程无解。

若方程有解，则可以使用扩展欧几里得算法求出方程的一组特解，并通过枚举生成其他所有解。

2. 质数测试同余定理在质数测试中有着重要的应用。

费马小定理和欧拉定理就是同余定理在质数测试中的两个重要应用。

根据费马小定理，若p为质数且a是整数，则a^(p-1) ≡ 1 (mod p)。

同余问题知识点总结一、基本概念1.1 同余关系对于给定的整数a、b和正整数m，如果m能整除a-b，即(a-b)/m为整数，则称a与b 对模m同余，记作a≡b(mod m)。

同余关系满足以下性质：自反性：a≡a(mod m)对称性：若a≡b(mod m)，则b≡a(mod m)传递性：若a≡b(mod m)且b≡c(mod m)，则a≡c(mod m)1.2 同余类对于给定的正整数m，同余关系将整数集合Z划分为m个不相交的子集，这些子集称为同余类。

同余类的定义：[a]={b∈Z|a≡b(mod m)}同余类的性质：同余类是模m下的等价类，它将整数集合划分为m个不相交的等价类。

二、同余的运算规则2.1 加法和乘法的运算规则加法：若a≡b(mod m)且c≡d(mod m)，则a+c≡b+d(mod m)乘法：若a≡b(mod m)且c≡d(mod m)，则ac≡bd(mod m)2.2 幂运算规则对于正整数n，有以下同余关系成立：a≡b(mod m) => a^n≡b^n(mod m)三、同余性质3.1 最小非负剩余对于给定整数a和模m，存在唯一的最小非负整数r，满足a≡r(mod m)且0≤r<m。

r称为整数a对模m的最小非负剩余。

3.2 同余方程同余方程的一般形式为：ax≡b(mod m)同余方程的求解：若最大公约数(gcd)为1，即a与m互质，则同余方程有唯一解；若gcd不为1，即a与m不互质，则同余方程有无穷多解。

3.3 中国剩余定理中国剩余定理：若模数m1、m2、...、mk两两互质，即gcd(mi,mj)=1(i≠j)，则对于任意的整数a1、a2、...、ak和模数m1、m2、...、mk，模方程组x≡a1(mod m1)x≡a2(mod m2)...x≡ak(mod mk)有唯一模m=m1*m2*...*mk的解x。

中国剩余定理的应用：用于快速求解大整数的同余方程组，加速计算过程。

第 2 章 同余运算（一） 内容●同余概念 ●性质 ●剩余类→整数分类 ●模幂运算（二） 重点● 同余及其计算（三） 应用：● 密码学● 公钥密码学【例】 RSA 公钥算法：准备：选大素数p 、q ，记n ＝pq ，φ(n)＝(p －1)(q －1)，再选正整数e ，满足（e ，φ(n)）≡1（mod n ）并求d ，满足 ed ＝1（mod φ(n)）加密：明文串P 编码为数字M ，则密文C ≡e M （mod n ） 解密： M ≡d C （mod n ），再将数字M 解码得明文串P2.1 同余的概念及基本性质(一) 同余概念【定义2.1.1】给定一个正整数m ，两个整数a 、b 叫做模m 同余，如果a －b 被m 整除，或b a m -|，记作b a ≡ ()m mod ；否则叫做模m 不同余，记作a ≠b （（mod m ））【注】由于b a m -|等价于b a m --|，所以同余式b a ≡ ()m mod等价于 b a ≡()()m -mod ，故以后总假定模1≥m 。

判断同余的方法一：利用定义【例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】（定理1）设m 是一个正整数，a 、b 是两个整数，则a≡b（mod m ）⇔存在整数k ，使得a ＝b ＋km 。

（证）a≡b（mod m ） ⇔ b a m -|⇔ 存在k ，使得 a －b ＝km ，即a ＝b ＋km【性质2】（定理2）同余是一种等价关系。

即（i ） 自反性：a≡a 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 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】【性质3】（等价定义）（定理3）整数a 、b 模m 同余⇔a 、b 被m 除的余数相同。

千里之行，始于足下。

同余问题学问点讲解同余问题是数论中的一个重要概念，它在数学中有着广泛的应用。

同余问题的定义是：对于给定的整数a、b和正整数m，假如a-b能够被m整除，则称a与b对于模m同余，记作a≡b(mod m)。

同余问题的本质是数的剩余，即两个数除以某个正整数得到的余数相等。

通过同余问题的争辩，可以得到一些有关数的性质和关系。

同余问题有一些基本性质：1. 若a≡b (mod m) ，则对于任意的正整数k，有 a+k*m≡b+k*m (mod m) ，即同余关系对加法成立。

2. 若a≡b (mod m) ，则对于任意的正整数k，有 a*k≡b*k (mod m) ，即同余关系对乘法成立。

3. 若a≡b (mod m) ，且b≡c (mod m) ，则 a≡c (mod m) ，即同余关系对传递成立。

4. 若a≡b (mod m) ，则 a^n ≡ b^n (mod m) ，即同余关系对幂运算成立。

基于同余性质，我们可以进行一系列的运算和推导。

首先，同余问题可以用来简化计算。

例如，对于不便利计算的大数，可以通过取模运算将其转化为较小的数进行计算，而不转变其同余关系。

第1页/共2页锲而不舍，金石可镂。

同余问题还可以用来求解方程。

例如，对于形如ax≡b (mod m) 的方程，可以通过同余性质进行变形和推导，得到方程的解。

同余问题在密码学中也有重要应用。

例如，RSA算法中的模运算就是基于同余问题的。

同余问题还可以用来进行数字签名和数据加密等操作。

同余问题还与模运算有亲密的关系。

模运算是将一个数除以另一个数得到的余数，而同余问题是比较两个数的余数是否相等。

通过同余问题，可以推导出一些模运算的性质和规章。

最终，同余问题还有一些重要的定理，如中国剩余定理、费马小定理等。

这些定理在数论和密码学中有广泛的应用。

总结起来，同余问题是数论中的一个基本概念，它争辩的是两个数取模后的余数是否相等。

通过同余问题的争辩，可以推导出一些有关数的性质和关系，用来简化计算、求解方程、进行密码学操作等。