Cryptography Reference
In-Depth Information
> FBFactor := proc(n::And(posint,odd), mult::nonnegint:=0,
{mindeps::posint:=5, c:=1.5})
local mfb, m, x, fb, nfb, r, M, d;
if isprime(n) then
return ''(n)
elif issqr(n) then
return ''(isqrt(n))*''(isqrt(n))
elif n < 1000000 then
return ifactor(n)
end if;
if mult = 0 then
mfb := MultSelect(n, ':-c' = c)
else
mfb := [mult, FactorBase(mult*n, c)]
end if;
m := mfb[1];
ifm>1then
print('Using multiplier: ');
print(m)
end if;
x:=m*n
print('Using smoothness bound: ');
print(ceil(evalf(c*sqrt(exp(sqrt(ln(x)*ln(ln(x))))))));
fb := Array(mfb[2], datatype = integer[4]);
nfb := ArrayNumElems(fb);
print('Size of factor base: ');
print(nfb);
r := Relations(x, fb, ':-mindeps' = mindeps);
M := r[3];
print('Smooth values found: ');
print(nfb + mindeps);
print('Solving a matrix of size: ');
print(LinearAlgebra:-Dimension(M));
d := Dependencies(M);
print('Number of linear dependencies found: ');
print(nops(d));
print('Factors: ');
FindFactors(n, r, d)
end proc:
There is one required input parameter,
n
, for the integer to be factored, and three
optional parameters. The first of them is an optional ordered parameter
mult
which
specifies the multiplier to be used (in order to allow experimentation) and takes, by
default, the optimal value selected by the function
MultSelect
. The remaining
optional parameters are two keyword parameters:
mindeps
specifies the minimum
number of linear dependencies to be searched for (with default value 5) and
c
specifies
the constant to be used for computing the smoothness bound
B
(with default value
1.5). The output is the number itself if
n
is prime (checked with
isprime
) and, in
case
n
is composite, either two nontrivial factors of
n
or a message informing that no
nontrivial factors have been found. In order to exclude cases that are too small for the
smoothness bound to be reliably computed, we use Maple's
ifactor
for numbers
less than 10
6
(of course, the previously defined function
TrialDivisionFactor
could have been used instead).
Example 6.17
Let us go back to the number factored in Example 6.16 and look at
the result of evaluating the possible multipliers:
