Page 216 - 《软件学报》2021年第9期

2840 Journal of Software 软件学报 Vol.32, No.9, September 2021

ˆ
ˆ
例 2:设 ( , , ) = 1 2 3 0.3x x + 1 2 x 3 , g x x x 3 0.5x x x + 1 23 0.2x x ,计算 (, , ) g x x x⋅ ˆ(, , ) .
ˆ( , , ) =
f xx x
f xx x
3
23
1
2
2
2
1
3
1
若不考虑系数为 0 的单项,则 f,g 所有可能的情况如下:
=
×
f = 1 x x + 1 2 x 3 p ( ) f = 1 0.3 1 0.3 g = 1 x xx + 1 2 3 xx p g 1 0.5 0.2 0.1
×
=
( ) =
2 3
f = x x p f 0.3 0 0 g = x x x ( p g ) = 0.5 0.8 0.4
=
×
×
=
( ) =
2 1 2 2 2 1 2 3 2
( ) =
( ) =
=
×
f = 3 x 3 p f 3 0.7 1 0.7 g = 3 x x p g 3 0.5 0.2 = × 0.1
2 3
×
( ) =
=
f = 0 p f 0.7 0 = × 0 g = 0 ( p g ) = 0.5 0.8 0.4
4 4 4 4
将 f i ,g i (i=1,2,3,4)逐个相乘(其中,f 2 ,f 4 概率为 0,此处省略):
fg ⋅ 1 = x x x + 1 2 3 x x ( p fg ⋅ 1 1 ) = 0.3 0.1 0.03× =
2 3
1
fg ⋅ 1 2 = 0 ( p f g ⋅ 1 2 ) = 0.3 0.4 0.12× =
fg ⋅ 1 3 = x x x + x x ( p fg ⋅ 1 3 ) = 0.3 0.1 0.03× =
1 2 3
2 3
fg ⋅ 1 4 = 0 ( p f g ⋅ 1 4 ) = 0.3 0.4 0.12× =
f ⋅ 3 g = 1 x x x + x x ( p f ⋅ 3 g 1 ) = 0.7 0.1 0.07× =
1 2 3
2 3
f ⋅ 3 g = 2 x x x ( p f ⋅ 3 g 2 ) = 0.7 0.4× = 0.28
1 2 3
f ⋅ 3 g = 3 x x ( p f ⋅ 3 g 3 ) = 0.7 0.1 0.07× =
2 3
f ⋅ g = 0 ( p f ⋅ g ) = 0.7 0.4× = 0.28
3 4 3 4
统计以上结果:
( p f g⋅ = x xx + xx ) = ( p f g⋅ ) + ( p f g⋅ ) + ( p f ⋅ g ) = 0.03 0.03 0.07+ + = 0.13
12 3 2 3 1 1 1 3 3 1
( pf g⋅ = x x x ) = ( p f ⋅ 3 g 2 ) = 0.28
12 3
( pf g⋅ = x x ) = ( p f ⋅ g ) = 0.07
23 3 3
( pf g⋅ = 0) = ( p f g⋅ 1 2 ) + ( pf g⋅ 1 4 ) + ( p f ⋅ 3 g 4 ) = 0.12 0.12 0.28 0.52+ + =
ˆ
由此得到 (, , ) g x x x⋅ ˆ(, , ) 的 4 种情形以及相应的概率.
f xx x
2
1
2
3
3
1
n
性质 2(乘法法则). 若考虑系数为 0 的单项,则 n 元布尔函数中的单项总数为 2 .由于每一单项的系数可能
n
2
为 1 可能为 0,故 n 元布尔函数可能出现的全部情形有 2 种,每种情形的概率为其概率布尔多项式中各单项系
数的乘积.算法 1 说明概率布尔多项式具体的乘法运算法则,该算法复杂度最大为 2 2 n+ 1 + 1 次乘法运算.
算法 1. 概率布尔多项式乘法运算法则.
ˆ
f xx
输入: ( , ,..., x ), g x x );
ˆ( , ,..., x
1 2 n 1 2 n
ˆ
输出:乘积结果 (, ,..., x n ).
hx x
1
2
ˆ
ˆ
ˆ , ( , ,..., x = ∑
1: 令 ( , ,..., x = f xx 2 n ) IP N ˆ a x g x x 2 n ) ∑ I P N b x
I
I
I
∈
∈
1
( ) I
1
()
ˆ
n
2
2: 列举 f 所有可能的情况 f i 以及概率 pi = 1,2,...,2 ,p i 为 f i 中各系数之积;
,
i
n
3: 列举 ˆ g 所有可能的情况 g j 以及概率 qj = 1,2,...,2 ,q j 为 g j 中各系数之积;
2
,
j
n
2
4: for i=1 to 2 do
n
2
5: for j=1 to 2 do
6: h = f g⋅ i j
(1) 2−⋅ 2 n + j
i
7: P = p q⋅ i j //P k 为 h k 出现的概率, k = 1,2,...,2 2 n+ 1
(1) 2−⋅ 2 n + j
i
8: end for
9: end for
,
10: return hP k (k = 1,2,...,2 2 n+ 1 )
k
由概率布尔多项式及其运算法则,可以通过如下方式构造概率积分区分器.
性质 3(概率积分区分器构造方法). 针对分组长度为 n 的分组密码算法,令活跃比特数为 s,记密文某一比特
布尔多项式 f 中,首项 x 0 x 1 …x s−1 的系数 a I 为关于 c 0 ,c 1 ,…,c n−s−1 的多项式,其中,I={0,1,…,s−1}.取 p 0 =p 1 =…=p n−s−1 =