Cryptography Reference
In-Depth Information
if type(q, negint) then
e[1] := 1;
q:=-q
end if;
for i from 2 to l while r <> 0 do
r := modp(q, fb[i]);
while r=0do
q := iquo(q, fb[i]);
e[i] := 1 + e[i];
r := modp(q, fb[i]);
ifq=1then
return [x, xˆ2-n, e]
end if
end do
end do
end proc:
Next we give the function that finds the relations corresponding to smooth values
factored over the factor base. The required input parameters are
n
, for the integer
being factored, and
fb
for the factor base given as a Maple
Array
. There are also
two optional keyword parameters. The first of them, called
mindeps
, specifies the
minimum number of relations to be found. With the default
mindeps = 5
the
function searches for relations until
K
5 of them are found, where
K
is the size
of the factor base. This guarantees that the basis of the null space of the relations
matrix will contain at least 5 dependencies but, in general, it will contain more and
this number can be lowered when the integer being factored is large. The second
keyword parameter,
verbose
, specifies the way information is to be printed and
has
true
as default value. The output is a list containing three entries. The first is a
vector with the
x
-values, the second a vector with the
x
2
+
n
values (also called the
z
-values in our previous notation) and the third is the relations matrix, an
r
−
K
matrix
whose rows are the exponent vectors corresponding to the
rB
-smooth values found.
×
> Relations := proc(n::posint, fb::Array,
{mindeps::posint:=5, verbose::truefalse:=false})
local s, np, f, j, g, f1, f2, i;
s := isqrt(n);
np := ArrayNumElems(fb);
f:=[];
j:=1;
g := np + mindeps;
while nops(f) < g do
f1 := FBTrialDivision(n, s-j+1, fb);
f2 := FBTrialDivision(n, s+j, fb);
f := [op(f), f1, f2];
j:=j+1
end do;
if verbose then
printf("%d smooth values found out of %d numbers tried:\n", g, 2*j-2)
else
print('Numbers tried to factor: ');
print(2*j-2)
end if
[Vector([seq(f[i][1], i = 1..nops(f))]), Vector([seq(f[i][2], i = 1..nops(f))]),
LinearAlgebra:-Transpose(Matrix([seq(f[i][3], i = 1..nops(f))]))]
end proc:
The next function searches for a basis of the null space of thematrix obtained by re-
ducing the relations matrix modulo 2. The input is the relations matrix and the output
is a list of the dependencies, each of which is given as a one-dimensional array over
F
2
.
