一个实现Kruskal算法的程序及其变式应用

针对社会实际中普遍存在的最优树问题,简要说明了用MATLAB6.5软件实现Kruskal算法的方法和程序,并对如何修改程序以适应于改变了的问题进行分析,给出了一个只要输入边权矩阵和顶点个数,就能求出带约束条件的连线问题的程序。

基于FPGA的SM4算法高效实现方案

针对SM4算法的FPGA实现方案存在数据处理速度不够高和逻辑资源占用过高的问题,提出了基于现场可编程门阵列(FPGA)的高性能、低资源消耗的SM4算法实现方案。所提方案采用循环密钥扩展与32级流水线加解密相结合的架构,循环密钥扩展的方式降低了逻辑资源消耗,32级流水线加解密的方式提高了数据吞吐率。同时,所提方案采用代数式S盒并通过合并线性运算以及在不可约多项式的合并矩阵中筛选最优矩阵运算的方式进一步减少S盒变换的运算量,从而达到降低逻辑资源占用与提高工程数据吞吐率的目的。测试结果显示,该方案比现有最佳方案在数据吞吐率上提升了43%,且资源占用率降低了10%。

uBlock算法的低延迟一阶门限实现方法

目前已有文献给出了uBlock分组密码算法的侧信道防护方案,但是这些方案不仅延迟较高,难以适用于低延迟高吞吐场景,而且在毛刺探测模型下缺乏可证明安全性.针对这一问题,本文给出了在毛刺探测模型下具有可证明安全性的uBlock算法的低延迟门限实现方案.此外,我们引入了Changing of the Guards技术来避免防护方案在执行过程中需要额外随机数.对于防护方案的安全性,我们用自动化评估工具SILVER验证了S盒的毛刺探测安全性,并用泄露评估技术TVLA(Test Vector Leakage Assessment)验证了防护方案的整个电路的安全性.最后,我们用Design Compiler工具对防护方案的性能消耗情况进行了评估.评估结果显示,与序列化实现方式的uBlock防护方案相比,我们的防护方案的延迟能够减少约95%.

分组密码算法在x64平台上的软件实现速度测试方法研究

密码算法的软件实现速度是衡量其实现性能的重要指标之一。在密码算法的设计和评估工作中,测试密码算法的软件实现速度是一项必不可少的工作。在国内外已有的工作中,关于如何在x64平台上进行密码算法的软件实现速度测试没有形成统一的测试标准。本文以分组密码算法的速度测试为例,研究如何在x64平台上测试密码算法的软件实现速度。首先,我们通过实验分析在x64平台上对密码算法进行软件实现速度测试的过程中容易出现的问题。第二步,我们对目前已有的四种速度测试方法:Matsui速度测试方法,Fog速度测试方法,SUPERCOP速度测试方法和Gladman速度测试方法进行研究,对四种速度测试方法的异同进行比较,分析四种方法中存在的问题。第三步,我们采用理论分析与实验探究相结合的研究方法,研究如何降低速度测试过程中产生的波动性数据对实验结果的影响。我们对速度测试公式选择、样本量选择等问题进行了细致的研究。最终我们给出在x64平台上测试分组密码算法软件实现速度的最小值和平均值的有效方法。应用该方法得到的测试结果是稳定的(测试得到的速度随机性小,结果既不会偏大也不会偏小)、可靠(测试过程取样充分,测试得到的速度是可信的)、高效的(在保证测试结果可靠和稳定的前提下,取样量较小,测试过程耗时较少)。利用本文给出的速度测试方法,我们对AES算法和SM4算法在x64平台上的软件实现速度进行了实际测试。

新一代卫星导航信号接收处理算法的设计与实现

随着卫星导航技术的快速发展,新一代卫星导航信号呈现出不同于传统信号的独特特性。深入分析新一代卫星导航信号的物理与调制特性,以及其在复杂信号环境中的表现。基于此,提出一系列卫星导航信号接收处理算法的设计与优化策略,包括信号同步与时延估计优化策略,以及适应性算法与机器学习策略的结合。为了满足实时性要求,进一步探讨现场可编程逻辑门阵列(field programmable gate array, FPGA)与图形处理器(graphics processing unit, GPU)、流水线设计与优化策略在算法实现中的应用,并通过实际场景验证这些算法的有效性和实用性。

后量子密码算法的软件实现研究

基于公钥密码算法的各类安全技术已经成为了目前网络空间安全的重要基石,在构建信任体系、保护传输安全、身份鉴别等方面发挥着举足轻重的作用.然而,利用Shor算法,量子计算机可以在多项式时间内破解RSA、ECC等当前主流公钥密码体制所依赖的数学困难问题.随着量子计算技术的发展,这一安全威胁日益迫近,所以学术界和工业界都致力于研制抵御量子计算机攻击的公钥密码体制.NIST后量子密码标准化项目是目前最具代表性的项目之一,它于2017年征集了数量众多、种类多样的后量子密码方案,目前已产生阶段性结果.除了算法安全性分析之外,各后量子密码算法的软件实现性能也是该项目评价其优劣的重要指标之一.本文围绕六类主要的后量子密码算法,以密码算法软件实现的视角,详细分析了每一类的代表方案及其主要计算负载、优化算法以及软件实现特点;并基于x86和ARM平台,全面梳理和总结了各文献中提出的、特定类型算法的加速技术和通用优化方法.

基于流水线的RSA加密算法硬件实现

针对硬件实现高位RSA加密算法成本比较高的问题,在传统的基4蒙哥马利(Montgomery)算法上进行改进。首先引入CSA加法器快速完成大数的加法计算;然后在后处理上做优化,以减少每次蒙哥马利计算的大数个数;最后在计算RSA加密算法时加入了流水线,在并行执行RSA加密的条件下降低硬件资源的使用。在Xilinx XC7K410T系列的FPGA开发板上的实验结果表明,在保证加密速率的前提下,改进的RSA加密算法结构使用的硬件资源是原来并行结构的1/2,而且可以在更高的频率下工作。

卫星图像处理算法研究及其硬件实现

随着航天技术的快速发展,其空间遥感技术带来的数据逐渐扩增,传统存储器的处理办法无法有效匹配无损图像处理的存储需要,卫星的信息容量也导致了传输瓶颈的出现。要实现其卫星图像的有效处理,必须对卫星图像的算法和硬件进行重新构造。

聚焦计算思维:高中“算法与程序实现”的教学研究

计算思维是信息技术学科的核心素养之一。本研究以发展计算思维为目标,通过创设项目情境、创建数字活动、创新测评方式,探讨如何将计算思维渗透到高中信息技术学科“算法与程序实现”的教学中,提高学生运用信息技术解决问题的能力,发展学生的核心素养。

生成式人工智能在高中信息技术教学中的应用——以《算法与程序实现》单元为例

近年来,生成式人工智能引起了研究者和开发者的关注,其对于教育的影响越来越深入。首先探讨生成式人工智能在教育领域应用的可行性;其次选取《算法与程序实现》单元进行整体教学分析;再次研究生成式人工智能在单元教学中的应用;最后总结生成式人工智能应用的原则。

基于计算思维的项目式教学实践——以“设计算法实现用数学公式计算”教学为例

立足计算思维核心素养的培养,对项目式教学进行探索,可以进一步提高高中信息技术学科教学的质量。在高中信息技术学科教学中,教师基于计算思维运用项目式教学方法进行教学实践,可通过实施项目设计、计划制订、实施过程、学生自评、展示交流、综合评价等六个步骤,有效落实学生计算思维核心素养的培养。

几种排序算法在链式存储结构上的递归实现

排序是程序设计中常用的一种操作,递归是一种重要的程序设计方法.探析了几种常用的排序算法在链式存储结构上的递归实现,包括基本思想、C语言函数源代码及详细注释,并与顺序存储结构上的算法实现进行了性能比较,以便于学习者熟练掌握链式存储结构上的递归程序设计,并为排序算法选择合适的存储结构提供借鉴.

Kruskal算法的改进与VB实现

首先简述了Kruskal算法的算法思想及其在通讯网络中的应用,其次对该算法进行分析并改进,最后给出改进算法的VB实现。

基于模型驱动的密码算法可视化开发平台研究

针对密码算法开发平台普适性差、无法跨平台的问题,本文采用模型驱动实现密码算法开发的方法,设计了一种基于模型驱动的密码算法可视化开发平台,提出了一种基于模型驱动的密码算法开发的领域语言—MCL密码元语言;实现了基于模型的代码生成器和代码映射器.实验证明,该开发平台仅需要开发者拖拽图形块的操作就可以实现密码算法模型的建立,然后平台可以根据建立的密码算法模型生成不同编程环境下的代码.平台实现了C和python的代码映射器模块,密码算法模型可快速映射为C、python代码.平台有较好的实用性,开发者的密码算法实现过程简洁、高效,不同编程环境下的代码均可以通过平台自动生成,提高了密码算法实现的跨平台性.

关于Kruskal算法的一种新实现

通过给网络G的每一个顶点赋予一个所在连通分支编号的方法 ,来判定每条边的加入是否构成圈 ,讨论了Kruskal算法中判定圈的新途径 。

uBlock算法的低代价门限实现侧信道防护方法

在传统的基于黑盒模型的密码分析中,攻击者仅可以利用密码算法的输入输出信息进行攻击,现有密码算法在黑盒模型下的安全性已经得到较为充分的论证.但是在灰盒模型下,攻击者的能力得到提高,其不仅可以获取密码算法的输入输出信息,还可以获得密码算法实际执行过程中泄露的功耗、电磁、光等物理信息,这些物理信息和密码算法的中间状态具有相关性,敌手可以利用这种相关性进行秘密信息的恢复,这种攻击被称为侧信道攻击.侧信道攻击自提出以来,由于其相对低的实现代价以及较高的攻击效率对于密码算法的实现安全性造成了严重的威胁.uBlock算法是2019年全国密码算法设计竞赛分组密码一等奖获奖算法,同样受到了侧信道攻击的威胁.目前针对uBlock算法的研究较少,在硬件实现方面主要考虑低延迟高吞吐量的实现,缺乏针对资源受限情况下的低代价优化实现,不利于侧信道防护方案的构造.目前公开的文献中指出其S盒适用于基于门限实现的侧信道防护方案构造,存在3-share的无需新随机数的门限防护方案,但是没有给出具体的实现方案.针对这样的现状,本文首先基于流水线和串行化的思想设计并实现了一种适用于uBlock算法的低代价硬件实现方案;其次在上述低代价实现方案的基础上构造并实现了一种适用于uBlock算法的3-share无需新随机数的门限防护方案;最后针对3-share门限实现面积消耗较大的问题进一步优化实现代价,构造并实现了一种2-share的无需新随机数的门限防护方案.为了验证上述防护方案的实际安全性,本文在FPGA开发板中进行了实际实现,并基于测试向量泄露评估技术进行侧信道评估实验,实验结果验证了3-share和2-share uBlock算法门限防护方案对于侧信道攻击均具有相应的防护能力.为了进一步对比防护方案之间的实现代价,本文从寄存器消耗、随机数消耗以及时延等角度对各个方案进行了对比,然后又通过实验评估了不同方案在FPGA资源、等效门等方面的消耗,总而言之上述代价对比说明2-share无需新随机数的门限实现方案的资源消耗相对于其他防护方案较少,其中在面积消耗上其相对于3-share的无需新随机数的门限实现方案降低了约30%.

Kruskal算法的一种高效实现方法

kruskal算法是一种求连通图的最小生成树的算法,无论是采用"避圈法",还是采用"破圈法",都要用到圈的判断,文章基于此,分析提出一种高效实用的判断树中是否存在圈的方法.

RPU_Kruskal算法及其在Android上的实现

随着计算机应用的不断深入,图论的应用越来越广泛。kruskal算法是在连通无向图中寻找最小代价生成树,具有广泛的应用价值。RPU_Kruskal算法从随机化的快速排序、并查集并采用按秩合并与路径压缩对其改进。Android是Google公司推出的智能移动设备操作系统,处理与存储资源相对有限,将RPU_Kruskal算法实现到Android上去,得到了令人接受的效果。

关于Kruskal算法的一个简便实现

根据数据结构中求一个带权无向连通图的最小生成树算法的特点,文章给出了Kruskal算法的一个简便而完整的C语言实现。特别是对不连通子图的刻画,只引进了一个一维数组就解决了问题。

基于Visual c＋＋的Kruskal算法的贪婪策略实现与分析

贪婪策略可用于求解图的最小生成树，Kruskal算法是实现图的最小生成树的一种常用的算法。介绍了Kruskal算法的实现方法，并对算法的运行效率进行分析。