RSA中大素数生成算法优化及电路实现

为了减少大素数生成时间并加快RSA(Rivest,ShamirAdleman)公钥密码算法的加解密速度,并行化实现了小素数试除和Miller-Rabin素性测试两大关键步骤,使其在进行素性测试的同时能进行小素数试除,从而大幅减少了小素数试除单独运算消耗的时间.为了加速Miller-Rabin素性测试须要反复调用的模乘运算单元,采用一种基于字的高基Montgomery算法及多级流水结构,设计了一种可配置的高速模乘运算电路.经FPGA(现场可编程门阵列)测试,在100 MHz频率下,生成的512bit大素数的平均耗时约为75ms,生成的1 024bit密钥对的平均耗时约为166ms,耗时只有参照结果的54.2%左右.     

RSA公钥密码算法中大素数的生成及素性检测

通过小素数因子的幂乘积构造了一个大数并运用n-1法判定其素性.分析表明:为提高找到素数的速度,应用概率素性测试算法弃除大部分合数,对判定为素数的p进行N=2p 1的变换,再判定N是否为素数以生成安全素数,可构造RSA公钥密码中的两个大素数因子.     

RSA算法中快速生成大素数方法的改进

根据同余理论提出一种快速试除法来更快地判断一个大整数是否能被小素数整除,从而进一步提高RSA算法中所需要的大素数的生成速度．     

梅森素数趣谈

正素数,也被称为质数,是大于1且只能被1和它本身整除的自然数。人们很早就开始研究这类数字,欧几里得在2000多年以前用反证法证明了有无穷多个素数,著名的"哥德巴赫猜想"与素数有密切关系,著名的"黎曼猜想"也与素数有关系……要确定某个数是不是素数,如果数字小一点还好办,数字大了就很不好办。比如,对于2013,我们不能用所有比它小的正整数除它一遍吧?有人猜它是素数,可实际上它并不是,它还能被11和183整除。     

新型大素数快速并行搜索策略

有效地进行素性判定和搜索大素数一直是公钥密码学中研究的热点,但由于大素数的分布具有稀疏的特点,而且大素数搜索和判定的开销巨大,所以大素数的产生速度较慢.因此.本文提出了一种崭新的并行大素数搜索的限界过滤算法.根据素数的分布规律,将大素数的搜索限制在一定范围内的连续奇数中.搜索时,通过一轮预过滤算法,可淘汰大约83.7%的搜索空间内的整数,消除了传统随机递增搜索方法大量的大整数试除运算,从而提高素数生成的速度.实验结果表明:本文提出的算法在平均素性测试次数和搜索时间上均少于传统的随机递增法.而将限界过滤法扩展为并行算法并在双核CPU上计算.其搜索速度又可加倍提高.     

RSA数据加密算法的分析与改进

在RSA加密算法中,大素数寻找算法需要大量的计算,从而降低了RSA的效率。为此,笔者首先使用小素数筛值法、偶数排除法和小素数整除法进行伪素数的初步排除,再使用Miller-Rabin算法对伪素数的素性进行检测,以提高素数的检测效率。测试结果表明:改进算法与经典Miller-Rabin算法相比,其生成大素数的时间减少,且所得到的数不是大素数的概率小于0.1%。从而提高了RSA加密算法的效率,增强了RSA加密算法的适用性。     

梅森素数探究永不休

正2017年12月26日,"互联网梅森素数大搜索"(Great Internet Mersenne Prime Search,GIMPS)项目发布了一个巨大的素数:2~(77232917)-1。这是人类发现的第50个梅森素数,也是目前人类已知的最大素数。千百年来,梅森素数一直吸引着人们前来探究。梅森素数的由来素数也叫质数,是2及以上的整数中,只能被自身和1整除的数。(见《科学世界》2018年第1期"神秘的素     

一种快速生成大素数的方法

基于中国剩余定理对改进的增量素数生成算法进行了改进，设计了基于中国剩余定理的门限素数生成算法(TCPG),以提高大素数生成的效率。具体地说，TCPG算法用中国剩余定理对小素数数组进行随机抽样，然后求解同余方程；在素性测试失败后，不需要对整个小素数数组重新抽样，而是仅抽样门限个随机数，降低了随机数的抽样个数，从而提高素数生成算法效率。最后，对TCPG算法与原生素数生成算法、增量素数生成算法、改进的增量算法、M-J特例算法、改进的M-J算法和中国剩余定理素数生成算法(简称CRT)进行素数生成平均时长的对比分析实验。实验结果表明TCPG算法生成长度为512 bit的素数的平均时长(7.80 ms)略多于改进的增量算法所需时长(7.73 ms),但是，生成长度为1 024 bit和2 048 bit的素数的平均时长最短：TCPG算法在Miller-Rabin素性测试算法下生成1个长度为512 bit的素数的平均时长为7.80 ms,比CRT算法耗时减少1.46 ms;生成1个长度为1 024 bit的素数的平均时长为53.30 ms,比改进的增量素数生成算法、CRT算法耗时分别减少5.50、4...     

一个混合幂型的华林-哥德巴赫问题

在不超过N且又满足一定必要同余条件的正偶数中,除O(N^1/2-8/232^-k c)个例外,均可以表示为一个素数的平方,四个素数的立方与一个素数的k次方的和(k≥4)．     

关于判别素数的充要条件

利用等幂和与判别素数的充要条件及等幂和与Bernoulli数的同余关系,获得了与Bernoulli数有关的判别素数的充要条件,得到了整除Bernoulli数的充要条件,同时还得到了G.Giuga猜想的三个等价命题．     

孪生素数有无穷多个的一个证明

运用一种新的筛法,筛去较小的孪生素数和不满足孪生素数条件的数,运用初等数学的方法,证明其有无穷多个,从而证明了孪生素数有无穷多个.且给出了孪生素数分布的一个规律,即对于一切素数p,在任何两个相邻素数平方的区间[[2i,p2i＋1]上,至少有一组孪生素数.此方法还可以用于其他素数间隔是否为无限个的判断和证明以及分布规律的研究.     

梅森素数研究综述

梅森素数是数论研究中的一项重要内容,也是当今科学探索的热点和难点之一。本文介绍了梅森素数的概念、理论及算法;回顾了梅森素数的研究历史;介绍了由梅森素数引发的课题以及搜索梅森素数的分布计算技术;评述了梅森素数分布研究的成果;同时也对梅森素数研究的前景进行了展望。     

表大奇数为三个取自算术级数的素数之和

解决了三素数定理推广到素取自算术级数的问题。     

关于模方程的同余分解式

给出一个计算次数为n=pq(p，g为素数)的模方程的算法，并以n=6，10，14为例，计算了模方程的同余分解式。     

两种形式的素数与挛生素数猜想

用模型论方法证明几乎一切形式为p2+4(p是素数)的数都是素数,几乎一切形式为2p+1(p是素数)的数也都是素数.并证明关于各种素数的挛生素数猜想.     

一种基于RSA公钥密码体制大素数的生成方法

作者阐述了大素数在RSA公钥密码体制中的作用和意义,在概括当前两种主要的素数产生方法的基础上,说明了两种方法的优缺点,同时介绍了几种生成素数的算法。最后,结合Miller_Rabin测试方法、传统的素数筛选法和确定型多项式算法的各自优点,提出了一种新的生成大素数的方法。     

+10-孪生素数问题及一个猜想

首次提出+10-孪生素数的概念,确定了1000以内+10-孪生素数的对数,并证明了在自然数列中+10-三孪生素数对的唯一性(定理6);最后提出了+10-孪生素数对有无限多的猜想.     

有关梅森素数的预测

梅森素数是一种特殊的素数,探究梅森素数的分布规律历来是数论研究的热点与难点;对梅森素数的分布规律作了简略研究,同时也对梅森素数研究的前景进行了展望。     

梅森素数的分布规律

本文从已知的梅森素数出发,探讨梅森素数在自然数中的分布规律;提出了在2~(2~n)与2~(2~(n 1))之间梅森素数的个数为2~(n 1)-1的猜想,并据此做出了小于2~(2~(n 1))的梅森素数的个数为2~(n 2)-n-2的推论。     

梅森素数的一些注记

 梅森素数历来是数论研究的重要内容,也是当今科学探索的热点和难点之一;而卢卡斯-雷默测试是迄今为止判断梅森数素性最快最有效的工具;周氏猜测是关于梅森素数分布的著名难题。本文首先介绍与梅森素数研究有关的3个重要问题：然后通过对卢卡斯-雷默测试递归数列的研究,揭示了其衍生数列的一个特殊性质,提出相关的猜想;得出卢卡斯-雷默测试的一个关联等式,由该等式与周氏猜测的密切关系,提出相关的猜想;提出了广义卢卡斯-雷默测试的存在性问题,并提出了相关的猜想。结果表明,采用不同的方法对解决梅森素数的有关问题会有所启发和帮助。