（计算机应用技术专业论文）costas阵列的存在性、计数问题及其在密码学中的应用.pdf

手茼要 任何没有信息扩张的密码体制都可以看作是置换的结果。而起源于雷达信号 设计的c o s t a s 阵列，作为一种特殊的置换矩阵，与置换一一对应，经降维所得c o s t a s 序列是一种特殊的置换。现代密码学中的公钥体制基于特定的数学难题。而c o s t a s 阵列的存在性、计数等问题悬疑至今，成为困难的数学问题。围绕着c o s t a s 阵列的 存在性、计数问题及其在密码学上的应用，本论文取得了以下三方面的研究成果。 1 给出了广义g o l o m b 构造法所缺少的一个必要条件；将随机优化算法应用于 c o s m s 阵列的存在性探测。本文首先对，“义g o l o m b 构造法进行了研究，发现该推 广法缺少一个必要条件，并给出了该条件。代数构造法能构造无穷多阶的c o s t a s 阵列，但部分阶数的阵列不能由其构造，这些阵列的存在性尚不确定。计算机枚 举法可以探、坝, u c o s t a s 阵列的存在性，但计算复杂度呈指数阶。针对高复杂度的弊端， 本文将c o s t a s 阵列的存在性探索视为优化问题，建立了优化模型。在模型的求解上， 文中基于模拟退火算法、遗传算法和广义粒子群算法等三大随机优化算法，分别 提出了s a a c a s 、g a c a s 、g p s o c a s 二种算法，实验结果初步表明：三种算法对 于1 8 阶以下c o s t a s 阵列的探测有效。 2 给出了对称c o s t a s 阵列个数与一般c o s t a s 阵列个数的关系式；改进了现有的 c o s t a s 阵列串行搜索算法并将其并行化。本文研究了对称c o s t a s 阵列的计数问题， 得到了对称c o s t a s 阵列个数和该阶c o s t a s 阵列总个数的关系式。现有的c o s t a s 阵列 枚举算法基于回溯法，通过置换的差分计算决定算法继续搜索或回溯。从计算、 存储必要的差分及检查重复差分的角度，本文改进了现有算法，并以定理的形式 给出了证明。最后将改进后的枚举算法并行化，该算法具有线性加速比和可扩放 性。 3 构造了一种基于c o s t a s 阵列的数字签名方案；将c o s t a s 阵列分别应用于 s h a m i r 背包数字签名、n i e d e r r e i t e r 公钥体制和险。构造c o s t a s 阵列的复杂度属指数 阶，而判定一个置换矩阵是否为c o s t a s 阵列可在多项式时间内完成，因而c o s t a s 阵 列具有构造困难而判定容易的性质。由此，本文基于c o s t a s 阵列构造了一种数字签 名方案。利用c o s t a s 阵列分布的稀疏性，将c o s t a s 阵列用于s h a m i r 背包数字签名和 n i e d e n e i t e r 公钊体制，提高其安伞性。s 盒是询多分组密码算法中的唯一非线性部 件，因此，它的密码强度决定了整个分组密码算法的安全强度。任意行阶的双射s 盒都可以看作是o 到2 ”1 的所有整数的一个置换。本文提出将c o s t a s 阵列作为初始s 盒进行演化以获得密码学性能良好的s 盒，从而为将来设计各种分组密码算法提供 非线性资源。 关键词：c o s t a s 阵列，存在性，计数，模拟退火算法，遗传算法，广义粒子群算法， 数字签名，n i e d e r r e i t e r 公钥体制，s 盒 a b s t r a c t ac r y p t o g r a p h ys y s t e mw i t h o u ti n f o r m a t i o ne x p a n s i o nm a yb ev i e w e da st h e p r o d u c to fp e r m u t a t i o n s c o s t a sa r r a y s ，s p e c i a lp e r m u t a t i o nm a t r i c e s ，d e r i v ef r o mr a d a r s i g n a ld e s i g n t h e r ei so n c - t o - o l l em a p p i n gb e t w e e nc o s t a sa r r a y sa n dp e r m u t a t i o n s a f t e rd i m e n s i o nb e i n gd e s c e n d e d , c o s t a sa r r a y sp r o d u c ec o s t a ss e q u e n c e sw h i c hl u e s p e c i a lp e r m u t a t i o n s i nm o d e r nc r y p t o g r a p h y , ap u b l i c - k e ys y s t e mi sb a s e do nac e r t a i n h a r dm a t h e m a t i c a lp r o b l e m e x i s t e n c ep r o b l e ma n dc o u n t i n gp r o b l e mo fc o s t a sa r r a y s r e m a i nu n s o l v e dy e t , a n db e c o m eh a r dm a t h e m a t i c a lp r o b l e m s c o n c e n t r a t i n go n e x i s l e n e ep r o b l e ma n d c o u n t i n gp r o b l e mo fc o s t a sa r r a y sa n di t se r y p t o g r a p h i e a p p l i c a t i o n , t h r e ea c h i e v e m e n t sh a v eb e e no b t a i n e di nt h i st h e s i s 1 al a c k e dn e c e s s a r yc o n d i t i o no fe x t e n d e dg o l o m bc o n s t r u c t i o nw a sg i v e n ，a n d s t o c h a s t i ca l g o r i t h m sw e i _ ca p p l i e dt oe x i s t e n c ed e t e c t i o no fc o s t a s a r r a y s f i r s t l y , e x t e n d e dg o l o m bc o n s t r u c t i o nw a ss t u d i e d t h ee x t e n s i o nw a sl a c ko fat m e e c s s a r y c o n d i t i o na n dt h ec o n d i t i o nw a sg i v e n a l g e b r a i cm e t h o d sc o u l dc , o n s t r u c t i n f i n i t e l y m a n yo r d e r so f c o s t a sa r r a y s , b u td i dn o tw o r ko np a r to f o r d e r s t h u st h ee x i s t e n c eo f c o s t a sa r r a y sf o rs o m l eo r d e r sw a sn o tk n o w n c o m p u t e re n u m e r a t i o nc o u l dd e t e c tt h e e x i s t e n c eo fc o s t a sa r r a y s ，w h i c ht o o ke x p o n e n t i a lt i m e t oa v o i dh i e , l ac o m p l e x i t y , e x i s t e n c ed e t e c t i o nw a st h o u g h to s 衄o p t i m i z a t i o np r o b l e m a n da l lo p t i m i z a t i o nm o d e l w a sd e v e l o p e d o nm o d e ls o l u t i o n , s a a c a s g a c a sa n dg p s o c a s 、】i 硼p r e s e n t e d r e s p e c t i v e l yb a s e do ns i m u l a t e da n n e a l i n ga l g o r i t h m ，g e n e t i ca l g o r i t h ma n dg e n e r a l p a r t i c l es w a r mo p t i m i z a t i o nw h i c h 饿s t o c h a s t i ca l g o r i t h m s t h ee x p e r i m e n tr e s u l t p r e l i m i n a r i l ys h o w e dt h a tt h r e ea l g o r i t h m sw e r ee f f e c t i v ef o rd e t e c t i o no fc o s t a sa r r a y s w h o s eo r d e r sw e ml o w e rt h a n1 8 2 t h er e l a t i o nb e t w e e l ln u m b e ro fc o s t a sa r r a y sa n dn u m b e ro fs y m m e t r i co n e s w a sd i s c l o s e d ，a n dt h ee x i s t e n t e ds e q u e n t i a ls e a r c ha l g o r i t h mo fc o s t a sa r r a y sw a s i m p r o v e da n dp a r a l l e l i z e d c o u n t i n gp r o b l e mo fs y m m e t r i cc o s t a sa r r a y sw a ss t u d i e d a n dr e l a t i o nf o r m u l aw l l so b t a i n e d t h ef o r m u l ad i s c l o s e dt h er e l a t i o nb e t w e e nn u m b e r o f s y m m e t r i cc o s t a sa r r a y sf o rac ：e r l a i no r d e ra n dn u m b e ro f c o s t a sa r r a y sf o r t h es a m e o r d e r e x i s t e n t e de n u m e r a t i o na l g o r i t h m sw e l eb a s e do nb a c k t r a c k i n g ，a n dd e t e r m i n e d f u l t h e l s e a r c ho rb a c k t r a c k i n gb yc o m p u t i n gd i f f e r e n c eo f t h ep e r m u t a t i o n f o c u s i n go n c o m p u t i n g , s t o r i n gn e c e s s a r yd i f f e r e n c ea n dc h e e k o u t i n gr e p e t i t i o n , t h et h e s i si m p r o v e d t h e a l g o r i t h m a n dp r o v e dc o r r e l a t i v et h e o r e m s t h e i m p r o v e da l g o r i t h m w a s p a r a l l e l i z e d ，a n dt h ep a r a l l e la l g o r i t h mh a dl i n e a rs p e e d u pa n ds c a l a b i l i t y 3 ad i g i t a ls i g n a t u r es c h e m eb a s e do nc o s t a sa r r a y sw a sc o n s t r u c t e d ，a n dc o s t a s a r r a y sw e r ea p p l i e dt o s h a m i rk n a p s a c ks i g n a t u r es c h e m e ，n i e d e r r e i t e rp u b l i c - k e y s y s t e ma n ds - b o x e s c o n s t r u c t i n gc o s t a sa r r a y st o o ke x p o n e n t i a lt i m e ，b u tc h e e k o u t i n g w h e t h e rap e r m u t a t i o nm a t r i xw a sac o s t a sa r r a yo rn o tt o o kp o l y n o m i a lt i m e s o c o s t a sa r r a y sw e r ed i f f i c u l tt oc o n s t r u c tb u te a s yt oc h e c k o u t b a s e do nt h i sp r o p e r t y , a d i g i t a ls i g n a t u r es c h e m ew a sd e s i g n e d b a s e do nl o wd e n s i t y ，c o s t a sa r r a y sw e r e a p p l i e dt os h a m i rk n a p s a c ks i g n a t u r es c h e m ea n dn i e d e r r e i t e rp u b l i c - k e ys y s t e m ，a n d t h e i rs e c u r i t yw a se n h a n c e d s - b o x e sw e r et h eo n l yn o n l i n e a rc o m p o n e n t si nm a n y b l o c kc i p h e r s s o ，t h e i rc r y p t o g r a p h i cp r o p e r t i e sh a dd e t e r m i n e dt h es e c u r i t yo ft h e w h o l ec i p h e ra l g o r i t h m s a nn - o r d e rb o e e t i o ns - b o xc o u l db er e g a r da sa p e r m u t a t i o no f a l li n t e g e r sb e t w e e n0a n d2 已1 t h et h e w sp r e s e n t e dt h a tc o s t a sa r r a y sc o u l db ei n i t i a l s - b o x e sf o re v o l u t i o nt og e ts - b o x e sw i t hb e t t e rc r y p t o g r a p h i cp r o p e r t i e s ，a n dp r o v i d e d a b u n d a n tn o n l i n e a rr e s o u i v sf o r t h ef u r t h e rd e s i g no fs y m m e t r i cc r y p t o g r a p h i c a l g o r i t h m s k e y w o r d sc o s t a sa r r a y s ；e x i s t e n c ep r o b l e m ；c o u n t n gp r o b l e m ；s i m u l a t e da n n e a l i n g a l g o r i t h m ；g e n e t i ca l g o r i t h m ；g e n e r a lp a r t i c l es w a m io p t i m i z a t i o n ；d i g i t a ls i g n a t u r e s c h e m e ；n i e d e 邛e i t e rp u b l i c k e ys y s t e m ；s - b o x e s 刘涛c o s t a s 阵列的存在性、计数问题及其在密码学中的应用 第1 章引言 1 1 背景知识 雷达和声纳信号常用于测试目标的距离以及目标靠近或背离观察者的速度。 而距离既与信号时延成正比，又与信号的频率移位成正比。在跳频雷达和声纳系 统中，从可能的频率集合优，正，厶 中选出若干个频率组成信号，然后分别以时 间间隔 ，l ，t 2 ，岛 发出这些信号，为方便计一般约定f 栉。那么，此类信号可以 用一个r 置换矩阵4 却f ，) 表示，这里行行对应于n 个频率饼 ，栉列对应于甩个 时间间隔 d ，口广1 当且仅当在时间间隔务发送频率石。当这些发出的信号被目标 反射回来时，观察者只能收到原来信号在时间或频率上的延迟信号，而根据这些 延迟值便可确定出目标的距离和背向速度。为了确定延迟值，观察者必须比较回 收的信号与发出信号的备份。具体比较步骤是，将备份信号的所有延迟重叠到所 收到的反射信号上，再找出最一致的那个延迟信号。而判定爿与其延迟彳的“一 致”程度是由“1 ”被重叠的次数来度量的。用公式表示便是设彳= ( 勘， 一= ( 口户( q m d + ，l _ n 或i s 险_ n l0 5 - c ( r ，s ) s h当( ，s ) ( o ，o ) 实际上，观察者所收到的反射信号常常带有误差，因此在雷达、声纳系统中 将j j ) 称为模糊函数，它表明了实际反射的带噪声信号与理想的无噪声信号延迟 之间的整体“一致”性。可以将信号矩阵彳= ( 簖) 想象成一个带有矿个格子的正方 形胶片，对应于4 矿= o 的矿川个格子是不透明的，而对应于口尹1 的疗个格子是透 明的，取两张相同的这种胶片，然后将一张胶片错位地重叠到另一张胶片上，重 叠部分的透明窗口数目就是c ( ，曲。 在2 ”个聍 阶0 ，l 矩阵中共有栉! 个置换矩阵，但是不同置换矩阵作为信号模 式用于雷达和声纳系统中的效果是不大相同的，就是说相应的时，s ) 函数的性质差 别很大。例如若取4 - - - 是r r 阶单位矩阵，那么“l ，1 ) 嘲1 。于是当行较大并且 在噪声环境中时，若取厶为信号模式，那么几乎肯定会产生假目标，此假目标是 2 扬州大学硕士学位论文 真目标在时间和频率上的等值延迟。 由于任意给定置换矩阵彳中的两个位置之后，总可以找到某个延迟4 使得彳 与4 在指定位置处重合，所以显然有m i n m a x c ( r ，啦：1 ( ( ，咖o ，o ) ) 。 由此可见能满足m a x j 沪l ( ( ，j 麒0 ，o ) ) 的信号模式4 就是模糊函数最小的 信号，它能最准确地确定出目标的距离和背向速度。由于这种信号是由j p c o s t a s 于1 9 6 6 年最先提出的【n ，所以大家都称这种信号为c o s t a s 阵列。 1 2c o s t a s 阵列的定义 c o s t a s 阵列有如下几个等价的定义 2 - 4 1 。 定义1 1n x n 阶置换矩阵4 嘞，) 称为c o s t a s 阵列，当且仅当对任意不全为0 的整数对( ，曲，以下非循环相关函数满足： 月 时，垆d 自4 ( j + ，u 埘5 l s , j f f i l 这里，l 甄，勤，l r i 勤，h 9 ，( ，咖0 ，o ) 。若_ ，或加不在区间 1 ，一】中，则 口( 什嘎一l 尸o 。 定义1 2 行阶c o s t a s 阵列是满足如下两个条件的聆胛阶矩阵： 1 每行每列仅有一个元素为1 ； 2 任意两条1 元素间连线不同时具有相同的长度和斜率。 定义1 3 满足如下条件时，1 埘的全排列筋，钆，n 缸l 称为c o s t a s 序列：对 于任意j ，f 和k ，0 q 2 ，w e l c h 构造法产生一个厅疗阶c o s t a s 阵列矾( ，f p l ) 和一 个一撑阶c o s t a s 阵列( 撑_ p - 2 ) 。对于某些素数，可产生一个n x n 阶c o s t a s 阵列 w 3 ( n = p - 3 ) 。 w e l c h 构造法可利用g 民力上的对数表实现。设提g f ( p ) 的生成元。 既：( ，| = 甲- 1 ) 对于1 s f = 窜弘l ，0 9 9 - 2 ，( 力处元素为1 当且仅当j = 。 ：( n = p - 2 ) 删去矾的顶行和最左列便可得之。 ：( r m p - 3 ) 当a = 2 时，删去的最上两行和最左两列便可得之。 w o ：( 萨p ) 在矾上增加一角，有可能得到一个新的c o s t a s 阵列。 2 1 _ , e m p e l 构造法 对于任意素数p 的任意七次方，嘞，存在有限域g f ( q ) 。在g f ( q ) 上应用l e m p e l 构造法，可生成上2 、上。型及变形死型c o s t a s 阵列。设提g f ( q ) 的生成元。 厶： 习- 2 ) 对于1 5 f = 匀- 2 ，l g 匀- 2 ，( f 力处元素为1 当且仅当以d _ 1 。 厶：( n - m 一3 ) 当q 2 ，2 是生成元时，删去如的顶行和最左列便可得之。 t 4 ：( n = q - 4 ) 当+ = l 时，删去三2 的最上两行和最左两列便可得之。 3 g o l o m b 构造法 在g f ( q ) 上应用g o l o m b 构造法，可生成g 2 、g 3 、g 4 型及变形g 4 ，g 5 ，乃， 乃型c o s t a s 阵列。设舐局黾g f ( q ) 的生成元。 岛：( ，| = 叼2 )对于l i _ q - 2 ，1 黟匀一2 ，( f ，力处元素为l 当且仅当彬l 。 g 3 ：( 肝g - 3 ) 当甜户= l 时，删去g 2 的顶行和最左列便可得之。 g 4 ：( ，f 呵哪当g = 2 ，耐伊l 时，删去g 的最上两行和最左两列便可得之。 g 4 ：( ，咧4 ) 当纠- 5 1 ，d + r 1 = 1 时，删去g 2 的最上两行和第l 、q - 2 列。 g 5 ：( 研5 ) 删去g 4 的第酽2 行和第2 列。 乃：( ，f 叼- 1 ) 当q # 2 时，有可能在g 2 的四个角上增加一角即令( o ，o ) 或( o ，g 1 ) 或( g - l ，0 ) 或国- l ，q - 1 ) 处元素为l 。 t o ：( 萨动当q - - - i ( r o o d6 ) 时，有可能在g 2 的四个角上增加两角，即令( o ，o ) ， 国- l ，g - 1 ) 或( o ，g 1 ) ，臼一1 ，0 ) 处元素为1 。 对于w e l c h 构造法和g o l o m b 构造法，杨义先等作了推广，称为广义w e l c h 构造法和广义g o l o m b 构造法 s q 0 。 广义w e l c h 构造法；“是素数域g l 凡力中非零元，v 是g 黝中任意元，提 g 代力的生成元，对于l j 鱼o , - 1 ，o f g _ 9 - 2 ，( 力处元素为l 当且仅当u i = a 。 广义o o l o m b 构造法：是g f ( q ) 中非零元，龌g f ( q ) 的生成元，c 和d 是两 4 扬州大学硕士学位论文 个正整数，并且满足条件g o d ( c , q - 1 ) = g c d 似q - l 产l ，j 是任意整数，对于l 甄脚一2 ， ( f 力处元素为1 当且仅当矿i + o 矿喳甜。 1 4c o s t a s 阵列的搜索方法 c o s t a s 阵列除了用代数方法构造外，还可以通过计算机搜索得到。有两类搜索 方法：完全搜索和局部搜索，而局部搜索主要有基于l - g a p 周期性搜索法 4 1 和s p i n 生成法【l l 】。 把两个相同的n x r c o s t a s 阵列垂直叠放在一起，中间留一空行，那么每个 ( m - 1 ) x n 区域内有行个l 元素，如果这些l 元素满足定义1 2 的第二个条件，那么 称该c o s t a s 阵列具有1 - g a p 周期性。 已经证明，由w e l c h 构造法和g o l o m b 构造法构造的c o s t a s 阵列都具有1 - g a p 周期性。 利用1 - g a p 周期性，给似 1 ) x n 区域内的空行增加一个l 元素，可以测试 ( 肿1 ) ( 时1 ) 置换矩阵是否为c o s t a s 阵列，从而实现c o s t a s 阵列的局部搜索。该方 法可以推广，即增加多个1 元素并测试相应的置换矩阵是否为c o s t a s 阵列。 s p i n 生成法：将代数构造方法得到的c o s t a s 阵列行、列循环移动、旋转并测 试是否依然满足c o s t a s 阵列的条件。有如下几个操作( 不限于此) ： s p i n - a d d ：旋转n - i 阶c o s t a s 阵列并增7 $ f l ( 1 ，1 ) 点。 s p i n - d r o p ：每个点旋转至f j ( 1 ，1 ) 位置并被删除。 s p i n - a d d2 ：旋转- 2 阶c o s t a s 阵列并增加( 1 ，1 ) 点和( ， d 点，或( m1 ) 点和( 1 ， d 点。 s p i n - d r o p2 ：每个点旋转到( 1 ，1 ) 位置，此时如果存在( i 、7 砣， r + 2 ) 点，则( i ，1 ) 点和( 胴之，朋- 2 ) 点均被删除。类似地，( m - 2 ，1 ) 和( 1 ，卜2 ) 点可被删除。 1 5c o s t a s 阵列的理论难题 目前，c o s t a s 阵列作为一种最佳离散信号被广泛应用于雷达信号设计等遥控、 遥测系统中【1 2 4 8 】。另外，c o s t a s 阵列在通信1 9 - 2 2 1 和密码学 2 3 - 2 5 1 等上也有一定应用。 但是，关于c o s t a s 阵列，下列基本理论问题尚待研究【2 l ： 1 行月c o s t a s 阵列存在的的充要条件是什么? 2 ( 猜想) 存在一个正整数使得当，创后一定至少存在一个h x hc o s t a s 阵列。 3 ( 猜想) 对一切正整数栉都至少存在一个n x n c o s t a s 阵列。此猜想是上面 2 中猜想的加强形式。 刘涛c o s t a s 阵列的存在性、计数问题及其在密码学中的应用 5 4 ( 猜想) 序列c ( n ) n ! 单调下降，即c ( 肿1 ) ，( 附1 ) ! 雯协蜘! 。或者更强地有： c ( 时1 ) ( 时1 ) ! 2 5 ! 大得以至于 在我们p c 上都不能用6 4 位的整数表示。所以，我们认为。要得到一个代数构造 法不能构造的c o s t a s 阵列是困难的。特别地，3 2 是c o s t a s 阵列存在性不为人知的 最低阶数。然而，利用当今的确定性算法和计算能力，穷尽测试3 2 阶置换矩阵工 作量是极其巨大的。因此，我们将c o s t a s 阵列的存在性探索视为优化问题，尝试 基于随机优化算法来搜索c o s t a s 阵列。 优化模型是： 朋胁m a x c ( r ，曲 8 扬州大学硕士学位论文 这里，i 叫勤，i s l 5 n ，以磅故o ，o ) ，a 是t l x n 置换矩阵。优化结束后，如果产1 ， 则一个n 阶c o s t a s 阵列就被找到了。 优化过程中，置换矩阵用与其相关联的秤个元素的置换铆拂) 来表示。 这里，以= 1 ，1 s 色鲰。 对于该优化模型，下文将基于模拟退火算法、遗传算法和广义粒子群算法等 三大随机优化算法，分别设计算法求解。 2 3 基于模拟退火算法的c o s t a s 阵列随机搜索算法一s a a c a s 2 3 1 模拟退火算法概述 模拟退火算法【3 吣”( s i m u l a t e da n n e a l i n ga l g o r i t h m ，记作s a a ) 是基于蒙特卡 罗迭代的全局随机优化算法。s a a 独立于具体问题，算法的主要输入就是一个合 适的代价函数，该函数值的最小化产生问题的一个解。特别地，搜索过程中，s a a 不仅接受使代价减小的新状态，也有限制地接受使代价增大的新状态。因此，s a a 能跳出局部最优解。s a a 采用一组称为冷却进度表的参数控制算法进程，使算法 在多项式时间里给出一个近似最优解。 s a a 的一般过程：从选定的初始状态开始，在借助于控制参数t 递减时产生的 一系列m a r k o v 链中，利用一个新状态产生函数和接受准则，重复进行包括“产生 新状态一计算目标函数差一判断是否接受新状态一接受或舍弃新状态”这四个任务 的试验，不断对当前状态迭代，从而达到目标函数最优。图2 1 形象地描述了该过 程。 2 3 2s a a c a s 设计 基于s a a ，我们提出了一种新的c o s t a s 阵列搜索算法s a a c a s ，s a a c a s 包 含如下五个元素： l 。状态产生函数。该算法本质上是一个邻域优化方法。一个可接受试验状态 的产生称为一个“移动”。状态产生函数决定了解在解空间的移动模式。这里，一 个置换称为一个状态。改变一个置换几个元素的位置将产生一个新状态。我们的 算法轮流采用如下两个操作。 假设有一个置换而，忍，磊。 2 变换f 3 “。产生两个随机数材和v ( “v ) 。2 - 变换转置甜和v 间的元素。执行 2 一变换产生一个新簧换厕，忍1 ，l ，羁p l ，而，砧l ，霸。 3 变换【3 。产生三个随机数甜，v 和w ( u s v w ) 。3 - 变换将和v 间的元素插 刘涛c o s t a s 阵列的存在性、计数问题及其在密码学中的应用 9 图2 1s m 的一般过程 i 0 扬州大学硕士学位论文 入到w 后。执行3 变换产生一个新置换厕，缸i 撕扣，锄，忍，7 f w + l ，磊。 2 状态接受函数。这是关于哪些引起代价函数值增长的状态被接受的准则。 一般地，人们都选择蒙特卡罗准则。我们也选之。 3 初始温度t o 。t o 用于提高算法功效，选择大值能保证算法不会过早地陷入 局部最优。 4 温度更新函数u p a a t e ( t ) 。这个函数决定了温度的衰减方式，指数函数用得 最多，我们取“i = 蕊( o 口 = 1 ) a n d ( 纪 = 1 ) a n d0 2 y 2t h e n y 2 ：明； e n d ； m e ：- - y 2 ； e n d ； 上面计算过程包含3 重循环，其循环次数依次为2 肿1 、n 和n 。因为不考虑( ， 咿o ，o ) 的情况，外面两重循环需执行( 2 n + 1 ) x n - 1 次，所以计算批的频度为 ( ( 2 n + 1 ) x n 1 ) x n = 2 n 3 + n 2 n 。 3 2 变换伪码如下： p r o c e d u r et w o e x c h a n g e ( u , v ：i n t e g e r ) ； v a t m i d ：i n t e g e r , 蛐 脚眭鼍v - u + 1 ) d i v2 ； f o rf ：= lt om d d o 研计扛l 】n v - i + 1 ； e n d ； 最坏情况下，u = l ，卿，则频度为n 2 。 4 3 - 变换伪码如下： p r o c e d u r et h r e e e x c h a n g e ( u , v ，w ：i n t e g e r ) ； v a t s u c _ v , p s t a r t o e n d ：i n t e g e r ； b e f m 刘涛c o s t a s 阵列的存在性、计数问题及其在密码学中的应用 1 3 f o r h = u t o v d o t e m p i - u + 1 ：= 砸f l ； 肼心1 ：= p m o d ，什l ； f o r f ：硼1 ，t o w d o u i - s u e _ y + u ：= 两f l ； p s t a r t ：2 i - s u c _ v + u ； p e n d ：= p s t a r t + v - u ； f o ri ：= p s t a r tt o p e n dd o 刀f 1 1 ：= 嘲p i - p s t a r t + 1 ； e n d ； 最坏情况下，u = l ，w = n ，则频度为, 。 s a a c a s 外循环最多执行1 + i o g a ( t e m p e t o ) 次，内循环最多执行s t e p 次，所 以算法总的时间复杂度为d ( 矿s t e p 1 0 9 。警。 实验结果： 设定s t e p = - 1 0 0 n ，疗是置换的大小。t e m p e = i x l o 1 0 。t o = 3 0 0 ，“l = o 9 7 岛。 s a a c a s 能找出表2 1 中c o s t a s 阵列。 表2 1s , 从c a s 搜索到的c o s t a s 阵列 c o s t a s 阵列 3i2 i34 2 2 43 l5 l5 6 2 43 54 6 23 l7 58 2 6 l7 43 7 2 4 8 93l65 l o5 2 l9 38 4 6 7 5 1 0 2 6 4 l1 179 83 5 9 67 11 2 4 281 11 0 3 98 4 6 1 27 i ll25 1 3 1 0 3 7 68 2 1 2 l o l1 3 1 4 4 1 139 5 58 1 2 l l4 6 2 1 5 1 3 1 43 l o7 19 栉一3 4 5 6 7 8 9 m n ! b m 蟮 1 4 扬州大学硕士学位论文 2 4 基于遗传算法的c o s t a s 阵列随机搜索算法g a c a s 2 4 1 遗传算法概述 遗传算法1 3 0 , 3 2 ( g e n e t i c a l g o r i t h m ，记作g a ) 思想来源于自然界的进化过程。 g a 是一种高度并行的随机智能优化算法，很适合求解诸如t s p 等大规模复杂问 题。g a 将问题的解编码成称为染色体的数字串。然后，一群染色体在称为遗传算 子的选择、交叉和变异三种操作作用下，一代一代地进化。在若干代进化后，很 多染色体具有较高的适应度，g a 收敛到最优的染色体，该染色体对应问题的最优 解。遗传算法的一般流程如图2 2 所示： 图2 2g 的一般过程 2 4 2g a c a s 设计 基于g a ，我们提出了一种新的c o s t a s 阵列搜索算法g a c a s 。g a c a s 的主 要元素如下： 1 编码方案。每个, x ? , 置换矩阵彳关联一个有厅个元素的置换( m ，巧0 ， 这里，彳尹l ，1 9 勤，户巧。以置换伪，磊) 表示染色体。 2 初始种群。随机生成p o p s 乙阶1 到胛的置换。这些置换( 染色体) 组成 了初始种群。这里，p o p 田冱表示种群规模。 3 适应度函数。设r t l c = m f l xc ( r ，d 。适应度函数产l ，船。也就是说，对于一个 染色体，其小c 越小，则其适应度越高。当户l 时，一个染色体对应一个c o s t a s 阵列。 4 g a 停止准则。设定最大进化代数，用m a x t e 表示。另外，在进化过程 中，当一个染色体的适应度为l ，则g a c a s 立即停止。 刘涛c o s t a s 阵列的存在性、计数问题及其在密码学中的应用 5 选择策略。采用常用的赌轮选择1 3 2 1 。在一个进化代中，每个染色体f 都有 自己的适应度石和相对适应度p ，= 舢。这里，s u m 表示所有染色体的适应度 求和，i _ i d m a x 盯e 则转步骤5 。 步骤3 从老种群p o p ( k ) 选择染色体构成新种群- p o p ( k + 1 ) 。 步骤4k = - k + l 。在种群刚助中施加交叉和变异操作。转向步骤2 。 步骤5g a c a s 停止，输出结果。 g a c a s 有如下运行参数：待搜索c o s t a s 阵列阶数打，种群规模p o p _ s i z e ， 最大进化代数m a x _ i t e ，交叉率髓，变异率砌。 2 4 3g a c a s 分析 1 初始化种群需要随机产生p o ps i z e 个染色体，生成每个染色体运算量为 弗2 i n n ，那么初始化种群的计算复杂性为p o ps l z e x n 2 i n n 。 2 适应度计算工作量在于计算m c ( 即m a xc ( r ，s ) ) ，频度为2 n 3 + ，h 。 3 选择策略可用伪码描述如下： p r o c e d u r es e l e c t ； v a t i j , r a n & i n t e