Cryptography Reference
In-Depth Information
∞
3
2
+
1
2
2
+
1
2
3
+··· =
3
2
+
1
2
i
=
2
.
i
=
2
, there is a factor 2
2
for each two
z
-values (and
no higher power factors) so we obtain an average exponent equal to 1. Finally, if
mn
Next, if
mn
≡
5
(
mod 8
)
then we have that the even
z
-values are not divisible by 4 and
hence we have one factor 2 in one of each two
z
-values, giving an average exponent
of
≡
3
(
mod 4
)
1
2
.
It remains to evaluate the case when
mn
is even, which only happens when
m
itself is even, as we are assuming throughout that
n
is odd. In this case we have
mn
since
m
is square-free and hence the even
z
-values are divisible
by 2 but not by 4. Since half of the
z
-values are even, the expected average exponent
is, again,
≡
2
(
mod 4
)
1
2
in this case.
Summing up the previous discussion we obtain the following function that gives
the expected average exponent for each prime
p
in the factor base (cf. [160]):
if
p
odd and
m
p
⎧
⎨
2
p
−
1
=
1,
1
p
if
p
odd and
p
|
m
,
g
(
p
,
m
,
n
)
=
2if
p
=
2 and
mn
≡
1
(
mod 8
)
,
⎩
1if
p
=
2 and
mn
≡
5
(
mod 8
)
,
1
2
if
p
=
2 and
mn
≡
1
,
5
(
mod 8
)
.
2, etc, be the factor base
corresponding to
mn
, when
m
is one of the possible values of the multiplier. Then
each
z
t
(corresponding to
mn
) factors in the form
Now, let
FB
m
={
p
1
,...,
p
K
}
, where
p
1
=−
1,
p
2
=
K
p
e
tj
j
z
t
=
(
±
1
)
·
·
q
,
j
=
2
where
q
is the product of the prime factors of
z
t
which do not belong to the factor
base. If we denote by
FB
m
(
the factor
j
=
2
p
e
tj
z
t
)
, then the most favorable situation
j
is when
z
t
is
B
-smooth, i.e.,
FB
m
(
1. Thus, when choosing the
multiplier, we try to maximize the ratio between the factor
FB
m
(
z
t
)
=±
z
t
and
q
=
z
t
)
and the average
value of
z
t
itself (maximizing
FB
m
(
is not enough because, when using a multi-
plier, the size of the
z
-values grows relative to the size of the
z
-values corresponding
to
n
and this growth must be taken into account). The average value of
FB
m
(
z
t
)
is
obtained by raising the primes in the factor base to the average exponents given by
the previous formula an
d m
ultiplying these factors. Since a rough approximatio
n to
z
t
is given by
t
2
z
t
)
2
t
√
mn
and, for large integers
n
,
t
is small compared to 2
√
m
n
,
we see that the size of the
z
-values corresponding to
mn
are larger by a factor of
√
m
than those corresponding to
n
and hence instead of maximizing the expected av
er
age
value of
FB
m
(
+
z
t
)/
√
m
or,
z
t
)/
z
t
we may just choose the
m
that maximizes
FB
m
(
