CINTA课的碎碎念

CINTA 算法

2022年CINTA授课笔记

2022年9月

GF乘法及求逆元操作

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

大家的任务：
- 写一个程序GF_mul（C或者Python）完成任意$GF$中元素的乘法。
- 思考这样一个问题，集合$GF$的非零元素会有乘法逆元吗？即，任取$a \in GF$，且 $a \not = 0$，是否一定存在$b \in GF$使得$a * b = 1$？
- 如果我告诉你们答案，以上的问题答案是肯定的，如何求任意元素的乘法逆元？请写一个程序GF_inverse完成这个任务。[提示，还是从egcd算法出发，关键点在于，你们要思考，什么是除法。]

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

LeetCode上加减乘除相关题目

• Power of 2
• 加法题
• 除法题
• 完全平方数
• x的n次方

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

The Aggregate Magic Algorithms

2022年7-8月

欧拉公式

• 斌头老师教你记住欧拉公式

两题思考题（20220714）

• n个元素分成两个非空子集，有多少种分法？Why？

• 定义n元素的Cycle（圈）如下，比如，四个元素，A B C D 形成一个圈，B C D A也是圈，但是这两圈我们认为是同一个圈。但是，A C D B就是另一个圈了。请问，n个元素会形成多少个不同的n元素圈？

---

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 $P = \{ p_0, p_1, \cdots, p_{n-1}\}$, and an integer $X$ and a prime $q$. To find a $n$ bits vector $x \in \{0, 1\}^n$, such that:

$$\prod p_i^{x_i} \equiv X \pmod{q}$$

Your works

• Write a Sage (Python) program to solve the MSP problem. For example, we let the parameters $n = 40$, $X = 4462431763815383677508$ and $q = 10396403247585105914591$.
• Anaylize the efficience of your progrm, and try to improve.
• What is the relation between Subset Sum Problem(SSP) and Subset Product Problem?
• How hard is the MSP problem? Give a postulate, and prove. (I don't think you can do it.)

以下是历史遗留内容。

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

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

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

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

说到这里，我们回想一下egcd在做什么？一直在保持 $as + bt = r$这一类型等式的成立。所以，$a$和$b$不变。现在$r$要除2，等式的左边要干啥？保持平衡啊！怎么才平衡，凑数！比如：

$$(as + bt)/2 = r/2$$
但是，$s$或$t$不能同时被2整除时，失败！
于是，想到(怎么想到的，算法里面不是这样做的吗？哈哈哈...)
$$(as + bt)/2 + ab/2 - ab/2 = r/2$$
变形得到
$$a (s + b)/2 + b(t - a)/2 = r/2$$

问题是，你怎么确保$(s + b)$和$(t - a)$一定被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人次。

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

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

国庆假期的思考题

题目：对任意正整数$n$，数列$a_n = 100 + n^2$，设$d_n = gcd(a_n, a_{n+1})$。请问最大的$d_n$是什么？为什么？

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

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

原根定理

对任意素数$p$，$Z_p^*$是循环群，且存在$\phi(p - 1)$个生成元（原根）。

欧拉函数的一种性质

给定任意正整数$n$，$n$的所有因子分别记为$d_0, d_1, \cdots , d_r$，其中包括$1$和$n$。记函数：

$$F(n) = \phi(d_0) + \phi(d_1) + \cdots + \phi(d_r)$$
现在需要证明$F(n) = n$。为完成这个任务，请依次完成以下小任务：
- 证明，对任意素数$p$，$F(p) = p$。

• 证明，对任意素数$p$，$F(p^2) = p^2$。

• 证明，对任意素数$p$，$F(p^k) = p^k$，$k$是任意正整数。

• 证明，对任意素数$p$和$q$，$F(pq) = pq$。

• 证明函数$F$是积性函数，即对任意的正整数$m$和$n$，如果$gcd(m,n) = 1$，则$F(mn) = F(m)F(n)$。提示：既然$m$与$n$互素，则它们之间就不存在大于一的公因子，那么它们的因子相乘之后作用于欧拉函数会满足什么特性？

• 最后，完成证明$F(n) = n$的任务。提示：任意整数$n$都是素数的乘积，即$n = p_0^{k_0} p_1^{k_1} \cdots p_t^{k_t}$。

作业一例

答案：因为$H$是$G$的子群，根据拉格朗日定理，$H$的阶整除$G$的阶，即$|G|/|H| = n$，$n$是一个整数。又因为$H$是$G$的真子群，所以，$n \geq 2$，所以$|H| \leq |G|/2$。

思考题

思考题一

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

思考题二

定义商群$G/H$，再定义映射$\phi(gH) = g^kH$，$k$是定值（一个正整数）。请问这是不是良定义映射，为什么？

好消息

这个学期我们讲过整数乘法的算法，复杂度是$O(n^2)$，2019年已经有人提出了复杂度为O(n log n)的算法，这里有文章。 目前大家当然是看不懂了，我也没有看，估计也看不懂。只是报告这个消息给大家，让大家注意，这些看上去简单的算法持续有人在研究。

之前GMP使用的是基于FFT的Schönhage–Strassen algorithm，那篇博客里面也说到了。复杂度是O( n log n (log log n)) 。

题解

任取环$R$中的元素$x$，都满足$x^2 = x$，请证明环$R$是交换环。
证明（以下是一个错误的证明，请找出错误）：
根据假设有$(a + b)^2 = a + b$。所以有：

$$(a + b)^2 = a^2 + 2ab + b^2 = a + 2ab + b = a + b$$
同理，
$$(b + a)^2 = b + a = b + 2ba + a = a + b = a + 2ab + b$$
整理可得：
$$ab = ba$$
所以，$R$是交换环。

考试题解

这是2019级CINTA考试中唯一一道不出现在课堂与作业的“难题”，答对率极低，其实客观说，也不难。

题目Z是整数环。请证明环 2Z 不与环 3Z 同构。（8分）

答案

设$\phi$是从$2\mathbb{Z}$到$3\mathbb{Z}$ 的环同构，则$\phi(4)=\phi(2*2)=\phi(2+2)$ (请注意，$\mathbb{Z}$是环，有两种操作 )。所以有

$$\phi(2)\phi(2)=\phi(2)+\phi(2)$$
记$\phi(2) \in 3\mathbb{Z}$为$3k$，$k$是某整数（因为$3\mathbb{Z}$中的元素就是3的倍数。）。所以有
$$\phi(2)\phi(2)=3k * 3k = 9k^2 = 6k = 3k + 3k = \phi(2)+\phi(2)$$
因此，有$k=2/3$，不是一个整数。矛盾！