Cryptography Reference
In-Depth Information
equivalently, that maximizes the logarithm of this quantity. Thus we want to choose
the value of
m
that maximizes the function:
1
2
ln
f
(
m
,
n
)
=−
(
m
)
+
g
(
p
,
m
,
n
)
·
ln
(
p
).
−
1
=
p
∈
FB
m
Next we give a Maple implementation of the function
g
defined above:
> g := proc(p, m, n)
ifp=2then
if m*n mod 8 = 1 then
2.
elif m*n mod 8 = 5 then
1.
else
.5
end if
else
if m mod p <> 0 then
2./(p-1)
else
1./p
end if
end if
end proc:
The next function selects themultiplier. It takes as input the integer
n
to be factored
and has two optional keyword parameters. The first,
c
, specifies the constant to use
when choosing the factor base (with default
c := 1.5
) and the second,
verbose
,
specifies whether information about the possible multipliers is printed on screen
(with
verbose := false
as default). The output is a list
, where
m
is
the selected multiplier and
fb
is the factor base corresponding to
mn
.Thevalueof
m
is selected as the square-free positive integer
[
m
,
fb
]
23 that maximizes the value of
the function
f
defined above (called '
f-value
' in the messages printed by the
function).
≤
> MultSelect := proc(n, {c := 1.5, verbose::truefalse := false})
local mults, i, mn, fbi, f, h, fb, m;
mults := {1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23};
h:=0;
for i in mults do
mn := i*n;
fbi := FactorBase(mn, c);
f := evalf((-1)*.5*ln(i)+add(g(pr, i, n)*ln(pr), pr = fbi[2 .. -1]));
if verbose then
printf("Multiplier: %2d, f-value: %f\n", i, f)
end if;
ifh<fthen
h:=f;
fb := fbi;
m:=i
end if
end do;
[m, fb]
end proc:
Nowwe have all the ingredients needed to implement the factor base factorization
method. We put all of them together in the next Maple function.
