Jacobi和素性测定算法在PC上的实现

我们在ＰＣ机上实现了Ａｄｌｅｍａｎ－Ｐｏｍｅｒａｎｃｅ－Ｒｕｍｅｌｙ的Ｊａｃｏｂｉ和素性测定算法的Ｃｏｈｅｎ－Ｌｅｎｓｔｒａ版本，我们的Ｐａｓｃａｌ程序在４８６微机上对１０４位素数的严格素性证明在５分钟内完成。     

一种新的数字图像置乱方法

常见的基于位置空间的数字图像置乱方法存在不能改变图像统计特性的缺陷,同时置乱过程缺乏随机性,保密性不高。针对以上问题,提出了一种新的数字图像色彩空间置乱方法。该方法基于快速数论变换,置乱速度快,变换矩阵形式不固定,逆变换矩阵求解简单,恢复图像完全无损,且通过选取合适的参数,经过一次迭代就可以达到满意的置乱效果。实验结果表明,置乱后的图像接近白噪声,提高了保密信息的迷惑性,同时还原图像易于实现,有较好的实用性。     

关于Diophantine方程(an-1)(bn-1)=x2的Cohn猜想

设a和b是两个不相等的正整数.针对Cohn猜想,即方程(an-1)(bn-1)=x2没有正整数解(x,n),其中n＞4.利用初等数论方法和指数Diophantine万程的性质,得到了如果a和b具有相反的奇偶性,那么方程没有满足n＞4和2| n的正整数解(x,n).     

数论变换算法(NTT)应用于图像压缩技术

提出了一种全新的图像数据压缩算法,即数论变换(NTT,NumberTheoryTransformation)算法.证明了在以正整数p为模的整数环Z     

素数的可除性判据

本文将素数的非整除性判－Ｅｒａｔｏｓ ｔｈｅｎｅｓ判据转化为整除性判据。该判据比Ｊ．Ｗｉｌｓｏｎ判据有优点。     

FOI2020算法高级在线第6试详解

本文介绍了2020年福建省青少年信息学奥林匹克竞赛算法高级在线培训第六试三道题以及其解法。     

反证法在素数理论中的应用

介绍反证法的原理、基本思想、类型、适用题型及证明步骤,通过实例阐述反证法在素数理论中的应用。     

AKCN-MLWE算法AVX2高效实现

随着量子计算机的快速发展,经典密码系统面临巨大的威胁.Shor算法可以在量子计算机上多项式时间内分解大整数和求解离散对数,而这两类问题分别对应经典公钥密码系统中的RSA和椭圆曲线密码(ECC)所依赖的困难问题,因此可以抵御量子计算攻击的后量子密码近年来受到广泛的研究.格密码是后量子密码中最为高效且拓展性强的一类密码算法,在未来会逐步替代传统公钥密码算法(RSA、ECC等).256位高级向量扩展(AVX2)指令集是英特尔64位处理器中普遍支持的一类单指令多数据(SIMD)指令集,可用于并行计算.但是,由于格密码结构复杂,在支持AVX2指令集的英特尔64位处理器上难以对格密码方案进行高适配的深度优化.AKCN MLWE算法是我国自主设计的基于模格上容错学习(MLWE)问题的格密码密钥封装(KEM)方案,是中国密码学会举办的公钥密码算法竞赛第二轮的获奖算法.本文基于256位高级向量扩展(AVX2)指令集设计了针对AKCN MLWE算法的高效实现方案,包括以下几个关键优化点:针对多项式乘法,本文结合最优的数论变换(NTT)算法,将NTT的最后一层转换为线性多项式并使用Karatsuba算法进行加速计算,大幅提升计算效率的同时减少了预计算表的空间占用;针对取模运算,本文结合了Barrett约减算法和蒙哥马利约减算法的优势,同时采用延迟约减技术降低取模次数;本文针对所有多项式运算均实现了高度并行化,设计了针对多项式压缩与解压缩的并行算法,进一步提升了实现效率.本文设计的AKCN-MLWE算法AVX2高效实现方案在八核Intel Core i99880H处理器上仅需不到0.04 ms即可完成一次完整的KEM(包括密钥生成、密钥封装和密钥解封装),相比于参考实现提升8.84倍,其中密钥生成提升7.07倍,密钥封装提升7.90倍,密钥解封装算法提升11.78倍.本文提出的AKCN MLWE算法AVX2实现方案在相近经典安全强度下性能优于美国国家标准技术研究所(NIST)后量子密码标准化进程第二轮中众多格密码方案(Kyber、NewHope和Saber等).同时,本文设计的部分优化方案可用于提升Kyber、NewHope等格密码方案的性能.