网站建设毕业设计总结,天元建设集团有限公司联系方式,网站建设建议,白银市城县建设局网站实验一、数论基础#xff08;上#xff09;
一、实验目的
1、通过本次实验#xff0c;熟悉相关的编程环境#xff0c;为后续的实验做好铺垫#xff1b;
2、回顾数论学科中的重要基本算法#xff0c;并加深对其的理解#xff0c;为本学期密码学理论及实验课程打下良好…实验一、数论基础上
一、实验目的
1、通过本次实验熟悉相关的编程环境为后续的实验做好铺垫
2、回顾数论学科中的重要基本算法并加深对其的理解为本学期密码学理论及实验课程打下良好的基础。
二、实验原理
数论主要研究的是整数的运算及性质许多常用的加密算法都用到了数论知识。
三、实验环境
本次实验的实验环境为Dev-C 5.11以及IntelliJ IDEA IDE。
四、实验内容
1、厄拉多塞筛算法Sieve of Eratosthenes
1、算法原理 辅助变量 i 从 2 到 N的平方根 遍历在 [2,N] 区间 当中将所有 i 的倍数删除剩下的数即为 [2,N] 中的全部素数。
2、算法流程 本算法的大致流程如下图所示 3、算法的代码实现C语言
#include stdio.h
#include math.hint flags[10010] { 0 }; // 0代表质数1代表合数
int isprime[10010] { 0 }; // 质数的集合
int i, j;
int num; // [2,N]中质数的个数void getprimes(unsigned long long N);int main()
{unsigned long long N;printf(请输入N: );scanf(%lld, N);getprimes(N);return 0;
}void getprimes(unsigned long long N)
{for(i 2;i sqrt(N) 1;i ){if(flags[i] 0){j i * i; //从i的平方开始标记 while(j N){//将所有i的倍数除i本身之外标记为合数flags[j] 1; j i;}}}printf([2,N]中的全部质数为\n);for(i 2;i N;i ){if(flags[i] 0) //若i为质数{num ; printf(%d , i);}}printf(\n);printf(共 %lld 个, num);
}4、算法测试 测试点1n 2 测试点2n 103: 测试点3n 10000 2、简单欧几里得算法Simple Euclid’s Algorithm 1、算法原理 简单欧几里得算法用于求2个整数a和b的最大公约数该算法原理基于等式gcd(a,b)gcd(b,a mod b)其中 gcd(a, b) 表示a和b的最大公约数mod表示取模运算。
2、算法流程 本算法的大致流程如下图所示
3、算法的代码实现C语言
#include stdio.h
#include math.hint getgcd(int a, int b);//求a和b的最大公因数int main(){int a, b;printf(请输入整数a: );scanf(%d, a);printf(请输入整数b: );scanf(%d, b);printf(%d 和 %d 的最大公约数是 %d, a, b, getgcd(a, b));return 0;
}int getgcd(int a, int b){if(b 0){return abs(a);}else{return getgcd(b, a % b);}
}4、算法测试 测试点1a 7, b 5 测试点2a 31, b -13 测试点3a 24, b 36; 5大整数测试
测试算法在极大整数位数远超出C语言中 unsigned long long 所能表示的范围上的表现。使用 Java 语言中的大整数类 BigInteger实现。算法的完整代码如下
import java.math.BigInteger;public class euclid {public static BigInteger euclidfunc(BigInteger a, BigInteger b){BigInteger zero;BigInteger tmp;zero new BigInteger(0);while((b.compareTo(zero))! 0) {tmp a.mod(b);a b;b tmp;}if((b.compareTo(zero)) 0) {return a;}return zero;}public static void main(String[] args) {BigInteger a, b;a new BigInteger(); // 以字符串的形式填入测试点a的数值b new BigInteger(); // 以字符串的形式填入测试点a的数值System.out.println(a 和 b 的最大公约数是);System.out.println(euclidfunc(a, b));}
}测试方面选取2组互质的大整数以及1组最大公约数为2的大偶数作为测试用例以验证算法对于大整数的正确性。 大整数测试点1 a 2461502723515673086658704256944912426065172925575 b 1720876577542770214811199308823476528929542231719
运行结果
大整数测试点2 a 137096164691449488835122291235023051763859318102840889067550902 3843189897270890443917889846802171079840187598665712521108447262149 9595371254346390738382042 b 192350399949876251675909634808997772559337752383120440971227732 5564753027680631763602672767980082537045932161772487151544214743242 0951257037823141069640181
运行结果
大整数测试点3 a 965578072786402991215194630452063779349788872980869942115905155 7171732595578592378315943243630787051274235487747679004689180215305 3719263845602618422474671707896136814707875793300040916757228826108 4994903112959425534780109130436805236126554005262552907029834903821 91419067057726624348815391509161304477322782 b 146116799305702219220540123503890666704710410600856387071776221 5924772567527599977981699318091564264712437997953740725104236453636 8053733781377426865890713096999414678345169283722277214494143490905 0652825715582967684984814095461041109999161468223272534833391335036 612863782740784573110824091866969655931097032
运行结果 至此本次实验结束。
五、参考文献
1、《密码编码学与网络安全——原理与实践第七版》Cryptography and Network Security, Principles and Practice, Seventh Edition【美】威廉 斯托林斯 William Stallings 著王后珍等 译北京电子工业出版社2017年12月。
2、《密码学实验教程》郭华 刘建伟等 主编北京电子工业出版社2021年1月。
