Ruby's NoteBook - C/C++
type: channel
link: https://slugyao.top/index.php/category/C/
items: 刷题笔记——质数
items: AES算法的C语言实现

刷题笔记——质数
type: item
date: 2025-10-31T16:35:17+08:00
description: 简单复习一下有关质数的知识质数的定义在大于1的自然数中，因数只有1和它本身的自然数。由这个定义可以得到，1不是质数，2是最小的质数。判断质数试除法试除法是最快能想到的方法，这里的代码做了一点优化，即从2遍历到sqrt(n)而不是n-1。这是因为：如果n有一个大于sqrt(n)的因子，那么它必定有一个小于sqrt(n)的因子。因此，如果我们在2到sqrt(n)之间没有找到因子，那么大于sqrt(n)的范围内也不会找到因子。在遍历时需要判断i*i<=x，为了防止溢出，这里的写法是i<=x/i#include<iostream> using namespace std; bool is_prime(int x) { if(x<2) return false; else { for(int i=2;i<=x/i;i++)//从2遍历sqrt(x) if(x%i==0) return false; } return true; } int main() { int n,x; cin>>n; int cnt=0; while(n--) { cin>>x; if(is_prime(x)) cnt++; } return cnt; }质数筛质数定理：在1~n之间有n/logn个质数朴素筛法原理：把所有要判断的数列出来，把每一个数的倍数删掉对任意一个数P来说，如果它没有被删掉，则2~P-1都不是它的约数时间复杂度O(nlogn)#include<iostream> #include<algorithm> using namespace std; const int N=1000010; int primes[N],cnt; bool st[N]; void get_primes(int n) { for(int i=2;i<=n;i++) { //如果这个数没有被筛过，说明它是质数 if(!st[i]) { primes[cnt++]=n; } //把每一个数的倍数删掉 for(int j=i+i;j<=n;j+=i) st[j]=true; } } int main() { int n; cin >> n; get_primes(n); cout << cnt << endl; return 0; }埃氏筛法优化：在朴素筛法的基础上，只删除所有质数的倍数//埃氏筛法 #include<iostream> using namespace std; const int N=1000010; int primes[N],cnt; bool st[N]; void get_primes(int n){ for(int i=2;i<=n;i++) { if(!st[i]) { primes[cnt++]=i; for(int j=i*i;j<=n;j+=i) st[j]=true; //可以用质数把所有的合数都筛掉； } } } int main() { int n; cin >> n; get_primes(n); cout << cnt << endl; return 0; }线性筛法原理：从小到大枚举所有质数,筛掉这些质数的倍数对于每一个合数n，只会被它的最小质因子筛掉i % primes[j]==0:primes[j]一定是i的最小质因子，primes[j]也一定是primes[j]*i的最小质因子i % primes[j]≠0:primes[j]一定小于i的所有质因子，primes[j]也一定是primes[j]*i的最小质因子//线性筛法 #include<iostream> using namespace std; const int N=10000010; int primes[N],cnt; bool st[N]; void get_prime(int n) { for(int i=2;i<n;i++) { if(!st[i]) primes[cnt++]=i; for(int j=0;primes[j]<n/i;j++) { st[primes[j]*i]=true; if(i%primes[j]==0)break;//primes[j]一定是i的最小质因子 } } } int main() { int n; cin>>n; get_prime(n); cout<<cnt<<endl; }分解质因数对于一个合数n，把它分解成$p_{1}^{n_{1}}*p_{2}^{n_{2}}$的形式并输出#include<iostream> #include<algorithm> using namespace std; void divide(int n) { for(int i=2;i<=n/i;i++) if(n%i==0) { int …

AES算法的C语言实现
type: item
date: 2025-09-22T20:17:00+08:00
description: 做了一个小的实践，用C语言实现了128比特版本的AES算法。文章里面有很多公式，我实在调不好LaTex公式的渲染了，如果阅读起来不方便请见谅。1.问题背景及相关知识(1)算法提出背景1976年，“公钥密码”的概念被提出。在此类密码中，公钥用于加密，私钥用于解密，加密解密使用两种不同的密钥。随后1978年发布的基于数论方法构造的RSA算法成为之后几十年密码学的研究方向。针对RSA和DES算法的研究和计算机能力的不断提高，公钥密码体制的安全性逐渐受到威胁。数据加密标准DES不能满足官方和商业应用的安全要求，因此美国国家标准技术研究所NIST征集取代DES的新一代加密标准。经过五年的征集筛选，NIST最终将Rijndael算法确立为新的有效标准，以应对各种针对于RSA，DES算法的先进的密码分析技术，即高级加密标准AES。(2)相关数学知识a.有限域有限域又称为伽瓦罗域，是具有有限个元素的域，集合中元素的个数称为域的阶。M阶域存在当且仅当m是某素数的幂，即存在某个整数$n$和素数$p$，使得$$\begin{align*}\text{m = p}^{\text{n}}\end{align*}$$。$p$称为有限域的特征。b.扩展域如果有限域的阶不是素数，则这样的有限域内的加法和乘法运算就不能用模整数加法和整数乘法模$p$表示。$m>1$的域称为扩展域。在扩展域$$\begin{align*}\text{GF}(2^{\text{m}})\end{align*}$$中元素并不是用整数表示的，而是用系数为$GF(2)$中元素的多项式表示。这个多项式最大的度为$m-1$扩展域内的运算假设$$A(x),B(x) \in \text{GF}(2^{\text{m}})$$扩展域内的加法$$ \begin{align*}C(x) = A(x) + B(x) = \sum_{i=0}^{m-1} c_i x^i \quad \quad c_i \equiv (a_i + b_i) \text{mod} 2\end{align*}$$扩展域内的减法$$\begin{align*}C(x) = A(x) - B(x) = \sum_{i=0}^{m-1} c_i x^i \quad c_i \equiv (a_i - b_i) \text{mod} 2 \equiv (a_i + b_i) \text{mod} 2\end{align*}$$扩展域内的乘法扩展域乘法主要在列混合步骤中使用，我们要将扩展域中的两个元素用多项式形式展开，然后使用多项式乘法规则将两个多项式相乘。$$\begin{align*}C(x) = A(x) \cdot B(x) \text{m} o dP(x)\end{align*}$$通常在多项式乘法中C(x)的度会大于m-1，因此需要对其进行化简。扩展域中进行化简的操作为：将这两个多项式相乘的结果除以一个不可约多项式，最后的结果就是最后的余数。AES算法中使用的不可约多项式为:$$\begin{align*}P(x) = x^8 + x^4 + x^3 + x + 1\end{align*}$$2.算法原理AES算法作为一种对称加密算法，加密/解密时通信双方使用单一密钥。而对称密码算法根据对明文消息加密方式的不同可分为两大类，分组密码和流密码。AES算法属于分组密码算法，它的输入分组、输出分组以及加密/解密过程中的中间分组都是128比特。密钥的长度K可以为128，192或256比特，本次实践中实现的是128比特的版本。AES加密算法的数据处理单元是字节，128比特的分组信息被分成16个字节按顺序被复制到一个的矩阵中，这个矩阵称为状态，AES所有变换都是基于状态的变换。AES的所有变换操作，包括字节替换、行变换、列混合和轮密钥添加，均围绕这个状态矩阵展开。这种矩阵化的表示方式不仅便于数学描述，也有利于硬件实现时的并行处理。轮函数是AES加密的核心组件，通过多轮迭代实现数据的混淆（Confusion）与扩散（Diffusion）。在轮函数的每一轮迭代中包含四步变换，分别是：字节替换，行移位，列混合（最后一轮没有列混合）以及轮密钥添加，其作用即使通过简单的非线性变换、混合函数变换，将字节代换运算产生的非线性扩散达到充分混合，在每轮迭代中引入不同的密钥，这样就能以最简单的运算得到最好的加密效果，实现加密的有效性。AES算法流程图如下：(1)字节替换a. S盒的构造首先对于任意输入的字节求逆元，如果x=0x00，则其逆元定义为0x00，否则在$GF(2^8)$上计算x的逆元。在域上$a \otimes b = 1$$\otimes$表示扩展域内的乘法，则称b为a的逆元对x的逆元应用在$GF(2)$上的仿射变换$\begin{align*…