主要涉及数论方面的复习（大概是 NOIP 难度），目的为复习使用，因此与其他博客相比会更为简略，想要更详细的介绍也附上了相应的链接。

仅供大家参考，如有错误请指出。

内容太简单，大佬不要喷啊。>-<

先发一部分，后面的会慢慢补。

• upd on ： 学习并补充了阶和原根，二次剩余。
• upd on ： 添加范德蒙德卷积

根据费马小定理有（(p) 为质数）：

扩展欧几里得（exgcd）

只要这个数满足下面两个条件中的一个，就可以通过素数测试：

其中 (a) 是我们选择的一个小质数，在 (100) 选择 (8 sim 12) 个就基本能保证正确性。

如果一个数是素数，一定会通过素数测试；如果一个数是合数，很大概率不会通过素数测试。

复杂度应该是 (O(klog^2 n))，因为需要枚举一个 (r)，还有龟速乘。(k) 是选取的 (a) 的数量。

求解最小的满足下面条件的 (x)，保证 (a ot p)。

考虑所有 (j in [0,t-1])，求出 (ba^j) 并把他们放入哈希表，然后枚举 (i) 查找有无这个值，这样我们就能求出一个合法的 (x)，取最小值即可。

中国剩余定理（CRT）

用于求解线性同余方程，在模数互质的情况下适用。

扩展中国剩余定理（exCRT）

用于求解线性同余方程，模数互质不互质均适用。

一种暴力的，求解线性同余方程的方法。码量和理解难度都很小。

几个用来证明原根存在的定理：

• 定理 1：对于奇素数 (p) ，(p) 有原根。

王元在 (1959) 年证明了，若 (m) 有原根，其最小原根是不多于 (m^{0.25}) 级别的。（这启发我们可以暴力找最小原根）

一个数 (a)，如果不是 (p) 的倍数且模 (p) 同余于某个数的平方，则称 (a) 为模 (p) 的 二次剩余。而一个不是 (p) 的倍数的数 (b)，不同余于任何数的平方，则称 (b) 为模 (p) 的 非二次剩余。

对二次剩余求解，也就是对常数 (a) 解下面的这个方程：

通俗一些，可以认为是求模意义下的开方。

找到一个数 (a) 满足 (a^2-n) 是 非二次剩余，至于为什么要找满足非二次剩余的数，在下文会给出解释。 这里通过生成随机数再检验的方法来实现，由于非二次剩余的数量为 (frac{p-1}{2})，接近 (frac{p}{2})，所以期望约 2 次就可以找到这个数。

建立一个＂复数域＂，并不是实际意义上的复数域，而是根据复数域的概念建立的一个类似的域。 在复数中 (i^2 = -1)，这里定义 (i^2 = a^2 - n)，于是就可以将所有的数表达为 (A+Bi) 的形式，这里的 (A) 和 (B) 都是模意义下的数，类似复数中的实部和虚部。

可以理解为在大小为 (n) 和 (m) 的两个堆中选择 (k) 个点的方案数

感觉比较显然，把前面一个组合数转化成 (inom {n}{n-i}) 在利用上面的结论就行了。

密码学中的加密方式从密钥的数量方向可以分为对称加密和非对称加密，对称加密只使用一把密钥来对数据进行加解密，而非对称加密使用两把密钥来进行加密，分别为公钥和私钥。对称加密和非对称加密有很多非常出名的算法，例如：对称加密比较有名的算法有 DES 和 AES，非对称加密有 RSA 和 ECC。对称加密和非对称加密各有优缺点，那么咱们怎么去利用他们的优缺点呢? 本章我们将分别从理论和实践的角度分析对称加密和非对称加密，让更加容易地理解对称加密和非对称加密。

1.关于对称加密和非对称加密

我们都知道，密码体制有两种: 对称密码体制( 又称为单钥密码体制) 和非对称密码体制( 又称为双钥密码体制或公钥密码体制) 。对称密码体制使用相同的密钥( 秘密密钥) 对消息进行加密/解密，系统的保密性主要由密钥的安全性决定，而与算法是否保密无关。

对称密码体制设计和实现的中心是: 用何种方法产生满足保密要求的密钥以及用何种方法将密钥安全又可靠地分配给通信双方。对称密码体制可以通过分组密码或流密码来实现，它既可以用于数据加密，又可以用于消息认证。非对称密码体制使用公钥加密消息，使用私钥来解密。使用非对称密码体制可增强通信的安全性。

在密码学体系中，对称加密、非对称加密、单向散列函数、消息认证码、数字签名和伪随机数生成器被统称为密码学家的工具箱。其中，对称加密和非对称加密主要是用来保证机密性；单向散列函数用来保证消息的完整性；消息认证码的功能主要是认证；数字签名保证消息的不可抵赖性。这篇文章所要讲诉的就是保证消息的机密性的对称密码和非对称密码。

对称加密又称但密钥加密，整个加密过程中只使用一个密钥。所谓对称其实就是使用一把密钥加密，使用同一把密钥解密。对称加密由于加解和解密使用的是同一个密钥算法，故而在加解密的过程中速度比较快，适合于数据量比较大的加解密。

对称加密的主要有优点就是算法公开、计算量小、加密速度快、加密效率高；但是它也存在强大的缺点，缺点就是密钥协商过程中，一旦密钥泄露，别人可以获取到密钥，这样也能对密文进行解密。另外，每对用户每次使用对称加密算法时，都需要使用其他人不知道的独一密钥，这会使得收、发双方所拥有的钥匙数量巨大，密钥管理成为双方的负担。

两种经典的对称加密算法

DES 加密解密算法最初由美国 IBM 公司研究人员所设计发明，且为第一个公开的商用密码算法标准，自诞生以来便得到了 ISO 的一致认可。DES 是分组密码算法的典型代表，它的明文分组长度为 64bits，密钥长度为 64bits，其中包括有 8bits 的奇偶校验，因此有效密钥长度为 56bits。DES 加密解密算法使用的过程相同，且可以随时均都可以进行变动。它们其中有极少数被认为是易破解的弱密钥，但是很容易抛开它们不使用，因此其自身安全性主要依赖于有效密钥。

DES 算法加密过程首先先对明文分组进行操作，需要加密的明文分为每块 64bits 的固定大小。下图所示左右两部分分别为64bits 的明文分组加密过程和其 16 个子密钥生成的过程。

• 子密钥获取流程 子密钥的获取流程如下图

此处，用户输入 64 位的密钥。根据密钥置换表 PC-1，将 64 位变成 56 位密钥（此处去掉了奇偶校验位）。 PC-1 置换得到的 56 位密钥。此处密钥被分为前 28位 C0 和后 28 位 D0。分别对它们进行循环左移，C0 左移得到 C1，D0 左移得到 D1。 将 C1 和 D1 合并变成 56 位。然后通过 PC-2 表进行压缩置换，得到此轮的 48 位子密钥 K1。 再对 C1 和 D1 进行相同的左移和压缩置换，获取下一轮的子密钥……一共进行 16 轮，于是可以得到 16 个 48 bits 的子密钥。

• 异或运算 将 P 盒置换的结果与最初的 64bits 分组的左半部分异或，然后左、右半部分交换，接着开始另一轮。

• S 盒扩展 当产生了 48bits 密钥后就可以和明文进行异或运算，便可得到 48bits 的密文。再开始下轮的 S 盒迭代运算，其功能是把 6bit数据变为 4bits 数据，每个 S 盒是一个 4 行、16 列的表。每个 S盒的使用方法为：S 盒收到 6bits 的输入，6bits 的第 1 个 bit 和最后 1 个 bits 构成的 2 位二进制为该 S 盒行号，中间的 4bits 二进制为该 S 盒的列号，然后根据行号和列号查 S 盒定义表得到对应的值（通常为十进制），该值就是 S 盒变换的输出，并转化为二进制。

• P 盒置换 S 盒代替运算之后，输出 32bits，作为 F 函数最后一个变换 P 盒置换的输入。将该 32bits 位数据进行 P 盒置换，置换后得到一个仍然是 32 bits 的结果，此处可得 F 函数的输出值。

AES 加密算法为分组密码，分组长度为 128 位即 16 个字节，密匙长度有128、192 或 256 位，根据密匙 长 度的不同，加密的轮数也不同，本文采用长度为 128 位的密匙，加密轮数为 10 轮。AES 加密算法不仅编码紧凑、设计简单而且可抵抗多种类型的攻击，其基本结构包括 ４个部分。这四个部分分别为字节替换、行位移、列混合和轮密匙加。

字节替换也就是通 过 S-BOX 对字节元素进行非线性的变换，S-BOX 由有限域 GF(2 的 8 次方) 上的乘法求逆运算和仿射变换运算而来，通过查表的方式即可直接得到变换前后的字节元素，替换后字节元素至少有两位发生变换，能 充分打乱原来的字节元素，本文所介绍的 AES 加 密 算 法 就是对 S-BOX 进行改 进 而 来。具体替换规则为假设一字 节为 xy，则 S-BOX 中第ｘ行第ｙ列所对应的元素就是替换后的元素。

行位移是 AES 加密算法中的一个简单线性运算，即在 4 x 4 的状态矩阵中，把第ｉ行循环左移ｉ个字节(i＝0, 1, 2, 3)。

列混合是将状态矩阵中的每一列看成一个多项式，让其与一个固定的多项式 a(x) 相乘，再做模多项式 m(x) = x4（x的四次方） + 1 的运算，其中 a(x)＝’03‘x3（x的3次方）+ ’01‘x2（x的平方）+ '01'x + ‘02’。

轮密匙加变换就是让状态矩阵与经过密匙扩展得到的子密匙做异或运算，因此轮密匙加变换的逆变换就是其本身，其中子密匙是原始密匙通过密匙扩展算法得到的。

下图是整个算法的流程图

AES 加密算法先将 128 位的明文进行分组，得到一个 4x4 的明文状态矩阵作为算法的输入，然后选取密匙矩阵先对明文状态矩阵做一次轮密匙加变换，再经过 10 轮的轮函数加密，轮函数操作依次为字节替换、行位移、列混合和轮密匙加，其中由于最后一轮的列混合不仅不会提高安全性，反而会拉低 算 法 运 算 速 度，故该轮丢弃列混合变换。解密算法仍为 10 轮，由于算法的4个轮操作均为可逆变换，因此解密过程就是用与加密过程同样的密匙对每一轮的加密操作进行逆运算。

非对称加密又称为公钥密码，该技术是针对私钥密码体制（对称加密算法）的缺陷被提出来的，非对称加密会产生两把密钥，分别为公钥（Public Key）和私钥（Private Key），其中一把密钥用于加密，另一把密钥用于解密。非对称加密的特征是算法强度复杂、安全性依赖于算法与密钥但是由于其算法复杂，而使得加密解密速度没有对称加密解密的速度快。对称密码体制中只有一种密钥，并且是非公开的，如果要解密就得让对方知道密钥。所以保证其安全性就是保证密钥的安全，而非对称密钥体制有两种密钥，其中一个是公开的，这样就可以不需要像对称密码那样传输对方的密钥了。这样安全性就高了很多。

常用的非对称加密算发有 RSA、Elgamal、背包算法、Rabin、D-H、ECC（椭圆曲线加密算法）等。

两种经典的非对称加密算法

RSA 算法是一种迄今为止理论上比较成熟和完善的公钥密码体制，是非对称密码体制的典型代表。在网络、信息安全等许多方面都使用 RSA 算法，特别是 RSA 算法典型应用在通信中的数字签名，可实现对手的身份、不可抵赖性验证。在身份认证、信息安全、电子商务中有着广泛的应用前景。

RSA 算法由密钥的产生、加密算法和解密算法 3 个部分组成。

1. 产生两个大素数 p 和 q ；

2. 取序对 (e,n) 为公钥，可公开；(d,n) 为私钥，对外保密。

将要发送的字符串分割为长度为 m < n 的分组，然后对分组 mi 执行加密运算，得到密文 ci ：ci ≡(mi)e mod n

收到密文 ci 后，接收者使用自己的私钥执行解密运算，得到明文 mi ：mi ≡(ci)d mod n

RSA 详细的算法设计流程

Miller-Rabin 算法是一种基于概率的素数测试方法，在密码学的素数产生中，由于该算法的速度快、原理简单、易于实现，成为进行素数检测的最佳选择。

Miller-Rabin 算法是对费马算法改进，它的操作步骤如下：

1. 再取不同 a 要的值对 n 进行 t = 5 次测试，如果每次测试结果为 n 是素数，则以高概率判定 n 是素数。假设 n 通过 t 次测试，则判定结果错误的概率是1/4t；若只通过一次测试，素数判定的错误概率是 25%。

通过上面的的大素数生成模块，可以得到大素数 p和大素数 q ，根据欧拉函数 φ(n) =(p - 1)(q - 1) ，同时密钥 e 与 φ(n) 互质，根据中国剩余定理可以计算密钥e 。

得到 e 后，就可以通过公钥 (e,n) 进行加密得到密文 C 。在 RSA 加密过程中，为了计算 ci ≡(mi)e mod n ，采用快速指数算法。将快速指数算法描述为三元组(M,E,Y) ，其初始值为 (M,E,Y ) =(mi,e,1) 。重复执行以下操作：

RSA加密和解密算法设计

椭圆曲线加密算法（ECC）是基于椭圆曲线数学的一种非对称密码算法，是建立在基于椭圆曲线的离散对数问题上的密码体制。随着分解大整数方法的进步以及各方面的完善，RSA 算法渐渐不能满足现状，ECC 算法的需求性逐渐增大。ECC 以其明显的“短密钥”优势得到了广泛应用，并逐渐被确定为许多编码方式的数字签名标准。当然，ECC 还有许多未解决的问题，不过这种引用了丰富数学理论的算法，也印证了将更多数学有较大可行性理论应用到密码学这一领域中。

首先从数学角度阐释算法加密原理，ECC椭圆曲线加密算法数学基础是利用有限域上椭圆曲线离散对数问题（ECDLP）的计算困难性，所谓椭圆曲线是指由韦尔斯特拉方程。其椭圆曲线方程如下：

下面是椭圆曲线方式图示

其中，系数 ai 定义在某个域上（密码算法中需要把之前连续曲线变为有限域上的点，故 ai 也定义在有限域中）。曲线上所有点和一个无穷远点构成一个集合连同定义上的加法（eg：a+b≡c (mod p)）构成阿贝尔群。由于曲线上每一点都是非奇异点，故可在椭圆曲线上找到两点 P、Q，且存在如下关系式：

由此可见，已知 m、P 求 Q 较为容易，反之由 Q 逆向求 m、P 难度却较大，椭圆曲线密码正是基于该机制来展开设计及应用。

secp256k1 是区块链项目中应用最多的椭圆曲线算法，源于比特币中的应用，后来的大多数区块链项目如以太坊等都在用。名称中的前三个字母sec代表Standards for Efficient Cryptography (SEC)，后面的p256K1指的是参数256位素数域。Secp256k1为基于Fp有限域（又名伽罗瓦域）上的椭圆曲线，由于其特殊构造的特殊性，其优化后的实现比其他曲线性能上可以特高30％，有明显以下两个优点：

1）占用很少的带宽和存储资源，密钥的长度很短。 2）让所有的用户都可以使用同样的操作完成域运算。

在平面中的椭圆曲线上的加法在几何上根据线截取曲线的位置来定义。我们不会在这里讨论几何，除了说它归结为一组涉及实数的方程。但我们并没有在实数域上去工作，而是在有限域。有限域p，其中

这里选择p相对接近2^256。它不是小于2^256的最大素数; p和2^256之间有很多素数。其他因素也同样影响着选择p。请注意，我们不是在整数mod p本身工作，而是在一个阿贝尔组中，其加法法则由整数mod p上的椭圆曲线定义 。

二.密钥的压缩格式和非压缩格式

以“未压缩的形式”。 基点是椭圆曲线上特别选择的点，因此它是一对数字mod p，而不是单个数字。

该压缩的形式：只给 x，你就应该解决 y。在未压缩的 形式为您提供了 x 和 y。但是，这些数字是略微编码的。在压缩形式中，字符串以“02”或“03”开头，字符串的其余部分是 x 的十六进制表示 。将满足 y 的两个值

并且“02”或“03”告诉您选择哪一个。如果压缩形式以02开头，则选择最低有效位为偶数的根。如果压缩形式从03开始，则选择其最低有效位为奇数的根。（两个根将添加到 p，而 p 是奇数，因此其中一个根将是偶数，一个将是奇数。） 未压缩形式：未压缩的将始终以04开头。在此之后，按照 x 和 y 连接在一起的十六进制表示形式 。

一：几种著名的椭圆曲线的方程和对应的实际应用 1.魏尔斯特拉斯曲线和基于魏尔斯特拉斯曲线的若干种椭圆曲线公钥算法

Curve）在曲线的公式上有所不同，因此他们不兼容。蒙哥马利曲线和爱德华曲线的算法，能做到“Time-constant”，也就是说不论他们进行运算的数值是多少，他们所花的时间是相同的，因此“时间旁路”（Time side channel）攻击就对它们无效。

三：Curve25519介绍和迪菲赫尔曼密钥交换 Curve25519 是目前最高水平的 Diffie-Hellman函数，适用于广泛的场景，由Daniel J. Bernstein教授设计。在密码学中，Curve25519是一个椭圆曲线提供128位安全性，设计用于椭圆曲线Diffie-Hellman（ECDH）密钥协商方案。它是最快的ECC曲线之一，并未被任何已知专利所涵盖。

给定一个用户的32字节密钥，curve25519计算该用户的32字节公钥。给定该用户的32字节密钥和另一个用户的32字节公钥，curve25519计算一个32字节的共享密钥提供给这两个用户使用。然后可以使用这个秘密对两个用户进行身份验证和信息加密。方程为：

Curve25519的构造避免了许多潜在的实现方面陷阱，它不受计时攻击，能接受任何32字节字符串作为有效公钥(实际工程应用中，0除外)，并且不需要验证给定点是否属于曲线，或者是否由基点生成。2013年斯诺登事件以后，得到大量关注和使用，目前应用已经非常广泛，包括ssh, tls,OpenSSL,Libsodium等，实际成为NIST P-256椭圆曲线算法的替代品(前者被广泛质疑有后门(back door))

1.迪菲赫尔曼秘钥交换

Diffie–Hellman key exchange，缩写为D-H， 是一种安全协议，用于双方在一个不安全的通信网络上建立一个 共享的秘钥，有了共享秘钥以后，就可以使用这个密钥加密交互消息。由于通信双方最终使用的密钥相同，所以可以认为该协议目标是创建一个对称密钥（对称密钥和非对称密钥可自行学习）。该协议也称迪菲－赫尔曼密钥协商，名字以发明人的名字命名，符合惯例，无其他特殊意义。

迪菲－赫尔曼密钥交换本身是一个匿名（无认证）的密钥交换协议，它却是很多认证协议的基础，并且被用来提供传输层安全协议的短暂模式中的前向安全性。

First有自己的私钥a,Second有自己的私钥b,a,b均小于p,且私钥绝对保密。

进而达到共享秘钥的目的，二者通信可通过Fkey这个公共秘钥加密后面的通讯内容。整个过程中因为只有g , p,A,B是公开的，私钥a,b保密的，故基于离散对数运算，敌人很难破解公共秘钥。

迪菲－赫尔曼密钥交换本身并没有提供通讯双方的身份验证服务，所以有可能会被中间人攻击。一个中间人在信道的中间分别和A，B进行两次迪菲－赫尔曼密钥交换，就能够成功的向A假装B，向B假装A。此时攻击者可以读取任何一个人的信息并重新加密信息，然后传递给另一个人。因此通常都需要一个能够验证通讯双方身份的机制来防止这类攻击。有很多种安全身份验证解决方案使用到了迪菲－赫尔曼密钥交换。当A和B共有一个公钥基础设施时，他们可以将他们的返回密钥进行签名；STS以及IPsec协议的IKE组件已经成为了Internet协议的一部分。

四：ED25519签名过程 Ed25519使用了扭曲爱德华曲线，签名过程和最大的区别在于没有使用随机数，这样产生的签名结果是确定性的，即每次对同一消息签名结果相同。一般说来随机数是安全措施中重要的一种方法，但是随机数的产生也是安全隐患，著名的索尼公司产品PS3密钥泄露事件，就是随机数产生的问题导致的。如果你对Schnorr,secp256k1，sm2 等签名过程比较熟的的话，就容易理解如果在签名过程中出现了这个相同的随机数r,那么私钥将很容易被计算出来，造成泄露。

1. Ed25519公钥生成算法流程

1. Ed25519验证签名算法流程

(1)解压R为点坐标R’；

(2)解压pk为点坐标A；

(4)验证SB=R’+kA是否成立，若成立则验签成功。

混合加密-对称加密和非对称加密的实际应用场景

所谓混合加密就是使用在实际的应用中把对称加密和非对称加密结合起来使用。我们都知道非对称加密算法比对称加密算法慢数千倍，但在保护通信安全方面，非对称加密算法却具有对称密码难以企及的优势。所以在实际的应用中，都是对称加密与非对称加密混合使用。取其优势，去其糟粕，达到完美使用的一个目的。

对称加密技术，即专用密钥加密技术或单钥密码技术，加密密钥与解密密钥一致，发送方与接收方用同一组的公私密钥对加密或者解密信息。数据加密的一个关键要求是有相同的密钥才能解密。因为通信双方共享密钥，如果密钥丢失或泄露，那么获取密钥的人就可以加密或者解密数据，所以为保证消息的机密性必须保障密钥的安全。 这种算法比较简单且计算量比较小，对网络开放、从而能够效率高地加密。同时存在的缺点，一是通讯双方基于通过非面对面的方式协商一个共同的密钥，因此不能保证协商过程的安全性。二是通讯双方每次进行数据传输时都使用惟一密钥，这使得对称加密技术在开放型的网络中需要使用和生成大量的密钥，对于密钥的管理就成为用户的很大负担。三是对称加密算法只能对数据进行加解密，保证数据的机密性，但无法验证通讯双方的真实身份，不能确定数据的完整性。

非对称密钥加密技术，由公钥和私钥形成一个密钥对，其中公钥向公众公开，私钥归密钥持有人单独保管。通讯双方使用非对称密钥对数据进行加密和解密时，必须使用相互匹配的公钥和私钥。它有两种方式：一种是发送方用接收方的公钥来加密信息，接收方用其私钥解密信息，这样接收方可以收到多个发送方传来的加密数据，且此加密数据只有接收方一个用户可以解读；另一种即发送方利用自身的私钥加密信息，接收方用对方公钥解密信息，这样一个信息有可能被多个接收方解密。 非对称密钥加密技术的优点是简化了密钥的发放及管理的过程，支持数字签名等安全认证技术，缺点是加密和解密的计算过程特别复杂，运行数据加密和解密的速度比较慢。

问同学们一个问题：10以内，任取两个自然数互质的概率是多少呢？

对于这样的问题，没有其他办法，好在10这个范围不大，可以用枚举方式来进行。

黄色区域是互质，白色区域有除1以外的

其中1与任何数都是互质的，任意素数之间也都是互质的。

于是我们得出10以内的自然数互质的概率就是63/100=0.63。

那我们再扩展一丢丢呢，1000以内呢？其实也可以通过归纳的方式得出来，可以避开这种一一枚举的笨办法，但是也仍然很费事。接下来，我们来挑战一个真正的问题，在全体自然数中，任意两个数互质的概率是多少呢？

研究数的性质基本上都要归结于素数

这个问题有点难度，但是结合上面10以内互质枚举的列表，我们先来收集一些特征。

我们发现，似乎两个数是否互质，跟素数有很大关系。比如2，会跟哪些数互质呢？很明显，1,3,5,7,9。这些全部都是奇数，占到所有数字的1/2,与2不互质的概率也为1/2。3呢？会跟哪些数互质呢？那就是，1,2,4,5,7,8,10由于这里我们只列举了10以内的情况，所以这里互质的概率是7/10，假如我们列举到12以内的情况，这个概率就等于8/12，等于2/3了，那么与3不互质的概率就是1/3。依次分析5,7，你会发现一个有趣的事实。

任取一个数与某个素数p不互质的概率都是1/p，因为只有p的整数倍才会与p有公约数。那么任意自然数与p互质的概率就是1-1/p。我们现在来给全体素数从小到大做个排列。

任取两个自然数，这对自然数与2互质的概率就是1-(1-1/2)*(1-1/2),与3互质的概率就是1-（1-1/3）*(1-1/3)。依次类推，从全体自然数取出两个自然数都互质，那就要与任何一个素数都互质了。于是这个概率就是

任意两自然数互质的概率

这个大π是个连乘符号，表示将后面所有的式子都连乘起来的积。这个符号看起来有点恐怖，但并不是一点办法都没有。观察一下（1）式，我们来对这个式子进行处理。

到了(2)式之后，我们接下来就将全体的P1,P2,P3的具体数值代入进去。于是有

当工作进行到(3)式了，就必须转换思维了，否则工作就将无法进行下去。我们来回想小学时候学过的基础数学概念，把一个合数分解成若干个素数相乘的形式。这个过程叫分解素因数，但是你有没有想过，为什么把合数只分解成若干个素数相乘的形式，而不是分解成别的什么形式。

这里主要有2点原因，第一，素数的乘积可以表示成任意合数，第二，这种分解成素数乘积的形式是唯一的。第一条是显而易见的，因为合数分解到都是素数乘积的时候就只能停止了，因为素数只有本身和1两个约数了，再分解就没有意义。第二条在数学上有个高大上的名字——算术基本定理，与代数基本定理齐名。

欧几里得最先发现算术基本定理

好了，现在有上面两大前提，我们就可以对(3)式进行处理了。分数的括号里，都是1与素数的倒数平方的幂和，这里已经列举了所有素数，倘若我们对这个分母全部进行展开，我们就将获得全部自然数的倒数平方的幂和，因为这里的素数平方会跟其余所有素数都乘上一次。

于是，我们继续下面的工作。

这里的(4)式分母恰好是全体自然数的倒数平方和，接下来该怎么办呢？没办法，我们又要请出大神欧拉了。

1735年，28岁的欧拉历史上第一次求出这个级数的和，这个曾经难倒莱布尼兹，牛顿的超级难题，从此名扬天下。下面简单看下欧拉的超神解法。

欧拉关于巴塞尔级数的求解

于是巴塞尔级数的和是π^2/6=1.645，那么P=1/1.645≈0.6079。这与我们一开始仅枚举10以内的任意两数互质的概率0.63，就已经很接近了，说明了这个概率会随着自然数范围的扩大而迅速收敛！

虽然没有明确资料表示第一个求出任意两个自然数互质概率的人是谁，但晓然菌觉得很大可能就是欧拉。因为在欧拉的18世纪，数学工具还是很少的。你想求出这个概率，不管你用什么样子的开头，到最后都会归结于求巴塞尔级数的和，而欧拉作为第一个求出巴塞尔级数的人，又怎么会放过这么一个如此精彩的成果呢？

那么，假如有同学要继续扩展，任意取出3个自然数互质的概率又是多少呢？这不是晓然菌钻牛角尖，这样的问题历史上当然也有人研究过。采用类似的办法，当最后，你就会得出一个全体自然数倒数的立方和是多少？

黎曼大神为素数问题操碎了心

很遗憾，这个全体自然数倒数的立方和用欧拉的方式就行不通了，欧拉的方式只能针对于自然数倒数的偶次方幂和。事实上，这个立方和的确存在，但是你不能用任何有理式来表达，你只能通过无穷级数来表示。

数学史上，从不缺乏那些充满毅力的人，很早就有人计算得出，全部自然数倒数的立方和约是1.2021，那么任意三个自然数互质的概率就是1/1.，任意四个自然数互质的概率是1/(π^4/90)=0.924。这也符合我们的直观感受，你一次性取的自然数越多，那么它们都互质的概率就越大。

从这么个小小的问题上，我们也不难发现，任何跟数字相关的研究话题，到最后本质上都会归结于素数的某些性质。从两千年前的欧几里得时代到现在，素数的奥秘仍然被揭示得很少。18,19世纪是数学各个领域开疆拓土的最好时代，在那个伟大的时代里诞生了的数学大师们仍然在影响着现在。

特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。