[关闭]
@bintou 2022-09-27T11:17:46.000000Z 字数 4178 阅读 2061

CINTA课的碎碎念

CINTA 算法

2022年CINTA授课笔记

2022年9月

GF乘法及求逆元操作

定义集合,即所有8比特长的二进制串集合。定义集合上的加法、乘法如下:
- 加法等同于异或,即任取
- 乘法只定义乘2的运算。任取,如果的最高比特为0,则(左移一个比特)。如果的最高比特为1,则,也就是说,左移一个比特之后再异或一个八比特的十六进制值。当然,。[提示,因为,由此可以得到中任意值的乘法,回顾一下Simple-Mul的过程。]

大家的任务:
- 写一个程序GF_mul(C或者Python)完成任意中元素的乘法。
- 思考这样一个问题,集合的非零元素会有乘法逆元吗?即,任取,且 ,是否一定存在使得
- 如果我告诉你们答案,以上的问题答案是肯定的,如何求任意元素的乘法逆元?请写一个程序GF_inverse完成这个任务。[提示,还是从egcd算法出发,关键点在于,你们要思考,什么是除法。]

参考答案. 暂时别泄露给20级 :-)

LeetCode上加减乘除相关题目

关于算术基本算法的好资料

The Aggregate Magic Algorithms

2022年7-8月

欧拉公式

两题思考题(20220714)


2021年CINTA课授课笔记

模指数运算

模指数算法的复杂性、内涵远比我们想象的要多很多,有兴趣的同学可以浏览以下链接:
- Efficient modular exponentiation algorithms
- ModPow

第一次作业相关

七月的课前训练

Modular Subset Product Problem (选做题,比较难)

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:

Your works

以下是历史遗留内容。

第二周.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分析里面每一次减半的结论其实是没有了!怎么办呢?

这是另一个版本的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的倍数。)。所以有

因此,有,不是一个整数。矛盾!

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