《抽象代数》第八章讲了有限集合上的置换、轮换、对换的表示法，置换到轮换的分解，置换的奇偶性。

最近在阅读 Charles C. Pinter 的《抽象代数》。选做其中的一些习题。

第五章讲子群。设 (G,·) 是一个群， H ⊆ G 是 G 的子集。当 (H,·) 也是一个群时，则称 H 是 G 的子群（H ≤ G）。

也可用下述条件判定：

1. H 非空
2. ∀x₁,x₂ ∈ H, x₁·x₂ ∈ H （H 对乘法封闭）
3. ∀x ∈ H, x⁻¹ ∈ H （H 对逆元封闭）

这是《高等算术》习题系列的第二篇。 第二章讲了同余关系、同余方程、费马小定理、欧拉函数等。

最近在阅读 Harold Davenport 的《高等算术》。选做其中的一些习题加以巩固，并将解答记录在这里。凡是做了新的习题，只需更新这个页面。

第一章主要介绍了整数的一些运算性质、数学归纳法、整除、质数、唯一分解定理、欧几里得算法。

斑马问题是一个著名的逻辑推理题。流传甚广的“爱因斯坦谜题”的形式与之类似。据维基百科考证，出处为1962年的《生活》杂志。题目内容如下：

1. 有五栋房子。
2. 英国人住在红房子里。
3. 西班牙人养狗。
4. 绿房子里的人喝咖啡。
5. 乌克兰人喝茶。
6. 绿房子紧挨在象牙色房子的右边。
7. 抽Old Gold牌香烟的人养蜗牛。
8. 黄房子里的人抽Kools牌香烟。
9. 中间的房子里的人喝牛奶。
10. 挪威人住在第一间房子。
11. 抽Chesterfields牌香烟的人住在养狐狸的人的隔壁。
12. 抽Kools牌香烟的人住在养马的人的隔壁。
13. 抽Lucky Strike牌香烟的人喝橙汁。
14. 日本人抽Parliaments牌香烟。
15. 挪威人住在蓝色房子的隔壁。

问题是：谁喝水？谁养斑马？

“海内存知己，天涯若比邻。”信息技术使得后半句真正地成为了现实。人与人之间的联系不仅摆脱了空间的隔阂，在时间上也几乎没有障碍，此所谓“即时通讯”。

具体而言，即时通讯指的是一类特定的软件服务，这类服务允许用户注册账号，并在互联网上向其他账号发送信息。信息的接收方可以即时发表回应。你一言我一语，俗称“聊天”，因此即时通讯软件也被称为聊天软件。

即时通讯没有广为接受的标准化方案。现实情况是，由商业公司开发一套专有（proprietary）的解决方案，并免费地提供给用户使用。不同的服务提供商之间的用户不可以互相通讯。

这样的现状有很多缺点。首先，社交性质类软件，流行的主要条件并非技术上的优越性，而是用户基础。用户对服务提供商不具备选择权，只能被动地接受服务提供商的所谓“服务条款”以及隐私权政策，他们的权利便受到此类条款的限制。

使用这类即时通讯服务，不可避免地会有用户的隐私被传输至服务器端。服务提供商是否能够妥善处理，存在重大的疑问。极坏的情况，用户隐私可能会被出售。一般的情况，服务提供商有可能分析用户行为，并对其推送具备针对性的广告。再退一步，即使服务提供商完全合规运营，服务器也存在被入侵而导致数据泄露的隐患。这些问题，是专有解决方案集中化的本质决定的。

最近因为更换了新的电脑，所以尝试在Windows 10上使用 WSL 代替双系统的配置。WSL 2采用了虚拟化的技术，并且具备一个真正的Linux内核。WSL 2的VM相比传统的全系统VM而言更加精简，并且Linux和Windows系统之间的可交互性更好：

• 每个操作系统都可以通过9P协议访问对方的文件系统；
• 每个操作系统都可以较方便地调用另一个操作系统的程序。例如，在PowerShell中使用grep一类的工具。
• Linux的文件系统储存在 .vhdx 文件中，可以动态扩展和收缩，不需要单独分区；
• VM的占用的内存是根据实际使用情况动态调整的。

听起来是个不错的选择。在新的预览版中，WSL 2更提供了GPU和GUI的支持。不过，我还没有用到预览版。

使用对称密钥通信时，双方需要事先约定密钥。如何安全地操作是一个关键问题。Diffie-Hellman-Merkle算法使得在不安全的信道中交换密钥成为可能。

在Diffie-Hellman-Merkle算法中，事先约定整数G和M。通信双方Alice和Bob分别拥有自己的私钥a和b。Alice把自己的公钥A=G^a发送给Bob。同理，Bob把B=G^b发送给Alice。Alice计算B^a，Bob计算A^b。这样，他们就得到了共享密钥K=G^ab。

注意，这里的乘法是模 M 的乘法，即A=G^a mod M，等等。对于取模的指数运算，其逆运算是一个目前难以解决的问题。对于外界的观察者而言，只知道G、M、A、B，并不能容易地求出a、b或K。这样就确保了密钥交换过程的安全性。

在实践中，常用密钥派生函数KDF对密钥K进行处理，用派生密钥KDF(K)作为对称加密的实际密钥。

自古以来，有大量信息需要隐秘地传输，例如军事机密。密码学也随之发展起来。一种常用的加密算法是对称加密算法，它由加密函数E和解密函数D构成：

    C=E(T,K)
    T=D(C,K)

其中T为明文，C为密文。信息的传输双方事先约定一个共用的密钥K。密文可以在不安全的信道中传递，即使被敌人截获，在未知密码的情况下也很难恢复出原文。

n 元集合 {0,1,…,n-1} 的 k 元子集共有 \(n\choose k\) 个。 设某个子集的元素为 \(c_1<c_2<\cdots<c_k\)， 则该子集可以编码为 \[{c_k\choose k} + \cdots + {c_2\choose 2} + {c_1\choose 1}.\]

此编码最小值为 0， 最大值为 \[{n-1\choose k} + \cdots + {n-k+1\choose 2} + {n-k\choose 1} = {n\choose k}-1.\] 上式的证明： 在两边加上 \(n-k\choose 0\) 并使用恒等式 \({n\choose k}={n-1\choose k-1}+{n-1\choose k}\)。