密码学数学基础(七)

前情回顾

上一篇文章呢，我们通过认识时间来聊到了同余的相关知识，细心的读者可以发现了，在一天的24小时当中，对于某一个整点，比如说一点吧，那么我们是不是能根据整点来对于日期进行一个分类，每个日期的一点都是一组，我们在上文当中也聊到了，同余关系实际上是一种等价关系，因此呢，我们可以借助同余来对所有整数进行一个分类。

背景知识

我们来回顾一下之前所学过的有关于等价关系的知识，后面介绍的相关知识，也会围绕这块展开

❝

「定义1」 定义在集合A上的关系R，如果满足自反性、对称性、传递性，我们称这个关系R为等价关系

❞

上一篇文章已经说过了，同余关系是满足自反性、对称性和传递性的，因此呢同余关系是一种等价关系。

❝

「定义2」 设R是定义在集合A上的等价关系，与A中的一个元素a有关系的所有元素的集合叫做a的等价类

❞

上面这个定义似乎看起来比较抽象，咱们来举一个例子，设A是所有有工作的人构成的集合，考虑定义在集合A上的关系R，那么一个等价类就可以看做是所有的在同一个单位的所有的职员了，这里不考虑那种同时在多个单位工作的情况蛤。

符号和记号

• 表示所有模m同余的数字的集合，即

设m是一个整数，对于任意的整数a，有

剩余类

❝

「定理1」

❞

设m是一个正整数，则

• 对于任意一个整数a, 存在唯一的一个使得, 其中
• 的充要条件为
• 的充要条件为

❝

证明

❞

1）设a为任意的整数，根据带余除法，存在唯一的整数q,r使得

因此有，固.

2）因为所以必要性成立.

下面来证明下充分性，整数a,b满足我们只需要证明，对于任意的整数有然后根据传递性，我们可以得到这也就说明了以及.同理可得以及故.

3）通过2）即可得到必要性成立，下面来证明下充分性，利用反证法，假设即存在整数c同时满足以及那么根据2）可以得到

然后根据对称性可以得到然后再根据传递性可以得到因此这与假设矛盾，固交集为空集。

❝

「定义3」 叫做模m的a的剩余类，一个剩余类当中的任意一数叫做该类的剩余或者代表元. 若是m个整数，并且其中任何两个数都不在同一个剩余类当中，我们称叫做模m的一个完全剩余系

❞

简单的来看一下什么是完全剩余系，也就是我们从每一个分类当中都挑选出来唯一的一个代表元，还是用上面的员工和公司的关系举例子，那么我们是不是可以用所有公司的CEO所构成的集合来做这个完全剩余系，这里还是不考虑同一个职员同时入职多加公司的情况，也就是说完全剩余系当中的每个成员都是一个代表，他可以用来表示整个关系.

好了，有关同余的知识呢就先介绍到这里了，如果想了解更多的有关同余和关系的知识，可以去翻一翻文末的参考资料，最后呢，一如既往的文艺一把,

❝

壮心未与年俱老，死去犹能做鬼雄 — 【宋】陆游

❞

伴随着一天天长大，我们的年龄虽然是在与日俱增，但是呢我们可以保持永远都有一颗十八岁的心，溜了溜了，咱们下次再见~~

参考资料

• 信息安全数学基础 第二版 陈恭亮
• 离散数学及其应用 [美] Kenneth H.Rosen