Cryptography Reference
In-Depth Information
N
(i.e.,
n
N,
2
=1
),
q
1
+
q
2
is odd,
gcd
(
q
1
,
2
)=1
and
2)
2
|
N
or
4
not
|
q
2
=
p∈P
p
n
q
2
,p
,
n
q
2
,p
≥
1
,
∀
p
such that
p
=2
and
n
N,p
≥
1
.
The statement
q
2
=
p∈P
p
n
q
2
,p
,
n
q
2
,p
≥
1
can be
expressed in simple words as follows:
each
p
factor of
N
must also be a factor
of
q
2
. It is important to note that this statement still allows
q
2
to have prime
factors that differ from all
p
factors of
N
.
1
,
∀
p
such that
n
N,p
≥
Example 1:
if
N
=36
,thenwehavecase1)ofProposition1because
4
N
. All possible values of
q
1
are simply the set of numbers that are relatively
prime to
N
.Consequently,
q
1
=
|
{
1
,
5
,
7
,
11
,
13
,
17
,
19
,
23
,
25
,
29
,
31
,
35
}
.Since
36 = 2
2
3
2
×
(
p
1
=2
and
p
2
=3
),then2and3mustbeafactorof
q
2
.That
is,
q
2
=
(2
3)
=
3)
,
(2
2
3)
,
(2
3
3
2
)
,
5
×
×
×
3)
,
(2
×
×
(2
×
{
6
,
12
,
24
,
18
,
30
}
.
As mentioned above, the use of the prime number 5 in
5
3)
does not
violate the condition in case 1) of Proposition 1. In total, for
N
=36
there are
12
×
(2
×
×
5=60
possible quadratic PPs (QPP).
The statement
q
2
=
p∈P
p
n
q
2
,p
,
n
q
2
,p
≥
1
of case 2) can also be expressed in simple words as follows:
each
p
6=2
factor
of
N
must also be a factor of
q
2
. It is important to note that this statement
still allows
q
2
to have the prime factor 2 and all prime factors that differ from
all
p
factors of
N
(
q
2
may or may not have 2 as a factor).
1
,
∀
p
such that
p
=2
and
n
N,p
≥
Example 2:
if
N
=90
,thenwehavecase2)ofProposition1because
2
|
N
3
2
and
4
not
5
,all
p
values that differ from 2 are
p
1
=3
and
p
2
=5
. Therefore, the potential values for
q
2
are
(3
|
N
.Since
N
=90=2
×
×
5)
=
5)
,
(3
2
5
2
)
,
2
5)
,
2
2
×
×
5)
,
(3
×
×
(3
×
×
(3
×
{
15
,
45
,
75
,
30
,
60
}
Under the condition
gcd
(
q
1
,N/
2 = 45) = 1
, the potential values for
q
1
are have
120 possible QPPs.
{
1
,
2
,
4
,
7
,
8
,
11
,
13
,
14
,
16
,
17
,
19
,
22
,
23
,
26
,
28
,
29
,
31
,
32
,
34
,
37
,
38
,
41
,
43
,
44
,
46
,
47
,
49
,
52
,
53
,
56
,
58
,
59
,
61
,
62
,
64
,
67
,
68
,
71
,
73
,
74
,
76
,
77
,
79
,
82
,
83
,
86
,
88
,
89
}
Despite the tight conditions imposed by Proposition 1 on
q
1
and
q
2
,the
search space of QPPs is still large, especially for medium to large interleavers.
Thus, it is desirable to reduce the search space further. A solution is to consider
only QPPs that do have a quadratic inverse (for more details on quadratic
inverse for QPP, see [7.39]). This solution for reducing the search space is based
on the interesting finding reported by Rosnes and Takeshita [7.38], namely,
for
32
512
and
N
= 1024
, the class of QPP-based interleavers with
quadratic inverses are strictly superior (in term of minimum distance) to the
class of QPP-based interleavers with no quadratic inverse. Using exhaustive
≤
N
≤
