Cryptography Reference
In-Depth Information
> Dependencies := proc(A::Matrix)
uses LinearAlgebra:-Modular;
local M, rd, cd, z, rk;
M := Mod(2, LinearAlgebra:-Transpose(A), integer[1]);
rd := LinearAlgebra:-RowDimension(M);
cd := LinearAlgebra:-ColumnDimension(M);
if rd < cd then
#(MatBasis requires as many rows as columns; 0-rows are added if needed)
z := Create(2, cd-rd, cd, integer[1]);
M := ArrayTools:-Concatenate(1, M, z)
end if;
rk := MatBasis(2, M, rd, true);
[LinearAlgebra:-Row(M, rk+1 .. cd)]
end proc:
The final ingredient we need is a function that computes two nontrivial factors
of
n
if the relations and the dependencies previously assembled allow it. The input
is the integer
n
being factored, the relations in the format provided by the function
Relations
and the dependencies as given by the function
Dependencies
.The
output is either two nontrivial factors of
n
or a message informing that no nontrivial
factors have been found.
> FindFactors := proc(n, rels, deps)
local fact, i, x, y;
fact := 1;
for i to nops(deps) while fact = 1 or fact = n do
x := mul(j, j = rels[1]
∼
deps[i]);
#(use x:= mul(j, j=zip('ˆ',rels[1],deps[i])) in Maple versions prior to v.13)
y := isqrt(mul(j, j = rels[2]
∼
deps[i])); #(use zip in versions prior to v.13)
fact := igcd(x+y, n)
end do;
if fact <> 1 and fact <> n then
''(fact)*''(iquo(n, fact))
else
print('No nontrivial factors found')
end if
end proc:
Example 6.16
Let us factor the integer:
> n := 516378077600327:
We start by computing the factor base; we display it as a list and then we convert
it to an array, as required by the
Relations
function:
> f := FactorBase(n);
f := Array(f):
[-1, 2, 29, 31, 37, 41, 47, 59, 71, 73, 79, 107, 127, 131, 137, 157, 181, 193, 197,
199, 223, 227, 229, 239, 241, 257, 277, 283, 307, 311, 313, 317, 331]
Observe that, once again, this factor base does not look particularly good as
many small odd primes are missing. Since small primes contribute the most to the
factorization of the
z
-values, we expect that relatively many of these values will have
to be submitted to trial division in order to find the required number of relations.
The result of computing the relations is given in Table
6.1
. The output consists of
two vectors and a matrix. The first vector contains the '
x
-values' and the second the
