Cryptography Reference
In-Depth Information
> sieve := proc(svprimes::(Array(datatype = integer[4])),
svplogs::(Array(datatype = integer[2])), nsvprimes::integer[4],
M::integer[4], sievearray::(Array(datatype = integer[2])),
polroots::(Array(datatype = integer[4])))
local p, logp, i, j, r1, r2;
for i to nsvprimes do
p := svprimes[i];
logp := svplogs[i];
r1 := polroots[i, 1];
r2 := polroots[i, 2];
j := 1 + ((M+r1) mod p);
while j <= 2*M+1 do
sievearray[j] := sievearray[j]-logp;
j:=j+p
end do;
j := 1 + ((M+r2) mod p);
while j <= 2*M+1 do
sievearray[j] := sievearray[j]-logp;
j:=j+p
end do
end do
end proc:
The function
FindRelations
is similar to the previous
Relations
with
minor variations to adapt it to the sieve. Its four input parameters correspond to
the outputs of the same name produced by
Initialization
and it builds the
relations after performing trial division by the factor base primes. The function scans
sievearray
(after this array has been sieved) and tries to factor the integers
(
2
t
+
b
)
−
mn
(for
t
∈[−
M
,
M
]
or, in terms of the local variable
j
,for
j
=
t
) in case the value
sievearray[j]
is below a threshold
which is set here to 14 (the threshold should perhaps grow proportionally to ln
B
but, for simplicity, we use a fixed value that works well for integers with less than 50
digits). Because of these low values, these integers have a high probability of being
B
-smooth. The output of the function consists of the relations in the same format as
in
Relations
.
+
M
+
1
∈[
1
,
2
M
+
1
]
> FindRelations := proc(mn, b, M, fb, sievearray)
local f, start, j, x, r;
f:=[];
start := b-M-1;
for j to 2*M+1 do
x := start+j;
if sievearray[j] < 14 then
r := FBTrialDivision(mn, x, fb);
f := [op(f), r]
end if;
end do;
[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:
We have in place all the ingredients we need to implement the basic QS algorithm,
which is given by the next function. The only required input is the integer
n
to be
factored, which should be an odd composite that is not a power. QS is aimed at
difficult numbers whose factors are large, so small factors should have been factored
out previouslywith other methods. There are two optional keyword parameters,
c
and
cutoff
, whose arguments are passed to the function
Initialization
where
they are used as explained above. The default values are 1
.
2for
c
and 7 for
cutoff
,
