[关闭]
@bintou 2020-11-12T03:32:26.000000Z 字数 2261 阅读 146

CINTA课的碎碎念

CINTA 算法


第二周.Binary egcd的正确性分析

[
]
大家如果阅读这个bianry egcd算法有问题,应该大多都出现在repeat里面的那两个while,特别是s和t不能同时被2整除的时候。都被2整除,大家应该能懂。

要理解这里,关键点还是我常强调的,别想太多,动笔算一算!

其次,大家有没有注意到那两个变量在整个算法过程中都不变?这里就是我CINTA书里面强调的:只是占位符,并不直接参与计算。那这里为什么出现了

说到这里,我们回想一下egcd在做什么?一直在保持 这一类型等式的成立。所以,不变。现在要除2,等式的左边要干啥?保持平衡啊!怎么才平衡,凑数!比如:


但是,不能同时被2整除时,失败!
于是,想到(怎么想到的,算法里面不是这样做的吗?哈哈哈...)

变形得到

问题是,你怎么确保一定被2整除?
这里其实我也没想到更好的说明办法,那就分情况讨论嘛。
1、a和b同为奇数时;因为r为偶数,所以,s和t必须同为偶数或者奇数。可得!
2、a为奇数,b为偶数时;因为r为偶数,所以,这里我偷个懒,大家自己分析。

其他都比较容易。但是复杂性分析还是不容易的。有同学说,与gcd算法一样,其实不一样。为什么?注意那个repeat主循环,每次迭代r和r'只是做一次减法,注意,这里真是减法,不是gcd里面的mod运算。所以gcd分析里面每一次减半的结论其实是没有了!怎么办呢?

第三周. 关于作业的几个问题

作业错得很离谱,错得很典型。基本功缺失严重。

改作业两点意见:第一,不接受任何的MD文件和Html文件。如果你扔个pdf、c或者jpg,我还能看到,稍可忍受,MD文件、Html文件我怎么看啊?统统打回。第二就是不懂MarkDown的同学太多。打回。

大部分同学需要补一下大一的这一课:计算思维训练简要指南

第三周--关于乘法逆元的三个问题

第一个问题就要问:求乘法逆元输入什么,输出什么?返回一个void型,这能对吗?

第二,gcd和egcd有什么共同点。既然计算了egcd还需要gcd吗?

第三,egcd的输出是什么?它的输出就是乘法逆元?

国庆假期--关于努力

关于努力,应该有不少同学会说,我会努力的!我也相信大多数同学内心确实也是努力的!相信我。只是,相信归相信,还是靠事实说话。

我在课堂派出了两道所谓的扩展练习作业。其实根本不是难题,也不是什么扩展作业,就是基本作业里面抽出来,命名为扩展作业而已。出题至今大概两周了吧?提交答案的只有区区的2人次。

大学不是中学,没有什么超纲不超纲,没有什么上纲上线。学习无上限!我不会因此就说大家不努力。但是我坚信这个事实说明了很多问题。什么问题,你们自己说吧。

以后不会有所谓的扩展练习就是了。

国庆假期的思考题

题目:对任意正整数,数列,设。请问最大的是什么?为什么?

提示:首先编程算,找规律。找到规律之后就硬算。利用了Bezout定理。

我刚从一本书里看到的,看了解答,不很繁琐,就是硬做,所以,感觉没什么意思。

一种群论数论结合的原根定理证明

原根定理

对任意素数是循环群,且存在个生成元(原根)。

证明思路

是阶为的群,对任意的,记的阶为必然整除,即的某个因子。中存在多少个元素的阶为?至多个(CINTA,推论7.1)。

枚举的所有因子(包括本身),累加


请注意,这个结论与原根属性无关!是欧拉函数的属性。

以上两点结合,必有个阶为的元素。

欧拉函数的一种性质

给定任意正整数的所有因子分别记为,其中包括。记函数:


现在需要证明。为完成这个任务,请依次完成以下小任务:
- 证明,对任意素数

作业一例

答案:因为的子群,根据拉格朗日定理,的阶整除的阶,即是一个整数。又因为的真子群,所以,,所以

思考题

思考题一

设群的阶是是素数。请证明,如果不是循环群,即不存在阶元素,那么必然存在阶的元素,而且也必然存在阶的元素。

思考题二

定义商群,再定义映射是定值(一个正整数)。请问这是不是良定义映射,为什么?

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注