【网络安全】【密码学】【北京航空航天大学】实验一、数论基础(上)【C语言和Java实现】

2024-01-10 12:42:52

实验一、数论基础(上)

一、实验目的

1、通过本次实验,熟悉相关的编程环境,为后续的实验做好铺垫;

2、回顾数论学科中的重要基本算法,并加深对其的理解,为本学期密码学理论及实验课程打下良好的基础。

二、实验原理

数论主要研究的是整数的运算及性质,许多常用的加密算法都用到了数论知识。

三、实验环境

本次实验的实验环境为Dev-C ++ 5.11,以及IntelliJ IDEA IDE

四、实验内容

1、厄拉多塞筛算法(Sieve of Eratosthenes)

(1)、算法原理
辅助变量 i2N的平方根 遍历,在 [2,N] 区间 当中将所有 i 的倍数删除,剩下的数即为 [2,N] 中的全部素数。

(2)、算法流程
本算法的大致流程如下图所示:

在这里插入图片描述
(3)、算法的代码实现(C语言)

#include <stdio.h>
#include <math.h>

int 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)、算法测试
测试点1:n = 2

在这里插入图片描述
测试点2:n = 103:

在这里插入图片描述

测试点3:n = 10000

在这里插入图片描述
2、简单欧几里得算法(Simple Euclid’s Algorithm)
(1)、算法原理
简单欧几里得算法用于求2个整数ab最大公约数,该算法原理基于等式gcd(a,b)=gcd(b,a mod b),其中 gcd(a, b) 表示a和b的最大公约数,mod表示取模运算。

(2)、算法流程
本算法的大致流程如下图所示:
在这里插入图片描述

(3)、算法的代码实现(C语言)

#include <stdio.h>
#include <math.h>

int 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)、算法测试
测试点1:a = 7, b = 5
在这里插入图片描述
测试点2:a = 31, b = -13

在这里插入图片描述
测试点3:a = 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月。

文章来源:https://blog.csdn.net/weixin_43031313/article/details/135491541
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。