写给自己看,大佬们请移步,谢谢~

没有人可以请教真的是太痛苦了,大哭。

参考书:Kenneth H. Rosen《初等数论及其应用第六版》

学了一天回到宿舍后,看了看刚发下来的课本,原来《信息安全数学基础》这门课学的就是初等数论,那我还自学干嘛。。。直接听老师讲吧。

本文基本不再更新,除非有些知识是课堂上不涉及的。

如有课堂笔记我会另开一贴。(flag已立)。说实话,除了韩老师的课之外,我很多专业课也大都是水下来的。忏悔一秒种。

符号表

image-20200906224932197

第二章

乘法

明天写

除法

明天写

第三章

3.3 最大公因子及其性质

P69 定理3.7

image-20200906225036323

推导中使用的是公因子,而不是最大公因子。

所以我的理解是,(a, b)(a + cb, b)的所有公因子均相同。

因而自然会有最大公因子gcd(a, b) = gcd(a + cb, b)

P69 定理3.8

image-20200906225056844

证明出整数r是a, b的线性组合之后的一步,我的理解是这样的:

整理出r = a - dq = a - q(ma + nb) = (1 - qm)a - qmb

由带余除法的定义式可知,余数r必然满足0 <= r < d

注意,r是a, b的线性组合,因为1 - qm -qm都是整数。既然是a, b的线性组合,那自然也满足我们前面假设的d是a,b的线性组合的最小的正整数这一条件。

所以r的最小正整数取值为d,但是不等式的右边又取不到等号,那就只能取0了。

一但r取0,就意味着前面的带余除法的等式中的余数为0,即d整除a.

P71 定理3.9

image-20200906225236251

R = {ma+nb | m,n属于Z} ,S = {gcd(a, b) * k | k属于Z},证R = S

即证R包含于S,且S包含于R.

前者:

记d是a,b的最大公因子,所以d|a且d|b,所以d|(ma+nb),即有ma+nb = kd,注意,这里并不能直接推出R = S,因为此处的k并不一定会包含整数集内的所有整数,所以等式右边只是S中的一部分元素,因此只能推出R包含于S.

后者:

由定理3.8,一定存在r,s使得d = ra+sb(a,b的最大公因子是a,b的线性组合的最小正整数),所以有jd = jra + jsb。j是整数集内所有元素,但是jr和js未必能够遍历整数集,所以这里推出S是R的一部分,即S包含于R.

二者结合,证毕。

P71 定理3.10

image-20200906225316611

本定理较易理解,可概括为:两个不全为零的整数a,b的最大公因子是能被其他所有的公因子整除的正公因子。

有几个点需要注意:

  • 是正公因子。比如15和25的最大公因子是5,但是-5也是他俩的公因子,只不过是最小的。
  • 如果某个公因子不能被另一个公因子整除,那么一定会有一个更大的公因子,即这二者的最小公倍数(我觉得哈。

P72

image-20200906225327674

两两互素的条件比互素的条件强。

前者可推后者,反之不可

3.4 欧几里得算法

P75 欧几里得算法

image-20200906225402860

原理是定理3.7:gcd(a+bc, b) = gcd(a, b)

按照这个原理,每次运算时,将较大的那个参数表示成带余除法的形式(a+bc),注意该形式中两个相乘的数,有一个必须是较小的那个参数b(这样才能满足定理3.7的形式啊),即带余除法的除数。然后用余数a代替原来的较大的那个参数,求余数a与除数b的最大公因子。

提问,为啥要将较大的那个参数表示成带余除法的形式呢?表示较小的那个数不行吗?

当然不行,但是你这样做就不是优化运算了,反倒是复杂化运算了。

比如gcd(x=ky+r, y), x<y,可以等效成gcd(r, y),由于x小于y,所以k必然小于等于0。如果k等于0,那r等于x,你相当于没优化运算;如果k小于0,那么r反而比x大,恭喜你成功进行了反向“优化”。

image-20200906225540019

为啥最后一个等式会是这种形式的呢?(r(n-1) = r(n)q(n)

首先要明确,gcd(a, b) = gcd(|a|, |b|),所以本算法中的参数均选择相应的绝对值,必为非负数。

回答分两种:

  • 为什么不是r(n-1) = r(n)q(n) + r(n+1)呢?

因为如果此时余数r(n+1)不为0,则还要继续算下去,直到余数为0

  • 为什么不是r(n-1) = r(n+1),即 r(n)q(n)等于0呢?

答案很简单,如果r(n-1) = r(n+1),即商q(n)为0,被除数等于余数。但是,余数r(n+1)是必须小于除数r(n)的,即可推导出r(n-1) = r(n+1) < r(n)。但是,我们很容易知道r(n-1)是必然大于r(n)的(因为r(n-1)是倒数第二个等式的除数,r(n)是倒数第二个等式的余数),产生矛盾,因此假设不成立。

Last modification:September 6th, 2020 at 10:56 pm