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

news/2024/2/23 14:39:48/文章来源:https://blog.csdn.net/weixin_43031313/article/details/135491541

实验一、数论基础(上)

一、实验目的

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月。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925866.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

《ARM Linux内核源码剖析》读书笔记——0号进程(init_task)的创建时机

最近在读《ARM Linux内核源码剖析》&#xff0c;一直没有看到0号进程&#xff08;init_task进程)在哪里创建的。直到看到下面这篇文章才发现书中漏掉了set_task_stack_end_magic(&init_task)这行代码。 下面这篇文章提到&#xff1a;start_kernel()上来就会运行 set_task_…

如何用MetaGPT帮你写一个贪吃蛇的小游戏项目

如何用MetaGPT帮你写一个贪吃蛇的小游戏项目 MetaGPT是基于大型语言模型(LLMs)的多智能体写作框架&#xff0c;目前在Github开源&#xff0c;其Start数量也是比较高的&#xff0c;是一款非常不错的开源框架。 下面将带你进入MetaGPT的大门&#xff0c;开启MetaGPT的体验之旅。…

大创项目推荐 深度学习手势识别算法实现 - opencv python

文章目录 1 前言2 项目背景3 任务描述4 环境搭配5 项目实现5.1 准备数据5.2 构建网络5.3 开始训练5.4 模型评估 6 识别效果7 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习手势识别算法实现 - opencv python 该项目较为新颖…

推荐一个页面引导库 driver.js

页面引导功能是 web 开发中常见的一个功能。通过页面引导功能&#xff0c;你可以让用户第一时间熟悉你的页面功能。今天给大家推荐一个页面引导库 driver.js。 简介 driver.js 是一款用原生 js 实现的页面引导库&#xff0c;上手非常简单&#xff0c;体积在 gzip 压缩下仅仅 5…

MongoDB面试系列-01

1. MongoDB 是什么&#xff1f; MongoDB是由C语言编写的&#xff0c;是一个基于分布式文件存储的开源数据库系统。再高负载的情况下&#xff0c;添加更多的节点&#xff0c;可以保证服务器性能。MongoDB旨在给Web应用提供可扩展的高性能数据存储解决方案。 MongoDB将数据存储…

Shopify绑定Facebook收费吗?付款方式是什么?-站斧浏览器

Shopify绑定Facebook收费吗&#xff1f; 答案是&#xff1a;Shopify绑定Facebook并不收取额外费用。Shopify和Facebook之间的绑定是免费的&#xff0c;卖家可以充分利用这一功能来扩展他们的在线业务。通过将商店与Facebook Page相连接&#xff0c;卖家可以将产品目录同步到Fa…

LeetCode 41 缺失的第一个正数

题目描述 缺失的第一个正数 给你一个未排序的整数数组 nums &#xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,0] 输出&#xff1a;3示例 2&#xff…

rabbitmq-java基础详解

一、rabbitmq是什么&#xff1f; 1、MQ定义 MQ&#xff08;Message Queue&#xff09;消息队列 主要解决&#xff1a;异步处理、应用解耦、流量削峰等问题&#xff0c;是分布式系统的重要组件&#xff0c;从而实现高性能&#xff0c;高可用&#xff0c;可伸缩和最终一致性的架…

NLP技术在搜索推荐场景中的应用

NLP技术在搜索推荐中的应用非常广泛&#xff0c;例如在搜索广告的CTR预估模型中&#xff0c;NLP技术可以从语义角度提取一些对CTR预测有效的信息&#xff1b;在搜索场景中&#xff0c;也经常需要使用NLP技术确定展现的物料与搜索query的相关性&#xff0c;过滤掉相关性较差的物…

CASAIM与LG化学越南工厂达成全自动化智能测量技术合作,助力汽车锂电池相关零部件全自动化测量及质量管控

近日&#xff0c;CASAIM与LG化学越南工厂达成全自动化智能测量技术合作&#xff0c;CASAIM将为LG化学越南工厂提供最新一代的CASAIM-IS全自动化测量系统解决方案&#xff0c;助力LG化学越南工厂实现汽车锂电池相关零部件的高精度、高效率测量和检测&#xff0c;进一步提升产品质…

【Vue】后端返回文件流,前端预览文件

let date;request({url: this.$route.query.url,method: get,responseType: blob,}).then(resp > {date respthis.path window.URL.createObjectURL(new Blob([resp], {type: "application/pdf"}))}).catch((e) > {//旧版本浏览器下的blob创建对象window.Blo…

Langchain 与 Elasticsearch:创新数据检索的融合实战

1、简介 在信息爆炸的时代&#xff0c;有效地检索和处理数据变得至关重要。Langchain 和 Elasticsearch 的结合&#xff0c;为我们提供了一个强大的工具&#xff0c;以更智能的方式进行数据检索和分析。 作为一名拥有多年 Elasticsearch 实战经验的技术博主&#xff0c;我将在本…

注意:温度太高电路板表面会氧化导致不上锡

不上锡的情况为什么大多发生在热天&#xff1f; 因为天气太热&#xff0c;室内和室外温差太大&#xff0c;如把PCB板从30多度的室外转移到温度更低的室内就会导致PCB板表面“流汗”现象&#xff0c;PCB板表面有水份就会让其氧化PCB板拆封后&#xff0c;SMT工厂内部环境不好或温…

DC电源模块在新能源领域的应用前景

BOSHIDA DC电源模块在新能源领域的应用前景 DC电源模块在新能源领域有着广阔的应用前景。随着可再生能源技术的发展和普及&#xff0c;如太阳能和风能等的应用逐渐增多&#xff0c;DC电源模块在这些领域的应用越来越重要。 首先&#xff0c;DC电源模块可以用于太阳能发电系统…

记一次 .NET某收银软件 非托管泄露分析

一&#xff1a;背景 1. 讲故事 在我的分析之旅中&#xff0c;遇到过很多程序的故障和杀毒软件扯上了关系&#xff0c;有杀毒软件导致的程序卡死&#xff0c;有杀毒软件导致的程序崩溃&#xff0c;这一篇又出现了一个杀毒软件导致的程序非托管内存泄露&#xff0c;真的是分析多…

mac 上 ssh: connect to host localhost port 22: Connection refused

1。 问题 在搭建hadoop环境的时候 发现ssh localhost 在报错 2. 解决 打开系统设置 -> 共享 -> -> 在左边服务中选择 远程登录 注意红框这些选项慎重选择&#xff01;&#xff01;&#xff01; 修改后&#xff0c;在终端再次 ssh localhost 发现登录成功了 如果…

SpringBoot Redis入门(四)——Redis单机、哨兵、集群模式

单机模式&#xff1a;单台缓存服务器&#xff0c;开发、测试环境下使用&#xff1b;哨兵模式&#xff1a;主-从模式&#xff0c;提高缓存服务器的高可用和安全性。所有缓存的数据在每个节点上都一致。每个节点添加监听器&#xff0c;不断监听节点可用状态&#xff0c;一旦主节点…

Vue3 + Vite + Css3切换主题

1、css3中变量的作用 一个系统或者说一个项目中&#xff0c;往往涉及到很多颜色&#xff0c;但是如果系统看起来样式规整统一的话可能在色值方面偏靠一个色系&#xff0c;字体&#xff0c;颜色&#xff0c;背景颜色&#xff0c;图标颜色等等。 所有可以在css中定义统一的变量&…

智能时代,让AI为你撰写专业应用文

大家好我是在看&#xff0c;记录普通人学习探索AI之路。 何谓应用文&#xff1f;简单来说&#xff0c;应用文是指在日常生活中以及工作中撰写的&#xff0c;旨在传递信息、处理事务的一种文体类型。其范畴广泛&#xff0c;涵盖了诸如请假条、通知书、辞职信、检查报告、欠条、…

6.1810: Operating System Engineering 2023 <Lab7 lock: Parallelism/locking>

一、本节任务 二、要点 2.1 文件系统&#xff08;file system&#xff09; xv6 文件系统软件层次如下&#xff1a; 通过路径树我们可以找到相应的文件&#xff1a; fd&#xff08;文件描述符&#xff09;是进程用来标识其打开的文件的手段&#xff0c;每个进程有自己的文件…