小赛码/数论
竞赛/数论
质数
一、质数:数字的原子
-
原子是构成物质的基本单位
-
质数是构建整数的基本单元
示例:
60 = 2 × 2 × 3 × 5
(仅由质数构成)
所有大于1的自然数都可分解为质数的乘积
类比说明:
质数如同数学界的乐高积木,通过组合可构建任意整数
二、质数:现代密码的基石(RSA加密)
-
保护移动支付、即时通讯、数据传输的核心技术
-
RSA加密原理:
基于大质数乘积的数学特性:正向计算易,逆向分解难
三、质数的分布特性
前20个质数序列:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71...
分布规律:
-
密度递减:数字越大,质数出现频率越低
-
间距不规则:存在紧密对(如11-13)和巨大间隔(如113-127)
研究思考题:
为何质数分布不遵循简单规律?
能否建立有效的质数预测模型?(尚未解决)
RSA加密算法详解
一、核心机制
通过三个关键步骤实现信息安全:
步骤 | 操作 | 数学基础 |
---|---|---|
密钥生成 | 选择两个超大质数p,q | 质数无限性 |
加密过程 | 计算n=p×q及公钥 | 大数分解困难 |
解密过程 | 使用私钥还原信息 | 欧拉函数特性 |
安全核心:
当 n 超过 300 位时,暴力分解需数亿年计算时间
一、RSA 算法原理详解
1. 密钥生成步骤
第一步:选择两个不同的大质数
p = 61
q = 53
第二步:计算模数n和欧拉函数值φ(n)
n = p × q = 61 × 53 = 3233
φ(n) = (p-1)×(q-1) = 60 × 52 = 3120
- n作为公钥的一部分公开
- φ(n)用于后续密钥计算
第三步:选择公钥指数e
e = 17 (需满足1 < e < φ(n)且gcd(e, φ(n))=1)
第四步:计算私钥指数d
d ≡ e⁻¹ mod φ(n)
通过扩展欧几里得算法求得d = 2753
∵ 17 × 2753 = 46801 ≡ 1 mod 3120
2. 加密解密过程演示
加密消息m=65
c = m^e mod n = 65¹⁷ mod 3233 = 2790
解密过程
m = c^d mod n = 2790²⁷⁵³ mod 3233 = 65
二、质数判定算法
1. 试除法(朴素方法)
算法原理:
-
质数定义:大于1的自然数,除了1和它本身外没有其他约数
-
优化:只需检查2到√n之间的整数
C++实现:
bool isPrime(int n) {if (n <= 1) return false;for (int i = 2; i * i <= n; ++i)if (n % i == 0)return false;return true;
}
时间复杂度分析:
-
单个数:O(√n)
-
前N个数:O(N√N)
2. 埃拉托斯特尼筛法
算法步骤:
-
初始化布尔数组标记所有数为质数
-
从2开始,标记其倍数为合数
-
重复直到√n
C++实现:
void sieveOfEratosthenes(int n) {vector<bool> is_prime(n+1, true);is_prime[0] = is_prime[1] = false;for (int i = 2; i * i <= n; ++i) {if (is_prime[i]) {for (int j = i * i; j <= n; j += i)is_prime[j] = false;}}
}
时间复杂度:
O(n log log n)
3. 欧拉线性筛法
算法优势:
-
每个合数只被标记一次
-
可记录最小质因子
C++实现:
void linearSieve(int n) {vector<int> primes;vector<bool> is_prime(n+1, true);for (int i = 2; i <= n; ++i) {if (is_prime[i]) {primes.push_back(i);}for (int p : primes) {if (i * p > n) break;is_prime[i * p] = false;if (i % p == 0) break;}}
}
时间复杂度:
O(n)
教学流程
步骤 | 内容 | 形式 |
---|---|---|
1 | 朴素枚举法 | 手动判断10以内质数 |
2 | 埃氏筛图解 | 小圆点图示(划掉倍数) |
3 | 编写埃氏筛代码 | 强调 j=i*i 优化 |
4 | 时间复杂度分析 | 提问:哪些数字被重复处理? |
5 | 线性筛原理 | "最小质因子唯一性"示例 |
6 | 效率对比 | 10万级质数生成速度实测 |