Cryptography Reference
In-Depth Information
≥
so that only factor base primes which are
7 and do not divide the multiplier will
be used for sieving. The output is either two nontrivial factors whose product is
n
or
a message informing that no nontrivial factors were found.
> QS := proc(n::posint, {c := 1.2, cutoff := 7})
local st, nfb, svprimes, svplogs, nsvprimes, M, sievearray, polroots,
kn, b, fb, rels, A, deps;
st := Initialization(n, c, cutoff);
print('Using multiplier: ');
print(st[1]);
print('Using smoothness bound: ');
print(st[3]);
fb := st[6];
print('Size of factor base: ');
print(ArrayNumElems(st[6]));
svprimes := st[7];
svplogs := st[8];
nsvprimes := st[9];
M := st[5];
sievearray := st[11];
polroots := st[10];
print('Sieving interval of length: ');
print(2*M+1);
sieve(svprimes, svplogs, nsvprimes, M, sievearray, polroots);
print('Sieving done, searching for smooth values ...');
kn := st[2];
b := st[4];
rels := FindRelations(kn, b, M, fb, sievearray);
A := rels[3];
print('Number of smooth values found: ');
print(LinearAlgebra:-RowDimension(A));
gc();
print('Solving a matrix of size: ');
print(LinearAlgebra:-Dimension(A));
deps := Dependencies(A);
print('Number of linear dependencies found: ');
print(nops(deps));
print('Factors: ');
FindFactors(n, rels, deps)
end proc:
Example 6.20
Let us factor Fermat's number
F
7
with default settings:
> QS(2ˆ128 + 1);
Using multiplier:
5
Using smoothness bound:
28771
Size of factor base:
1592
Sieving interval of length:
57693817
Sieving done, searching for smooth values ...
Number of smooth values found:
1662
Solving a matrix of size:
1662, 1592
Number of linear dependencies found:
144
Factors:
(5704689200685129054721) (59649589127497217)
Before giving one more example, let us remark that this implementation admits a
lot of tweaking. Many integers will be factored with the default values but others will
