Cryptography Reference
In-Depth Information
≥
+
among them will be found as soon as
r
1. In practice, when
K
is large, fewer
relations will be sufficient to obtain a dependency with high probability.
The preceding discussion gives an outline of the factor base algorithm but there
is still an important question that we have not addressed: how the smoothness bound
B
is to be chosen. If
B
is chosen small then fewer relations will be needed to obtain
a dependency, which is good, but this must be weighed against the fact that a small
B
makes it more difficult to find
B
-smooth numbers (and hence relations); in fact,
if
B
is chosen too small, then we may not find any
B
-smooth numbers. The choice
of
B
ultimately affects the running time of the algorithm in a decisive way and we
will examine it in more detail later on, when discussing the quadratic sieve factoring
algorithm. For now, we just remark that the optimum value of
B
in the quadratic
sieve is, heuristically, close to
L
K
1
/
2
, where, as in Definition 2.12:
(
n
)
e
√
(
ln
n
)(
ln ln
n
)
L
(
n
)
=
(see also the discussion in [102, pp. 146-151] or [60, pp. 228-229]). The optimal
value of
B
in the factor base method is, as we shall see, also related to this quantity
and, for simplicity, we will adopt a suitable constant multiple of
L
1
/
2
in the Maple
(
n
)
implementation that follows.
6.4.6 The Factor Base Method in Maple
We start with a function that computes the factor base. The input is the number
n
to be
factored, which should be composite and a non-square and, in addition, there is an op-
tional input parameter,
c
, for a constant which take
s
1.5
as de
fault value and which,
multiplied by the abovementioned term
L
e
√
(
ln
n
)(
ln ln
n
)
,isusedtosetthevalue
of the smoothness bound
B
. The output is a list with the elements of the factor base.
(
n
)
=
> FactorBase := proc(n, c := 1.5)
local B, bound;
B := ceil(evalf(c*sqrt(exp(sqrt(ln(n)*ln(ln(n)))))));
bound := numtheory:-pi(B);
[-1, 2, op(select(x -> evalb(numtheory:-legendre(n, x) <> -1),
[seq(ithprime(i), i=2..bound)]))]
end proc:
The next function implements trial division over the factor base for integers of the
form
x
2
n
, where
n
is the number to be factored. The first two input parameters
n
and
x
are for these integers and the third input parameter
fb
is for the factor base
given as a one-dimensional Maple
Array
. The output is either a list consisting of
the values
x
,
x
2
−
−
n
and the exponent vector corresponding to
x
2
−
n
, in case the
latter is a
B
-smooth value, or the
NULL
sequence otherwise.
> FBTrialDivision := proc(n::posint, x::integer, fb::Array)
local l, r, e, q, i;
r:=1;
q := xˆ2-n;
l := ArrayNumElems(fb);
e := Vector(l, datatype = integer[1]);