基于频率的大素数高效生成算法

公钥密码体制加解密算法基于两个大素数乘积的难分解性。为了提升大素数生成算法的效率和降低算法的报错率,提出了一种基于概率论的方法,通过优化Eratosthenes筛法构建素数库,从而通过分析素数库中素数尾数的分类频数和表达式下素数频率,再通过对素数检验算法进行分析,最后得到一种高效的大素数生成算法。在算法中,任意初始的整数都具有较高的素数概率,从根本上提升了算法的执行效

第 2卷第 0期 8 521年 1月 01 0

华东交通大学学报J u a of Eat Ch n Ja t n Unv ri or l n s i a ioo g ie st y

、o . 8 No 0 ,1 2 .5 0c . 2 1 t. 0 1

文章编号：0 502 (0 10 -0 20 10 .5 3 2 1 )50 5—5

基于频率的大素数高效生成算法汤鹏志，彪李(华东交通大学基础科学学院，江西南昌 3 0 1 ) 30 3摘要：公钥密码体制加解密算法基于两个大素数乘积的难分解性。为了提升大素数生成算法的效率和降低算法的报错率，

提出了一种基于概率论的方法，￣4 Ea s ee筛法构建素数库，而通过分析素数库中素数尾数的分类频数和表达通过" L rot ns th从式下素数频率，再通过对素数检验算法进行分析，最后得到一种高效的大素数生成算法。在算法中，任意初始的整数都具有

较高的素数概率，从根本上提升了算法的执行效率。关键字：素数； lr a i Mie R bn算法； l-检验；生成；效率中图分类号：P 0 T31文献标志码： A

{曩}

17年 R nRv s A i hm r和L n d ma提出公钥密码体制 ( S )解密算法， 9 7 o i t d S a i e、 h eA l n e R A)N￣其安全性在于在计算机上生成两个足够长度的大素数，其乘积具难分解性口。目前，素数确定性算法主要分为递归试除法，r otee筛法， l r Ea s ns t h Mi检验和多项式时间内判定的素数 ( l e )算法。文献[] 3分析表明，r otee Ea s ns t h

筛法是一种较好的素数确定性算法。根据文献[]任意素数(和3均可表示为6+ k N ) 4,除2 ) k 1(∈的理论，可提升筛法效率。生成大素数的方法是随机产生一个大整数，然后进行素性检测。文献[]出一种 5提用概率方法来研究素数的分布，是提升大整数素性的有效途径。常用的素数检验算法主要为 F r at e r m算

法、o vy S a e检测法、em n Sl a— ts n o rs L h a检测法、 lr Mie检验、 Ur ai检测法和 A S l Mi - b eR n K算法。通过分析当今的大素数生成方法与原理提升大整数的素性和选择优良的素数检验算法，川，从而提出一种改进的大素数的高效生成算法。

l构建素数库对素数的分布频率研究，需建立在素数库的基础之上。在素数的研究领域中，确定性素数算法存在很

多，如试除法，r otee筛选法， lr Ea s ns t h Mie检验， K算法等。在素数算法中，r otee筛法应用非常广 l A S Ea s ns t h泛。传统 Ea s ee筛法需要对每个数依次比较， r ot ns t h算法的效率较为低下，通过对 Ea s ee筛法进行优 rt t ns oh化，出素数库构建算法。得

定理 1除 2 3和之外，素数均可表示成 6+ ∈的形式。 k 1 k N) f

定理2如果 k为素数，尼，J N l则× f∈必为合数。 推论1在Ea see筛法中 rohns tt对寻求到的第一个素数k,在区间(, 1 1k没有被划掉的数均为素数。

定义一个bo型素数判定数组 pn 1。根据定理 1当f2 3= k 1 f6+∈ ol[+1,=或或i6+或= k 5k N ) f

时，[=u; p】te否则p】fs。找第一[ te( ir[=ae寻 i l个p] r i i u:= 5收稿日期：0 10 .7 2 1-82

)数ii倍数 J[n] 的素，的 (∈0/均为，i )

合。外数赋时去偶，内循 J定奇。当数 ∈,】,数另，组值已除数将层环限为数故素为 (2 ) 时基金项目：国家自然科学基金项目(16 0 4;西省教育厅青年科学基金项目( J0 2 )江西省教育厅科研项目 10 1 1)江 GJ11 9;( J0 0 GJ 1 7 8

作者简介：汤鹏志(9 4 )男， 16 -,教授，硕士，主要研究方向为信息系统及其安全。