21/1埃及信息学杂志22（2021）101全文一种新的按序Abd Elhakeem Abd Elnabya，A.H.埃尔巴兹ba埃及新达米埃塔，达米埃塔大学理学院数学系b埃及新达米埃塔，达米埃塔大学计算机与信息学院计算机科学系阿提奇莱因福奥文章历史记录：收到2019年2020年3月2日修订2020年5月11日接受2020年6月11日在线提供关键词：素数密码算法A B S T R A C T利用集合论给出了一种新的生成直到某个特定数m2N;mP9;为止的所提出的方法是明确的，面向工程中发现的素数顺序。此外，我们给出了一个有效的可计算的显式公式，它精确地确定素数的个数，直到一个特定的数m2N;mP9：据我们所知，这是文献中给出的第一个精确公式。为了便于比较，给出了一个统一的框架，不仅给出了著名的Eratosthenes和Sundaram筛法的显式公式，而且给出了这两种筛法生成素数个数的精确闭合表达式，直到特定的个数m2N;mP9.此外，计算了三种方法的执行时间，表明我们的方法在生成素数方面具有优越的性能©2020 THE COUNTORS.由Elsevier BV代表开罗大学计算机和人工智能学院出版这是一篇CC BY-NC-ND许可证下的开放获取文章（http：//creative-commons.org/licenses/by-nc-nd/4.0/）上提供。1. 介绍数论在计算机科学和密码学中有许多越来越重要的应用[1]。数论的中心议题之一质数是大于1的自然数，除了1和它本身之外没有正因子，但大于1的自然数不是质数，称为合数。用筛分法产生素数在应用数论中起着重要的作用。有两种众所周知的方法可以通过筛选来排出合数并留下素数，即Eratos thenes和Sundaram[2]的筛选，用于获得直到特定数的所有素数。在这项研究中，我们提出了一个直接的方法，它依赖于集合的概念，以产生所有的素数的顺序。此外，众所周知，素数定理[2]近似地给出了素数的个数，并且指出，如果p<$x<$表示到特定数x为止的素数的个数提出了一个统一的框架，获得明确的公式都筛的埃拉托斯特尼和Sundaram。此外，使用这两种筛方法生成的素数的精确显式的封闭形式的公式得到。本文的重新组织如下：在第2节中，给出了生成素数的方法及其算法。在第三节中，我们提出了一个统一的框架，用我们提出的方法得到Eratosthenes和Sundaram的筛。结论总结见第4。2. 该方法我们使用集合论[3]来生成直到特定数m N;mP9的素数;所提出的方法由以下定理给出：定理：设Pm是直到某一特定数的素数的集合m2N;mP9.如果A¼f2i12i12n：n<$0;1;2;3;则p<$x<$~x=lnxl<$，然而，使用我们提出的方法，我们给出j2k我我我K一个明确的公式，它精确地确定了素数到一个特定的数字m2N;mP9：此外，我们亲-...;m-102i1012012年1月1日第一，第二，第三，k，A 1/4SA1; 和B1/4 f2j 1/1：j1/ 4;2; 3;.;，m-1，g;则A每当最大时，m = 0.02 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2 2 2 2 2 2 222 2 2 2 2 2 2 22 2 2<电子邮件地址：ali_elbaz@yahoo.com（A.H. El-Baz）开罗大学计算机和信息系负责同行审查。P <0.05，2g[PIB-A]，基数. 你好其中j· j表示https://doi.org/10.1016/j.eij.2020.05.0021110-8665/©2020 THE COURORS.由Elsevier BV代表开罗大学计算机和人工智能学院出版。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表埃及信息学杂志杂志主页：www.sciencedirect.comk12k12012年2月23日jkjpk2S22，，m-13：而i6做←←←jk←←←22M2联系我们2012年12月12日2.102A. Elhakeem Abd Elnaby，A.H. El-Baz/Egyptian Informatics Journal 22（2021）101-104校样：首先，必须注意的是，ni决定了生成的集合Ai中的元素，并且i确定从集合Ai生成的集合的数量。由于B<$B-A<$[A和B<$B-A<$\A<$U，则jBjjB-AjjAj） jB-AjjBj-jAj：1：12将公式1.12代入公式1.11，自从马克斯jm-00<哪个.k12012年2月23日k1. 你好 1显示集合Ak<$1中没有生成元素，因为nk<$1不满足集合Ai中所述的ni条件。这给Ak= 1½u。这证明了第一个要求。由于maxn i随i的增加而减小，setAku，则setAk包含至少一个元素，并且仅当maxmin0时满足。因此，m-2k1<$0）k<$日本语简体中文因为k是正整数。这证明了第三个要求，因此证明完成。● 建议方法下面的算法给出了我们提出的生成方法-素数假设Ai和A如上所述，在地板函数中，我们发现最小和最大元素算法：提出的生成素数的方法在A¼中KAi;1/19和。2jpm-1k分别为101和102，因为迷你-1：函数Prime（m）dm是极限，素数生成A1中的最大元素为9，Ak中的最大元素为.2jpm-1k12：此外，22：i←12.2，pm-1，16米;当pm是一个正实数r：4：B㈠ 2i +15：i i+16：结束时那么奇数合数的集合A可以定义如下：A1/4 f96c6m：c是一个奇合数g1：1n假设B如上所述，并使用地板函数的性质，我们发现B中的最小和最大元素是3，7：k18：i 19：当k>0时，10：km-2i124i211：i i+112：结束时2，m-1，分别为1。此外，m-1，m-1;m为奇数1/2-1;m为偶数13：k←i14：i←1假设CB和PB定义如下：C/f96c6m：c是奇数合数g：n 1：2 n和P/f36p6m：p是一个素数g：p 1：3 p则B可以写成如下：B¼C[P;P 1：4]此外，所述的Pm可以定义如下：p是一个素数g：p=1：5从（1.1）和（1.2）可以清楚地看出，A = C，因此，（1.4）变为B¼A[P：01：60]此外，从（1.2）和（1.3）可以清楚地看出，CPu：因此A\P¼u：101：70从（1.6）和（1.7），我们有P¼B-A1：8mm此外，从（1.3）和（1.5）可以清楚地看出，P =0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000将（1.8）代入（1.9），我们得到P<0.05，2g[B-A组：1：10，这证明了第二个要求。由于B-A=2g¼u，则（1.10）给出. 你好jf2gj2Σjk←←← ½]ð þÞ ← ðþÞðþþ Þ15：n←016：whilei6k do17：d m-102i1024i218：whilen6d do19：x n12i12我2 N1第20章：结束21：A x d将生成的元素x保存在向量A22：x第23章：结束24：P = B-AdP是表示B和A的集合差的素数25：结束功能3. 一个统一的框架为了与我们提出的生成素数的技术进行比较，我们提出了一个统一的框架来获得众所周知的筛选方法，即Eratos thenes和Sundaram的筛。3.1. 获得埃拉托塞尼筛的拟议技术为了使用我们提出的生成直到特定数的所有素数的方法来获得Eratosthenes筛m2N;mP9;我们执行以下步骤：步骤1：设BE是小于或等于特定数m的数的集合，即B E<$fj 1：j<$1; 2; 3;.. . ;m-1 g：2我我第四步：设A¼Ajk¼ þ¼EEEJKJKjk¼ þ¼我第四步：设A¼ASA E¼.2 i . . ;，m-1，m-2，m-1，m-2，m-1，m-2;.Σ我基数。2012年1月1日22.我A. Elhakeem Abd Elnaby，A.H. El-Baz/Egyptian Informatics Journal 22（2021）101-104103步骤2：设CE是大于2且小于或等于特定数m的偶数的集合，即CEn2l：l 2; 3;：;jmk o：步骤3：生成集合AE，其中我第一，第二，第三， ; k：2012年1月1日其中. 的英雄美洲其中，b：c是Floor函数，J：J是的英雄美洲如果 我1，我们得到m-2i<$1 <$0，然后停止生成集合2012年1月1日KE E我1/1第五步：设Pm是直到某个特定数的素数集合m2N;mP9，则我是P.M. E.AE[CE]：Fig. 1.执行时间与一个特定的数字m2N;mP9的建议，Eratosthenes和Sundaram的方法。此外，Pm的基数由下式给出：步骤3：生成集合AS，其中. 你好. BE..AE我CE. E .1/4。. - 我是说...[.A S¼fin i2i1：n i¼ 1; 2; 3;.m-102i101 m-102 i 101 m-102 i102 g;第一节第二节. ;k：而且3.2. 获得Sundaram筛的拟议技术2 2i1. 色葡萄¼m-1=2，B：C是的地板功能和J：J是.I.2012年1月1日为了使用我们提出的生成直到特定数的所有素数的方法来获得Sundaram筛，m2N;mP9;我们执行以下步骤：步骤1：设BS是小于或等于m的数的集合。基数。如果 我1，我们得到m-1，2，1，1，0，然后停止生成2012年1月1日设置A S。BS j jSKS1 2 3mi1/4英尺：¼;;... . ;g：1/1步骤2：生成集合CS，其中C S<$njmkq：q<$0; 1; 2;.. . ;m-jmko步骤5：令BS-AS2[CS3]fr：r2Ng第六步：设Pm是直到某个特定数的素数集合m2N;mP9;则表1执行时间与一个特定的数字m 2 N; m P 9的建议，Eratosthenes和Sundaram的方法。M生成集的数量（k）执行时间（秒）该方法埃拉托色尼Sundaram该方法埃拉托色尼Sundaram1000151661660.0395340.0404740.04081010,00050166616660.0457390.0574030.072236100,00015816,66616,6660.1047590.1746200.2141301,000,000500166,666166,6661.0641381.9046192.36141610,000,00015811,666,6661,666,6669.95760217.78065922.48408915,000,00019362,499,9992,499,99916.82556028.16315536.18790720,000,00022363,333,3323,333,33224.03361639.60860050.80938225,000,00025004,166,6664,166,66632.06257651.05823166.64437230,000,00027384,999,9994,999,99944.10803566.27667181.60348335,000,00029585,833,3325,833,33250.22069777.93147697.10765940,000,00031626,666,6666,666,66659.94312192.131258116.12803945,000,00033547,499,9997,499,99970.969666106.166029167.19887550,000,00035358,333,3328,333,33283.296963120.356633270.25010555,000,00037089,166,6669,166,66689.159296132.971661446.40153460,000,00038729,999,9999,999,999108.996244159.264843645.04355265,000,000403110,833,33210,833,332117.289075166.6993351305.10677470,000,000418311,666,66611,666,666127.232278187.5028241536.71974175,000,000433012,499,99912,499,999142.604397201.7722381898.55998580,000,000447213,333,33213,333,332152.231903223.0664062566.10795585,000,000460914,166,66614,166,666160.146174322.2531373232.66248390,000,000474314,999,99914,999,999170.764237410.1983503736.63605595,000,000487315,833,33215,833,332187.835150753.5632634776.194199100,000,000500016,666,66616,666,666192.2691251066.5399156802.735193SS2... ...2104A. Elhakeem Abd Elnaby，A.H. El-Baz/Egyptian Informatics Journal 22（2021）101-104P=0.2g[f2r=1：r2Ng此外，Pm的基数由下式给出：. 你好1/4。BS。 - 我是说... AS[CS。 þ 1是的。 它可以用来产生所有的素数，以便达到一个特定的数字mN;mP9：此外，我们给出了一个明确的公式，它确切地确定了素数的数量，直到一个特定的数字m 2 N; m P 9：此外，为了比较，一个统一的S此外，表1给出了用于生成素数的生成集的数量（k）和三种方法的执行时间与特定数量的比较：显然，所提出的方法使用比其他方法更少数量的生成集和更少的运行时间。结果如图1所示，表明我们的方法在获得素数方面的优越性能。运行实验的PC的系统规格是Intel® coreTM i7-4790 CPU@3.60GHZ，16 GB RAM和16位Win-XP操作系统，基于X64的处理器。4. 结论本文给出了一种显式的素数生成方法。这种技术取决于集合和地板功能-框架提出了获得两个Eratos-thenes和Sundaram筛使用我们提出的方法。计算了三种方法的执行时间，表明所提出的方法在按顺序获得素数方面更有效。竞争利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作。引用[1] 斯丁森博士密码学：理论与实践。第四版。 CRC Press; 2019.[2] Crandall R，Pomerance C.质数：一个计算的视角。第二版。New York：Springer;2005.[3] 坎宁安DW。集合论：第一课。 剑桥大学出版社; 2016.
我的内容管理
展开
