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]);
 
 
Search WWH ::




Custom Search