A Study on the Ultra-Wideband Microstrip-to-Waveguide Transition Based on Microstrip Tramped Antenna
-
摘要: 本文提出一种新型的微带转波导转换器,利用锥形天线实现其传输的超宽带和端射特性。将单片微波集成电路(MMIC)兼容的天线插入到矩形波导的E平面中,可以实现TE10主导模式传输。采用这种新的天线耦合方式,可以实现紧凑的结构设计和低成本的制造,而不需要多层衬底或侧壁开槽的波导。研究证明,在机械对准情况下,设计的UWB天线耦合的微带转波导连接器在6GHz?50GHz频带内,回波损耗优于-10dB,VSWR小于1.8。Abstract: A novel microstrip-to-waveguide transition is investigated in this paper, which utilizes a tramped antenna to reach its transmission characters of ultra-wide band and end-fire radiation. This monolithic-microwave integrated-circuit (MMIC)-compatible antenna is inserted in the E-plane of the rectangular waveguide to launch the TE10 dominant mode. With this new excitation scheme, compact design and low cost manufacturing are obtained without the need for multi-layer substrates or waveguide sidewall slits. Under mechanical alignment, a study shows that the designed UWB antenna coupled microstrip-to-waveguide connector has obtained return loss better than -10dB, VSWR less than 1.8 within the band (6GHz ~ 50GHz) .
-
Keywords:
- microstrip-to-waveguide /
- UWB /
- tramped antenna /
- MMIC
-
素数在公钥密码算法中广泛使用,公钥密码算法是基于难解性问题设计的,因此不需要像对称密码算法一样需要安全的信道传输密钥,但是公钥密码算法的计算量和大素数生成的资源开销较大。如:RSA算法[1]需要生成2个相同比特长度的素数p和q, 然后计算公钥(n, e) (n=p·q),以及计算私钥d=e-1 mod φ(n),其中e为随机数并与φ(n)互素。因为素数具有分布不均匀性,导致素数生成算法依赖于增量算法来寻找随机数的邻近素数,所以大素数的生成开销较大。
最原始生成素数的方法是选取一个随机奇数进行素性测试,如果不是素数则重新选取一个随机奇数,直到找到一个素数[2]。1980年,RABIN[3]提出了Miller-Rabin概率素性测试算法,该算法可以概率性检测输入的整数是否为合数。1988年,BEAUCHEMIN等[4]将Miller-Rabin概率素性测试算法用于检验随机整数是否是素数的可靠性问题。1991年,BRANDT等[5]对原始素数生成算法进行改进,提出了增量算法:在素性测试失败后,通过加2的方式寻找邻近的素数,从而提高算法效率。1992年,BRANDT和DAMGARD[6]对文献[5]的增量算法进行了详细的性能分析。2000年,JOYE等[7]改进了文献[5]的增量算法,降低了素性测试的次数,提出了M-J素数生成算法。2006年,JOYE和PALIIER[8]对文献[7]提出的M-J素数生成算法的参数选取进行了优化,提出了M-J特例素数生成算法。2011年,雷文等[9]改进了Miller-Rabin素性测试方法,增加了预测试环节,设计了快速大素数算法;汤鹏志和李彪[10]基于概率论的方法,改进了Era-tosthenes筛法并构建素数库,通过分析素数库中素数尾数的分类频数和表达式下素数频率,使用Miller-Rabin算法对形如∏Pmi×n+1(Pi为小素数)的整数进行校验,设计了快速大素数生成算法。2017年,郑朝霞等[11]在素性测试阶段,通过并行实现小素数擦拭和Miller-Rabin素性测试,从而减少了小素数单独运算消耗时间。2018年,李峰等[2]归纳并总结了原生素数生成算法、现代素数生成算法,并进行了性能比较分析。2019年,刘彦鑫[12]基于中国剩余定理实现素数搜索的算法,研究了素数在多维空间的分布规律,减少在某个区间搜索的整数数量,从而提高了素数搜索的效率。
本文是对改进的增量素数生成算法[2]进行改进,改进的增量素数生成算法中,起始状态是选取一个与小素数乘积互素的奇数,每次素性测试失败后,重新随机选取奇数,并将其与小素数的乘积求和。改进的增量素数生成算法在生成较短长度(512 bit)的素数时有更好的性能,但是在生成1 024 bit以上长度的素数时的性能较弱。为了得到一个可拓展长度的快速素数生成算法,本文基于中国剩余定理与门限的理念,设计了基于中国剩余定理的门限素数生成算法(TCPG)。具体地说,TCPG算法通过中国剩余定理求解小素数数组的同余方程组,从而获得初始状态;然后,在素性测试失败后,采用门限思想生成门限值个随机数,再求解同余方程组,从而提高素数生成的效率。
1. TCPG算法
1.1 改进的增量素数生成算法
增量素数生成算法由BRANDT等[5]提出,后来被抽象成算法1[2]的形式。两者的区别是:(1)算法1的初始化变量p与小素数乘积μ互素,小素数乘积通常为2×3×5×…×…≤p,其中p表示p的比特长度;(2)增量过程从p=p+2变成了p=p+μ。
表 算法1 改进的增量素数生成算法[2]Input:所需素数的比特位数n和小素数乘积μ=∏r(n)i=1pi Output:素数pend while
取与μ互素、长度为n bit的随机奇数p while T(p)==false do p=p+μ 返回p 1.2 中国剩余定理素数生成算法
中国剩余定理又称为“孙子定理”,是求解一次同余方程组的方法。设m1, m2, …, mn是两两互素的正整数,有M=∏ni=1mi,则同余方程组可表示为:
{x≡r1(modm1) ,⋯x≡rn(modmn) 。 此方程有唯一解:
x=n∑i=1riMiM−1i , (1) 其中,Mi=M/mi, Mi-1Mi≡1 mod mi。
中国剩余定理提供了求解同余方程组的方法[12],同时还提供了一种数值映射的方法:选取n个两两互素的正整数m1, m2, …, mn,然后求解同余方程组,得到1个与n个小素数互素的准素数。中国剩余定理素数生成算法(算法2)的核心思想是利用这种数值映射方法寻找素数。
表 算法2 中国剩余定理素数生成算法Input:所需素数比特位数n和小素数乘数μ=∏r(n)i=1pi Output:素数p 预计算: for i=1 to r(n)do θi=(μpi)[(μpi)−1modpi] end 主运算:
p=0while T(p)==false do for i=0 to r(n)do p=p+x×θi end
end
返回p1.3 TCPG算法
中国剩余定理素数生成算法在素性测试失败后,需要更新全部随机数后才求解同余方程,导致消耗过多的时间。为了解决此问题,TCPG算法根据素数比特长度选取合适的小素数数组,然后寻找该数组中最优的门限值k(门限值k代表需要更新随机数的个数);在素性测试失败后仅更新k个随机数,降低随机数的生成个数,从而提高素数生成效率。由于随机数是通过中国剩余定理在小素数数组中计算得到的,因此在素性测试中可以减少小素数擦拭次数,提高素性测试执行效率。为了生成给定区间[qmin, qmax]或其间隔中均匀分布的素数p,由式(1)可知x=∑ni=1riMiM−1i。当ri=1时,x=∑ni=1MiM−1i, 为最小值;当ri=pi时,x=∑ni=1piMiM−1i,为最大值。则x∈[∑ni=1MiM−1i,∑ni=1piMiM−1i]∈[qmin,qmax](如图 1所示),其中r(n)是一个关于n的整数函数,满足2×p2×…×pr(n)+1≥n。
TCPG算法可以先通过预计算同余方程中的MiMi-1来减少每轮的计算量,然后通过更新门限个随机数来重构素数p,具体如算法3所示。
表 算法3 TCPG算法Input:所需素数比特位数n、Π、门限值t Output:素数p 预计算: for i=1 to r(n)do θi=(Πpi)[(Πpi)−1modpi] end 主运算: c=0, p=0 for i=1 to r(n)-t do c=c+x×θi end while T(p)==false do p←c for i=r(n)-t to r(n)do p=p+x×θi end end 返回p 2. 实验结果与性能分析
本节将首先探究TCPG算法的门限值k对素数生成平均时长的影响,然后基于Miller-Rabin概率素性测试算法[3],将TCPG算法与原生素数生成算法、增量素数生成算法[5]、改进的增量算法[2]、M-J特例算法[7]、改进的M-J算法[8]和中国剩余定理素数生成算法[12](简称CRT)进行对比实验。
2.1 门限值对TCPG算法的性能影响
首先,分析不同门限值k对TCPG算法的性能影响。为了寻找小素数数组中的最优门限值k,研究当TCPG算法生成不同长度的素数时,不同门限值对素数生成平均时长的影响。实验环境为Go语言编程,运行在Intel i3-8350K@4.00 GHz处理器上,对每个k进行10 000次实验。
由图 2可知随机数的更新个数和素数生成平均时长没有明显的线性关系,因此,不同小素数的组合都需要通过实验来确定该数组的最优门限值k。本文采用的小素数数组在TCPG算法中生成1个长度为512 bit的素数的最优门限值k为6,所需平均时长为7.80 ms;生成1个长度为1 024 bit的素数的最优门限值k为3,所需平均时长为53.30 ms;生成1个长度为2 048 bit的素数的最优门限值k为18,所需平均时长为505.78 ms。
2.2 素数生成算法性能分析
测试环境为Go语言编程, 运行在Intel i3-8350K@4.00 GHz处理器上;TCPG算法在生成长度分别为512、1 024、2 048 bit的素数的门限值均为2.1节得到的最优门限值。
由平均时长和平均素性判定次数(表 1)可知TCPG算法生成1个长度为512 bit的素数的平均时长略多于改进的增量算法所需时长,但是,在生成长度为1 024 bit和2 048 bit的素数的平均时长最短:TCPG算法生成1个长度为512 bit的素数的平均时长为7.80 ms,比CRT算法降低了18.6%;生成1个长度为1 024 bit的素数的平均时长为53.30 ms, 比CRT素数降低了7%;生成1个长度为2 048 bit的素数的平均时长为505.78 ms, 比CRT算法降低了5%。
表 1 素数生成算法性能分析Table 1. Performance analysis of prime number generation algorithm素数长度 平均时长/ms 原生素数生成算法 增量素数生成算法 改进的增量算法 M-J特例算法 改进的M-J算法 CRT算法 TCPG算法 512 9.64 9.57 7.73 18.70 9.97 9.26 7.80 1 024 76.78 75.97 58.80 996.72 56.00 57.33 53.30 2 048 827.12 830.57 611.81 4 028.00 560.32 532.20 505.78 素数长度 平均素数判定次数 原生素数生成算法 增量素数生成算法 改进的增量算法 M-J特例算法 改进的M-J算法 CRT算法 TCPG算法 512 176 174 32 190 112 49 50 1 024 354 351 66 709 120 59 58 2 048 705 710 134 1 062 240 108 109 另外,实验算法统一进行30次Miller-Rabin概率素性测试,每个算法生成的素数可信度为(1-(1/4)30)*100%≈100%,也就是说,实验在生成十万个大素数的情况下,最多只有0个假素数,因此实验的结果是可信的。
3. 结论
为了提高大素数生成的效率,本文基于中国剩余定理对改进的增量素数生成算法进行了改进,设计了基于中国剩余定理的门限素数生成算法(TCPG)。然后基于Miller-Rabin素性测试算法,将TCPG算法与原生素数生成算法、增量素数生成算法、改进的增量算法、M-J特例算法、改进的M-J算法和中国剩余定理素数生成算法(简称CRT)进行对比实验。实验结果表明TCPG算法生成1个长度为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.30 ms;生成1个长度为2 048 bit的素数用时需505.78 ms,比改进的增量素数生成算法、CRT算法分别减少106.03、54.54 ms。
本文仅给出了TCPG算法的实现和性能分析,实际应用时需考虑侧信道信息的泄露[13]和算法的安全性问题[14];若要用于RSA方案,则还需要保证使用的是强素数[15]。
-
-
期刊类型引用(0)
其他类型引用(6)
计量
- 文章访问数: 1710
- HTML全文浏览量: 214
- PDF下载量: 67
- 被引次数: 6