Cryptography Reference
In-Depth Information
where
f
l
are real numbres that depend only on
l
.
We define function
g
on the set
0
,
1
with by:
,
2
n−k
···
−
⎧
⎨
m
=0
n
−
k
−
1
h
ml
2
m
f
l
if
∃
l,
p
=
g
(
p
)=
⎩
0
otherwise
Function
g
is well defined since the columns of
H
are linearly independent and
therefore
a fortiori
two-by-two distinct. The Hadamard transform of
G
is then
a function with real values defined on the interval
0
..
2
n−k
1
by:
−
2
n−k
−
1
1)
<p,w>
G
(
w
)=
g
(
p
)(
−
p
=0
l
=0
n−k−
1
h
ml
2
m
for
l
Now, function
g
is null except for points
p
l
=
∈
[0
,
···
,n
−
1]
.
Thus, we have:
f
l
exp
jπ
=
F
(
w
)
<
n−k−
1
m
=0
n−
1
n−
1
n−k−
1
h
ml
2
m
,w>
G
(
w
)=
f
l
(
−
1)
=
w
m
h
ml
l
=0
l
=0
m
=0
The two terms
F
ρ
(
ν
)
and
F
q
(
ν
)
are therefore expressed as Hadamard transforms
and can be calculated by means of the fast Hadamard transform.
Fast Hadamard transform
Let
R
=[
R
0
,R
1
, ..., R
2
n
−
1
]
be a vector with real components. The vector
obtained from
R
by the Hadamard transform is vector
R
=[
R
0
, R
1
,
, R
2
n
−
1
]
···
such that
2
n
−
1
R
j
=
1)
<i,j>
R
i
(
−
(8.3)
i
=0
The scalar product
<i,j>
is, as above, the bit-by-bit scalar product of the
binary developments of
i
and
j
. We also write in vector form,
R
=
RH
2
n
where
H
2
n
is the Hadamard matrix of order
2
n
whose coecient
(
H
2
n
)
i,j
=(
1)
<i,j>
.
−
Let
A
be a matrix size
a
1
×
a
2
and
B
amatrixsize
b
1
×
b
2
with real coecients.
Then the Kronecker product of
A
by
B
, denoted
A
⊗
B
,isamatrixsize
(
a
1
b
1
)
×
(
a
2
b
2
)
such that
(
A
⊗
B
)
i,j
=
A
q
1
q
2
B
r
1
r
2
where
i
=
b
1
q
1
+
r
1
and
j
=
b
2
q
2
+
r
2
with
0
r
2
<b
2
.
If
N
=2
n
, we show that ([8.11]):
≤
r
1
<b
1
and
0
≤
H
N
=(
H
2
⊗
I
N/
2
)(
I
2
⊗
H
N/
2
)
