互质
若 a 和 b 的最大公因子为 1，则称 a 和 b 互质。
互质关系有:
- 任意两个质数互质
- a 是质数，b 不为 a 的倍数，则 a 与 b 互质
- 1 和任意自然数互质
- p 是大于 1 的整数，则 p 和 p-1 互质
- p 是大于 1 的奇数，则 p 和 p-2 互质
- …
同余
当两个整数除以同一个正整数，若得相同余数，则二整数同余
两个整数a, b若它们除以正整数m所得的余数相等，则称a, b对于模m同余，记作：
相乘：
若
证明：
除法原理一:
若
证明：
由于c, m互质，则
费马小定理
假如 a 是一个整数，p 是一个质数，那么
如果 a 不是 p 的倍数，这个定理也可以写成
简单证明:
任意取一个质数，比如 7，给定数集 { 1,2,3,4,5,6 } ，给这些数都乘上一个与 7 互质的数，比如 3， 得到 { 6,12,18,24,30,36 }, 对于模 7 来说，这些数同余于 { 6,5,4,3,2,1 } ， 这些余数实际上就是集合 { 1,2,3,4,5,6 }
把 { 1,2,3,4,5,6 } 做阶乘，得到
得:
由于
如果用 p 代替 7，用 a 代替 3，就得到 费马小定理
欧拉函数
欧拉函数 小于或等于 n 的正整数中与 n 互质的数的数目
若 n 为一个质数，那么
欧拉定理
欧拉定理 如果两个正整数 a 和 n 互质，则 n 的欧拉函数
可以让下面的等式成立：
欧拉定理中的一种特殊情况，当 n 为质数时，可得 费马小定理:
模反元素
模反元素 如果两个正整数 a 和 n 互质，那么一定可以找到整数 b，使得 ab - 1 被 n 整除.
证明:
由 欧拉定理 可得：
RSA 加密算法
步骤：
- 第一步，生成两个随机的不相等的大质数 p 和 q，它们的积
的二进制位数就是密钥的位数，通常设置的位数有 1024，2048，3072，4096 等 - 第二步，计算 p 和 q 的乘积 n
- 第三步，计算 n 的欧拉函数
, 得 - 第四步，随机选择一个整数 e，条件是 1 < e <
, 且 e 与 互质
在 openssl 中
固定为 65537 > [知识点]费马数: 对于 ，通常可选 3, 5, 17, 257 和 65537。因为它们都是质数，且二进制中只有 2 位是 1，可以加快 d 的计算。这几个 e 的可选值实际是费马数的前 5 个数，费马数定义是 , 到 都是质数，但是从 开始就不是质数了。 例如： ，实际应用中通常选择 作为 .
-
第五步，计算 e 对于
的模反元素 d -
第六步，将 n 和 e 封装成公钥，n 和 d 封装成私钥
-
第七步，定义好了公私钥，则对信息
，加密和解密函数如下： - 公钥 n, e 加密:
- 私钥 n, d 解密:
需要证明:
- 公钥 n, e 加密:
- 常用于客户端公钥加密数据然后服务端私钥解密获取原始数据
- 常用于服务端私钥加密签名数据，客户端公钥解密获取签名数据并校验签名
实例
- 第一步：
- 第二步：
- 第三步：
- 第四步：
- 第五步：
- 第六步：公钥
, 私钥 - 第七步：假定
, 代入公式：
可靠性
使用数字:
公钥: ( n 和 e )
私钥: ( n 和 d )
那么已知 n 和 e 的情况下，可以推导出 d 吗？
, 只有知道 和 才能算出 ; ，只有知道 和 ，才能算出 ; ，只能将 因数分解，才能算出 和 .
结论：如果
唯一质数分解定理：任何一个大于 1 的正整数 n 都可以 唯一分解 为一组质数的乘积，其中
都是自然数(包括 0) 大数质因数分解
证明
证明其一即可，即证：
证明：
由于
-
假设:
与 互质: 由欧拉定理有: 由此：
得证。
-
假设:
与 不是互质关系: 此时，由于 等于质数 和 的乘积，所以 必然等于 或 ，假设 ，由于 必然与 互质，由费马小定理得: 这时 t 必然能被
整除，即 , 得: 由
， ，得: 得证。
证毕。
来自量子计算的挑战
RSA 加密系统能够确保安全的前提是，没有一个计算机能够在可接受的时间内分解一个极大整数，即使是超级计算机也要花费数年的时间。
基于量子计算机的质因数分解算法——Shor 算法，这种算法最吸引人的地方是，它能够将质因数分解问题的复杂度，从指数难度降低到近多项式难度
shor 算法 Grover 量子搜索算法