密码学数学基础(四)

好了，我们接着来学习小学二年级的数学，咳，不，是密码学相关是数学知识，这次我们来回顾回顾，我们小学一年级学过的数数儿[^1]。

前情回顾

上一篇文章，我们通过小朋友分铅笔的例子，由于可能存在不够整分的情况，因此呢，我们这里引入了带余除法，然后呢，这里能看到我这篇文章的读者们大概率不会是小学二年级的水平，然后呢我们稍微调整下我们学习的思路，这节课就当一节复习课了，我们来复习一下我们小学就学过的数数儿，

整数的表示

从封面图，我们可以看到，对于24这个数来说，我们是，也就是两捆儿10个的小棒加上4根儿单独的小棒，作为一个学会数数的读者，相信我们应该对于这个并不会陌生，但是呢，数学吧，这玩意来源于生活它又高于生活，正常我们所使用的都是10进制，然后对于学过计算机的读者可能遇到过2进制，8进制或者16进制，这里我们直接给出一个一般性的表示.

❝❝

「「定理1」」 假设并且b > 1，则对于每个正整数n，都可以表示为

❞❞

其中，并且，首项系数.

这个应该是不难理解，对于b=10就是我们常见的例子，实在不理解的，可以参考上面小学一年级的教材仔细看看，应该也就理解了。然后呢，我们还是来证明下这个东西，那么为什么咱们小学先学的数数儿，然后咱们这个数数要到现在才讲呢，因为这个证明是需要用到咱们上一篇文章所讲到过的带余除法的，好了，还是老规矩，不喜欢证明的可以直接略过这一部分.

❝❝

「「证明」」[^2]

❞❞

• **存在性: **我们先来证明这个表达式的存在性，也就是这个表达式是存在的，具体方法呢，就是不断的使用带余除法.

根据带余除法，我们可以得到

然后，我们针对在来做一次带余除法，可以得到

然后，我们针对继续往下操作，可以逐步得到如下的结果

注意到，

$$0 leqslant q_{k-1}<q_{k-2}<cdots<q_{2}<q_{1}<q_{0}<n $$=""使得

然后，我们通过上面所得到的式子，逆向带回去，我们可以一次得到

这样，我们就得到了上面我们所使用的表达式.

• **唯一性: **接下来我们来证明这个表达式的唯一性，我们不妨利用反证法，假设它不唯一，然后存在两个表达式

两个式子相减，可以得到

不妨假设j是最小的正整数使得，可以得到

或者

我们可以得到

然后，根据整除的的定义，我们可以得到

注意到

因此对于这个是矛盾的，因此可以说明我们前面假设是错误的，因此n的表达式是唯一的.

符号(Notation)

这里，我们又来加入一个新的符号表示，通过上面的例子，我们发现，如果我们要表示一个b进制的数字，那么我们要写的东西实在是很多，对于数学来说，这当然是不可忍受的，因此呢，有了下面的记号

来表示

其中，并且，首项系数,然后，我们称其为整数n的b进制表示.

四则运算

前面，我们用b进制数来表示了整数，捎带着回顾了一下我们小学一二年级学过的知识，那么接下来呢，我们接着来回顾下，我们小学二年级学过的四则运算[^3].

加法运算

设，，则

好了，这里让我们来回顾一下小学所学过的加法运算的过程，来个竖式计算

• 1)如果否则，取

• 2)如果$a_{1}+b_{1}+d_{0}

• k)如果$a_{k-1}+b_{k-1}+d_{k-2}

• k+1)最后，取.

看到这里，估计各位读者心里和我一样，心里一万匹羊驼飞过吧，这么一长串的式子，到底是干了个啥，这里，咱们来简单的说道说道，大家把这玩意看做是我们正常用的竖式计算，然后注意一点，这里不再是满10进一了而是满b进一，看成竖式再来看上面的表达式，就应该会清晰很多了.

减法运算

这里，减法运算实际上是加法运算的逆运算，这里就不给出完整的描述了，我们只需要取一下逆元，然后进行加法运算就可以了，有关于什么是逆元呢，可以去翻一下我之前有关于有限域介绍的文章[^4]，当然如果还是想去看这个减法是怎么描述的，可以参考[^2]里面的描述，这本书里面是完整的来了一遍减法的操作。

乘法运算

对于乘法运算，这里就需要一点点知识了，因为小学二年级学的是乘法口诀，所以到了小学三年级，才真正的学到了乘法，我们先来看一下当时我们是如何进行乘法运算的吧[^5]

然后，我们来看下对于一般的b进制数，我们应该如何做乘法运算.

设，，则

具体的计算过程如下

• 1)对于j=0，计算

• 2)对于j=1计算

• l) 对于j = l - 1, 计算

• l+1) 最后，计算得到最终的结果.

这里还是，大家想想当时竖式是怎么计算的，然后在理解上面这一坨的表达式，应该就明白了，这里我也不啰嗦了，有兴趣的读者可以自行的研究研究，如果不感兴趣，这块其实作用也不大.

除法运算

我们依然还是老样子，先来回顾一下小学三年级所学过的除法运算[^6]

有关于除法，我这块本来也不想重复下书里面的内容，这其实也就是算个逆元就好了，但是吧，你看着我们小学学过的除法运算的样子都和乘法不一样，所以呢，这里也就再来啰嗦一遍了.

设，，不妨设，则求商 余数使得

$$n=q cdot m+r, quad 0 leqslant r<m $$=""

• 1)计算

$$n_{1}=left(a_{1, k_{1}-1} a_{1, k_{1}-2} cdots a_{1,1} a_{1,0}right)_{b}=left{begin{array}{ll}n-m cdot b^{k-l}, & text { 如果 } n geqslant m cdot b^{k-l}, n-m cdot b^{k-l-1}, & text { 如果 } n<m cdot="" b^{k-l}="" .end{array}right.="" $$=""

• 2)如果，则终止运算，否则继续计算

• $$n_{2}=left(a_{2, k_{2}-1} a_{2, k_{2}-2} cdots a_{2,1} a_{2,0}right)_{b}=left{begin{array}{ll} n_{1}-m cdot b^{k_{1}-l}, & text { 如果 } n_{1} geqslant m cdot b^{k_{1}-l},

• n_{1}-m cdot b^{k_{1}-l-1}, & text { 如果 } n_{1}<m cdot="" b^{k_{1}-l}="" .="" end{array}right.="" $$="" $$vdots=""

• s-1)如果，则终止计算，否则计算

• $$begin{aligned} n_{s-1} &=left(a_{s-1, k_{s-1}-1} cdots a_{s-1,1} a_{s-1,0}right)_{b}

• &=left{begin{array}{ll} n_{s-2}-m cdot b^{k_{s-2}-l}, & text { 如果 } n_{s-2} geqslant m cdot b^{k_{s-2}-l},

• n_{s-2}-m cdot b^{k_{s-2}-l-1}, & text { 如果 } n_{s-2}<m cdot="" b^{k_{s-2}-l}="" .="" end{array}right.="" end{aligned}="" $$=""

• s)最终，,有以及q的

• $$n=q cdot m+r, quad 0 leqslant r<m $$=""

到这里，有关整数的加减乘除运算就都介绍完了，这篇文章，相对来说公式是比较多的，不过读者也别害怕，如果没有看懂呢，这篇文章不看问题实际上也不大，因为后面有关密码学的知识，能用到这块知识不多，但是为了知识的完整性呢，咱们也单独来讲一下，好了又到了说再见的时候了

❝❝

不经一番寒彻骨，怎得梅花扑鼻香 —黄檗禅师【唐】

❞❞

没有人能够随随便便成功，世上没有捷径，通向成功的路都需要翻山越岭，拜拜~~~~

参考资料

[^1]: 苏教版一年级下册数学^[1]

[^2]: 信息安全数学基础_陈恭亮^[2]

[^3]: 苏教版小学数学二年级上册^[3]

[^4]: https://mp.weixin.qq.com/s/r_QOcDFqXW3biIpS0rjAJg^[4]

[^5]: 苏教版三年级下册数学^[5]

[^6]: 苏教版小学数学三年级上册^[6]

ReferenceReference

[1]

苏教版一年级下册数学: "苏教版一年级下册数学"

[2]

信息安全数学基础_陈恭亮: "信息安全数学基础_陈恭亮"

[3]

苏教版小学数学二年级上册: "苏教版小学数学二年级上册"

[4]

https://mp.weixin.qq.com/s/r_QOcDFqXW3biIpS0rjAJg: https://mp.weixin.qq.com/s/r_QOcDFqXW3biIpS0rjAJg

[5]

苏教版三年级下册数学: "苏教版三年级下册数学"

[6]

苏教版小学数学三年级上册: "苏教版小学数学三年级上册"