@bintou
2022-09-27T11:17:46.000000Z
字数 4178
阅读 2061
CINTA
算法
定义集合,即所有8比特长的二进制串集合。定义集合上的加法、乘法如下:
- 加法等同于异或,即任取,。
- 乘法只定义乘2的运算。任取,如果的最高比特为0,则(左移一个比特)。如果的最高比特为1,则,也就是说,左移一个比特之后再异或一个八比特的十六进制值。当然,。[提示,因为,由此可以得到中任意值的乘法,回顾一下Simple-Mul的过程。]
大家的任务:
- 写一个程序GF_mul(C或者Python)完成任意中元素的乘法。
- 思考这样一个问题,集合的非零元素会有乘法逆元吗?即,任取,且 ,是否一定存在使得?
- 如果我告诉你们答案,以上的问题答案是肯定的,如何求任意元素的乘法逆元?请写一个程序GF_inverse完成这个任务。[提示,还是从egcd算法出发,关键点在于,你们要思考,什么是除法。]
参考答案. 暂时别泄露给20级 :-)
The Aggregate Magic Algorithms
n个元素分成两个非空子集,有多少种分法?Why?
定义n元素的Cycle(圈)如下,比如,四个元素,A B C D 形成一个圈,B C D A也是圈,但是这两圈我们认为是同一个圈。但是,A C D B就是另一个圈了。请问,n个元素会形成多少个不同的n元素圈?
模指数算法的复杂性、内涵远比我们想象的要多很多,有兴趣的同学可以浏览以下链接:
- Efficient modular exponentiation algorithms
- ModPow
Given a list of primes, e.g., from 2 to nth prime, denoted as , and an integer and a prime . To find a bits vector , such that:
[
]
大家如果阅读这个bianry egcd算法有问题,应该大多都出现在repeat里面的那两个while,特别是s和t不能同时被2整除的时候。都被2整除,大家应该能懂。
要理解这里,关键点还是我常强调的,别想太多,动笔算一算!
其次,大家有没有注意到那两个变量和在整个算法过程中都不变?这里就是我CINTA书里面强调的:和只是占位符,并不直接参与计算。那这里为什么出现了和?
说到这里,我们回想一下egcd在做什么?一直在保持 这一类型等式的成立。所以,和不变。现在要除2,等式的左边要干啥?保持平衡啊!怎么才平衡,凑数!比如:
问题是,你怎么确保和一定被2整除?
这里其实我也没想到更好的说明办法,那就分情况讨论嘛。
1、a和b同为奇数时;因为r为偶数,所以,s和t必须同为偶数或者奇数。可得!
2、a为奇数,b为偶数时;因为r为偶数,所以,这里我偷个懒,大家自己分析。
其他都比较容易。但是复杂性分析还是不容易的。有同学说,与gcd算法一样,其实不一样。为什么?注意那个repeat主循环,每次迭代r和r'只是做一次减法,注意,这里真是减法,不是gcd里面的mod运算。所以gcd分析里面每一次减半的结论其实是没有了!怎么办呢?
这是另一个版本的Binary-GCD算法。
作业错得很离谱,错得很典型。基本功缺失严重。
改作业两点意见:第一,不接受任何的MD文件和Html文件。如果你扔个pdf、c或者jpg,我还能看到,稍可忍受,MD文件、Html文件我怎么看啊?统统打回。第二就是不懂MarkDown的同学太多。打回。
大部分同学需要补一下大一的这一课:计算思维训练简要指南。
第一个问题就要问:求乘法逆元输入什么,输出什么?返回一个void型,这能对吗?
第二,gcd和egcd有什么共同点。既然计算了egcd还需要gcd吗?
第三,egcd的输出是什么?它的输出就是乘法逆元?
关于努力,应该有不少同学会说,我会努力的!我也相信大多数同学内心确实也是努力的!相信我。只是,相信归相信,还是靠事实说话。
我在课堂派出了两道所谓的扩展练习作业。其实根本不是难题,也不是什么扩展作业,就是基本作业里面抽出来,命名为扩展作业而已。出题至今大概两周了吧?提交答案的只有区区的2人次。
大学不是中学,没有什么超纲不超纲,没有什么上纲上线。学习无上限!我不会因此就说大家不努力。但是我坚信这个事实说明了很多问题。什么问题,你们自己说吧。
以后不会有所谓的扩展练习就是了。
题目:对任意正整数,数列,设。请问最大的是什么?为什么?
提示:首先编程算,找规律。找到规律之后就硬算。利用了Bezout定理。
我刚从一本书里看到的,看了解答,不很繁琐,就是硬做,所以,感觉没什么意思。
对任意素数,是循环群,且存在个生成元(原根)。
给定任意正整数,的所有因子分别记为,其中包括和。记函数:
证明,对任意素数,。
证明,对任意素数,,是任意正整数。
证明,对任意素数和,。
证明函数是积性函数,即对任意的正整数和,如果,则。提示:既然与互素,则它们之间就不存在大于一的公因子,那么它们的因子相乘之后作用于欧拉函数会满足什么特性?
最后,完成证明的任务。提示:任意整数都是素数的乘积,即。
答案:因为是的子群,根据拉格朗日定理,的阶整除的阶,即,是一个整数。又因为是的真子群,所以,,所以。
设群的阶是,是素数。请证明,如果不是循环群,即不存在阶元素,那么必然存在阶的元素,而且也必然存在阶的元素。
定义商群,再定义映射,是定值(一个正整数)。请问这是不是良定义映射,为什么?
这个学期我们讲过整数乘法的算法,复杂度是,2019年已经有人提出了复杂度为O(n log n)的算法,这里有文章。 目前大家当然是看不懂了,我也没有看,估计也看不懂。只是报告这个消息给大家,让大家注意,这些看上去简单的算法持续有人在研究。
之前GMP使用的是基于FFT的Schönhage–Strassen algorithm,那篇博客里面也说到了。复杂度是O( n log n (log log n)) 。
任取环中的元素,都满足,请证明环是交换环。
证明(以下是一个错误的证明,请找出错误):
根据假设有。所以有:
这是2019级CINTA考试中唯一一道不出现在课堂与作业的“难题”,答对率极低,其实客观说,也不难。
题目Z是整数环。请证明环 2Z 不与环 3Z 同构。(8分)
设是从到 的环同构,则 (请注意,是环,有两种操作 )。所以有
记为,是某整数(因为中的元素就是3的倍数。)。所以有
因此,有,不是一个整数。矛盾!