密码学的数学基础比较乏味,我本人的文章也只能做到在忠实的转述书本知识上加之自己的一点点通俗理解,学海无涯加油!基础不牢,地动山摇!
本文的行文思路是先介绍什么是因子?再介绍什么是素数?最后拓展到互素数的定义。除了定义外会列出还有这些数学概念在密码学中能用到的性质。
一、因子
(1)因子的定义
如果一个整数 𝑎 能够被另一个整数 𝑏 ()整除(即除以 𝑏 的结果是一个整数),那么我们说 𝑏 是 𝑎 的一个因子。数学上,这可以表示为 𝑏∣𝑎,读作“𝑏 整除 𝑎”。
例如,6 可以被 1、2、3 和 6 自身整除,因此 1、2、3 和 6 都是 6 的因子。
(2)正因子和负因子
通常讨论因子时,我们主要关注正因子,但在某些上下文中,负因子也非常重要。例如,-3 也是一个数 -6 的因子,因为 (−3)×2=−6。
但是,除非特别说明,讨论因子时通常默认只考虑正因子。
(3)整数因子的一些性质
整数 𝑎 整除 1:如果一个整数 𝑎 能够整除 1,那么 𝑎 必须等于 ±1。这是因为1是所有整数的因子,但是1也是唯一一个只有两个因子(即 ±1)的整数。这意味着,如果 𝑎∣1,那么 𝑎 只能是 −1 或 1
𝑎 整除 𝑏,且 𝑏 整除 𝑎:如果 𝑎 能够整除 𝑏,并且 𝑏 也能够整除 𝑎,那么 𝑎 必须等于 ±𝑏。这是因为如果 𝑎∣𝑏 和 𝑏∣𝑎,那么 𝑎 和 𝑏 的绝对值相等,即 ∣𝑎∣=∣𝑏∣。考虑到整除的定义,这意味着 𝑎 和 𝑏 只能是相等或相反数
任意非零整数 𝑏 整除 0:根据整除的定义,如果 𝑏 是非零整数,那么 𝑏 整除 0。这是因为 0=𝑏×0,符合整除的定义。但是,需要注意的是,0 不整除任何非零整数,因为整除的定义排除了除数为0的情况
线性组合的整除性:如果 𝑏 整除 𝑔,并且 𝑏 也整除 ℎ,那么对于任意整数 𝑚 和 𝑛,𝑏 也整除 𝑚𝑔+𝑛ℎ。这是因为如果 𝑏∣𝑔 和 𝑏∣ℎ,那么存在整数 𝑘1 和 𝑘2 使得 𝑔=𝑏𝑘1 和 ℎ=𝑏𝑘2。因此,𝑚𝑔+𝑛ℎ=𝑚(𝑏𝑘1)+𝑛(𝑏𝑘2)=𝑏(𝑚𝑘1+𝑛𝑘2),所以 𝑏 整除 𝑚𝑔+𝑛ℎ
二、素数
(1)素数的定义
素数是大于1的自然数,除了1和它本身以外,不能被其他自然数整除的数。换句话说,素数只能被1和它自身整除。若p不是素数,则成为合数。
例如,2、3、5、7、11、13等都是素数。最小的素数是2,它是唯一的偶数素数。
【注】素数的因子:素数只有两个正因子1 和它自己。例如,17 是一个素数,它的正因子只有 1 和 17
(2)整数分解的唯一性
整数分解可以理解为找一个整数n的所有因子。
对于一个正整数 ,其因子的个数取决于 𝑛 的素数分解。如果 ,其中 是素数,且, 是 的指数,那么 的因子个数为
例如: ;
在密码学中,特别是公钥加密算法的设计和分析中,这些性质经常被利用。例如,RSA算法的安全性就依赖于大整数因子分解的难度。
三、互素数
(1)互素数的定义
介绍互素数的定义之前,得先引入最大公因子。如果c是两个整数a,b的最大公因子那么它必须满足:
- c是a的因子,c也是b的因子,即c是a和b的公因子。
- a和b的任一公因子,也是c的因子。
表示为
下面介绍互素数的定义:两个或多个整数的公因数只有1,那么这个两个或多个整数被称为互素数(或互质数)。换句话说,如果两个或多个整数的最大公约数是1,那么这些整数就是互素的。
例如:8和15是互素的,因为它们没有除了1以外的公共因数。同样,3和5也是互素的。但要注意,互素数不一定都是素数,例如,8和9也是互素的,尽管两者都不是素数。
(2)互素数的性质
- 两个不同的质数一定是互质数:例如,7和11、17和31都是互质数。
- 1和任何自然数(0除外)都是互质数:这是因为1是所有整数的因数,但除了1本身外,没有其他公因数。
- 一个质数和一个合数,这两个数不是倍数关系时互质:例如,7(质数)和10(合数)是互质数,因为10不是7的倍数,且它们的公因数只有1。
- 不含相同质因数的两个合数互质:例如,14(=2×7)和15(=3×5)是互质数,因为它们的质因数完全不同。
- 相邻的两个自然数一定是互质数:例如,4和5、13和14都是互质数。这是因为相邻的两个自然数之间不可能有除了1以外的其他公因数。
互素数在密码学中的应用广泛,特别是在基于欧拉定理的加密算法中,如RSA算法。在RSA算法中,选择的两个大素数的乘积 𝑛 和欧拉函数 𝜙(𝑛) 必须与加密指数 𝑒 互素,这样才能保证加密和解密操作的正确性。