实验一-密码学数学基础
实验一 密码学数学基础
一、实验目的
- 掌握最大公因数的计算方法，理解其在密码学中的重要性。
- 学习扩展欧几里得算法，能够计算乘法逆元。
- 熟悉模幂运算的方法，了解其在加密和签名算法中的应用。
二、实验原理 - 最大公因数
最大公因数（GCD）是两个整数的最大公因数，是数论中一个基本概念。在密码学中，计算GCD用于判断两个数是否互素，有以下三种常见方法：
- 暴力穷举法
通过列举所有可能的公约数来找到最大公约数。具体操作是依次检查从1到较小数（假设[嵌入对象]则范围为[嵌入对象]）的所有整数是否为x和y的公约数，最终选择最大的公约数。此方法简单直观，但效率较低，适合小整数场景。 - 更相减损法
基于以下性质：两个整数的最大公约数等于较大数减去较小数后的结果与较小数的最大公约数。递归关系如下：
[嵌入对象]
重复相减直至两数相等，此时的值即为最大公约数。该方法虽然比暴力穷举法更高效，但当两数差值较小时，计算量依然较大。 - 辗转相除法
又称欧几里得算法，是效率最高的方法，基于以下定理：
[嵌入对象]
即，两个数的最大公约数等于较小数y和两数取模结果x mod y的最大公约数。通过不断取模运算，最终当余数为零时，非零的数即为最大公约数。
- 扩展的欧几里得算法
扩展欧几里得算法不仅可以求出两个数的GCD，还可以得到其线性组合形式 [嵌入对象]，其中x和y是整数，a和b是输入整数。具体过程如下：
对于[嵌入对象]或[嵌入对象]，显然有[嵌入对象]或[嵌入对象]。在此情况下，x和y的值可以直接给出。
对于[嵌入对象]，算法通过以下步骤来逐步减少问题的规模：
[嵌入对象]。
其中，q是商，r是余数。根据欧几里得定理[嵌入对象]，然后递归地求解[嵌入对象]，并在递归过程中保存每一层的系数x和y，最终构造出线性组合的解。 - 模幂运算
模幂运算即计算[嵌入对象]，是密码学中诸多算法的基础操作。直接计算[嵌入对象]然后对n取模会导致数值过大，计算复杂度高。为了提高效率，通常采用快速幂算法，该算法利用二进制分解的性质将指数幂的计算转化为一系列的平方和乘法，从而大大减少计算量。
直接计算[嵌入对象]的时间复杂度是O(m)，而使用快速幂算法，通过二进制分解后，时间复杂度降低为O(log m)。这显著提高了大指数计算的效率，尤其在密码学中进行大数计算时尤为重要。
三、实验内容 - 求最大公因数
给定两个整数a和b，计算其最大公因数。 - 扩展的欧几里得算法
输入两个整数a和b，利用扩展欧几里得算法计算其GCD，并输出对应的线性组合系数x和y。 - 模幂运算
给定整数a，m，n，使用快速幂算法计算[嵌入对象]。
四、实验报告要求
实验报告正文部分格式及内容如下：
实验目的：给出本次实验所涉及并要求掌握的知识点。
实验内容：给出实验的具体内容。
实验代码：给出实验时所实现的核心代码，展示算法的实现过程。
实验结果：给出实验的实际运行结果，并分析实验结果，验证算法的正确性和效率。
实验总结与心得：总结实验过程，分析实验中出现的问题及解决方法，总结实验的心得体会，并提出实验的改进意见。
test.1
#include<stdio.h>int gcd(int a,int b);int main()
{int n1,n2;scanf("%d %d",&n1,&n2);int ret=gcd(n1,n2);printf("最大公因数为：%d\n",ret);return 0;
}int gcd(int a,int b)
{while(b!=0){int tmp=b;b=a%b;a=tmp;}return a;
}```test.2
#include<stdio.h>
//扩展欧几里得算法
//辗转相除法
//a=b*q+r q:商，r:余数
//ax+by=gcd(a,b) gcd(a,b)=gcd(b,r)=gcd(b,a%b) 递归
//引用或指针
int GCD(int a,int b,int *x,int *y)
{
//特殊情况
if(b==0)
{
*x=1;//初始化
*y=0;
return a;
}
int gcd=GCD(b,a%b,x,y);
*y=y-(a/b) *x;
return gcd;
}
int main()
{
int a,b,x,y;
scanf(“%d %d”,&a,&b);
int ret=GCD(a,b,&x,&y);
printf(“最大公因数：%d\n”,ret);
printf(“一组x,y的解：%d,%d\n”,x,y);
return 0;
}
test.3
#include<stdio.h>
//模幂运算
//a^m mod n=(a^m/2 mod n)^2mod n;//m为偶数
//a^m mod n=(a*a^(m-1)mod n)mod n;//m为奇数
//a m n
int quick_gcd(int a,int n,int m);
int main()
{
int a,n,m;
scanf(“%d %d”,&a,&n,&m);
int r=quick_gcd(a,n,m);
printf("模幂运算结果为：%d\n",r);
return 0;
}
int quick_gcd(int a,int n,int m)
{
int ret=1;
int b=a%n;
while(m>0)
{
//m是偶数
if(m%2==1)
{
ret=(retb)%n;
}
b=(bb)%n;
m=m/2;
}
return ret;
}