布尔函数仿射等价判定算法研究

来源 :电子科技大学 | 被引量 : 0次 | 上传用户:gnayief
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
布尔函数是密码学和电路设计的基础,布尔函数等价判定在加密函数设计和电路优化方面都有重要应用。等价判定问题的目标是对给定的两个布尔函数,判断是否存在由可逆矩阵和布尔向量构成的仿射变换,使得两函数仿射等价。若函数等价,则进一步给出对应的仿射变换。本文在研究了已有的等价判定方法基础上,提出了一种基于矩阵群的仿射等价判定算法。由于布尔函数全体及其仿射变换空间具有随变元个数呈双指数增长的特性,如何针对给定布尔函数构造约束条件,尽量精准地筛选出可能使函数等价成立的仿射变换,是求解该问题的重点。目前现有的两种判定算法的主要思路是,先根据真值表计算函数的Walsh谱和自相关函数谱,再基于布尔函数绝对谱分布的等价不变性建立约束条件,进一步构造仿射变换搜索空间。该方法的不足在于构建搜索空间的计算量较大,并且很难在求解前预估仿射变换的搜索空间大小。本文提出的基于矩阵群的仿射等价判定算法创新性地选取布尔函数的支撑矩阵作为研究对象。该方法首先将仿射等价判定问题转化为矩阵表示,然后对支撑矩阵进行初等变换等操作得到同余标准型。再进一步对矩阵同余标准型进行分析得出,仿射变换搜索空间可以由支撑矩阵行向量、布尔正交矩阵群、布尔辛矩阵群和低阶布尔可逆矩阵群共同构成。最后给出了布尔正交矩阵群和布尔辛矩阵群的生成元,从而完成了仿射变换搜索空间的构建。矩阵群仿射判定算法的优势在于,可以在输入布尔函数对之前预先加载已经生成的矩阵群,从而能够大大降低构建搜索空间的计算量,提高搜索空间的构造速度。并且,通过对矩阵群阶数的分析,该方法首次得到了仿射等价判定的搜索空间大小为o(m·2r2/2+n(n-r))。其中,n表示布尔矩阵的变元个数,m表示支撑矩阵的行数,r表示支撑矩阵与其转置乘积矩阵的秩。为验证新方法的有效性,本文选取了随机生成函数、特殊Walsh谱分布函数以及具有高非线性度的布尔函数作为实验数据,将基于矩阵群的等价判定算法与目前已有的两种算法进行对比实验。分析实验结果可知,该方法对于代数次数较高的布尔函数以及邻域内Walsh谱分布较为集中的布尔函数,等价判定耗时更短。
其他文献
随着社会飞速地发展,人们的娱乐方式逐渐趋于多元化,三维人体重建技术在日常生活中已经获得了广泛的应用。在影视动画、电子游戏、虚拟试衣等领域,三维人体重建技术已经展现出其重要的应用价值。为了使用更加易于操作的方式实现三维人体重建,人们对利用单张二维图像重建三维人体模型的需求愈发强烈。当下比较主流的基于二维图像重建三维人体模型的方式为利用参数化标准三维人体模板。首先从包含目标人体的二维图像中获取目标人体
随着互联网的发展,人脸识别技术开始被广泛的应用。而传统的在PC上的人脸识别虽然精度较高,但存在难以部署,不具有通用性等问题。基于此背景,本文设计一种通用型人脸识别系统,将对于人脸的检测识别等相关计算,以及对人脸用户,人脸图片以及人脸特征等存储,都集中于基于ARM架构的Hi3559AV100芯片上。整个系统便于二次开发,且对大多数场景,视频,图片等都可以实时地进行人脸检测识别。系统设计了六个模块:接
现代医学经常借助于内窥镜对人体进行检查、治疗以及康复监测。但由于内窥镜视野较为狭窄且人体因为呼吸、运动等会导致器官发生形变,外科医生在手术中难以对软组织表面进行全面准确的复原与跟踪,同时对内窥镜图像序列软组织表面特征的跟踪,在手术培训和教学、虚拟现实软组织3D建模等领域也有重要应用。本文对基于深度特征学习的软组织三维运动跟踪方法进行了研究,主要包括帧间三角匹配、深度特征提取与匹配以及帧内跟踪三个部
以人体为中心的研究在计算机视觉领域是重要研究方向,从二维姿态至人体形状生成被广泛应用在相关领域,如人体姿态识别,人机交互,虚拟现实和运动捕捉等等。本文基于SMPL模型,对直接从三维姿态至人体形状、二维姿态至人体形状进行了探究,在此基础上本文对从单张自然图像中生成人体形状进行了探究,以及从多视角轮廓图像中对人体形状生成进行了探究。本文的主要工作内容可以概括如下:(1)本文在第三章对从三维/二维姿态至
随着电子信息技术的高速发展,我国集成电路产业的市场规模不断扩张,对芯片的需求量大幅上涨。光刻机作为集成电路的核心制造装备,其生产过程中的制造精度是保障芯片成品率的关键。光刻机工件台调平系统是光刻机的重要组成部件,其调平精度将直接影响到芯片成品率、光刻成本及效率。目前光刻机调平技术常采用折射-反射的光路结构,涉及的元器件较多,整体结构成本较高,鲁棒性较差。本文以光刻机工件台调平系统为研究对象,以解决
医学影像是一种非常重要的信息载体,其可以很好的帮助临床医师了解患者病情,辅助医师规划治疗方案。医学图像分割技术同样在临床应用中有着至关重要的作用,例如病灶大小测量、器官和病灶定位、病灶形状、放疗规划、辅助手术和解剖结构研究等。目前基于传统图像处理和深度学习的图像分割技术被广泛的应用于医疗图像的自动分割。然而,精确的医疗图像分割仍然存在以下挑战。首先患者的组织和病灶结构呈现高度的多样性和变异性;医疗
我们研究天然胶原中横向交联已有一些时候了,在交联时赖氨酸和羟基赖氨酸的氧化成醛基的ε-氨基与其他肽链的醛基或ε-氨基起反应。在醛鞣时的化学反应进行是相似的,因为鞣性醛在这里同样是与赖氨酸和羟基赖氨酸的ε-氨基起反应,生成了人工交联。我们提出关于我们的工作范围内取得的结果一览,是偏于实际明瞭情况的,但另
期刊
益生菌(Probiotics)是一类能够改善宿主肠内微生物平衡,并对宿主产生健康功效的微生物,然而益生菌在严苛胃肠和湿热环境易丧失活性,大多益生菌在60℃以上高温就会出现大量死亡,因此如何提高益生菌在湿热环境下的存活率是目前益生菌应用领域迫切需要解决的核心问题之一,使用良好的耐热壁材对益生菌进行微胶囊化可以很好地解决这一问题。本文首先通过转谷氨酰胺酶与预热后的乳清分离蛋白共价交联制备微胶囊,通过致
《祝福》以它深邃的思想,感染了一代又一代的中国人;鲁迅对封建文化的鞭挞,在今天仍有其巨大的现实意义.从民族文化反省的角度阅读作品,引导学生理解封建礼教对人性的摧残,反思封建思想对旧中国劳动妇女的毒害,对于生成、发展和提升语文核心素养大有裨益.《祝福》写于1924年2月7日,是《彷徨》的第一篇.相对于近100年后的人尤其中学生来说,理解文意就稍显困难,从“我”的视角出发,循着作者的创作意图,回归文本
近年来高校采取了诸多方案以缓解学生人数与实验仪器数量之间的矛盾。随着信息化教学的不断发展,高校使用计算机开发程序以模拟实验流程,已研发出相关虚拟实验代替传统实验。本文在此背景下设计了基于三维引擎的虚拟实验,不依赖传统测试软件内置函数,独立开发完成了三维实验的各项功能。与传统的二维虚拟仿真实验相比,该实验不仅模拟了实验流程,同时还具有很好的真实感与沉浸感。最后将该实验发布到网络上,使用户能够不受时空