Cryptography Reference
In-Depth Information
Maple's function
numtheory:-msqrt
which, as already remarked, computes
modular square roots (using Algorithm 2.8 for prime moduli) and is here applied
to compute the square roots of the polynomial values modulo the sieving primes.
The array
sievearray
is filled with an integer approximation of the value of
the binary logarithm of
Q
(
t
)
minus the expected contribution of the prime factors of
corresponding to the small pri
mes
that are not used for sieving. The logarithm is
approximated by
round
(log
2
(
Q
(
t
)
M
√
mn
2
))
because the value of
Q
(
t
)
=
(
t
+
b
)
−
mn
is approximately bounded by 2
M
√
mn
. We disregarded
the factor 2 which would add 1 to the logarithm because this can be compensated
later by setting the threshold to trial divide the polynomial values one unit lower.
The expected contribution of the non-sieving primes is computed using the function
g
and is subtracted from the log approximation to compensate not sieving with these
primes. The function that does the initialization is then the following:
on the interval
[−
M
,
M
]
> Initialization := proc(n, c, cutoff)
local z, m, mn, b, B, M, fb, pr, sp, svp, nsvp, sievingprimes,
i, svplogs, splog, sqroots, polroots, logapprox, sievearray;
z := MultSelect(n, ':-c' = c);
m := z[1];
mn := m*n;
B := ceil(evalf(c*sqrt(exp(sqrt(ln(mn)*ln(ln(mn)))))));
fb := z[2];
b := isqrt(mn);
if bˆ2 < mn then
b:=b+1
end if;
pr := selectremove(x -> evalb(x<=cutoff) or member(x,numtheory:-factorset(m)),fb);
sp := pr[1];
svp := pr[2];
nsvp := nops(svp);
splog := add(g(i, m, n)*log[2.](i), i = sp[2 .. -1]);
M := round(evalf(c*exp(sqrt(ln(mn)*ln(ln(mn))))/(ln(B)*ln(ln(B)))));
fb := Array(fb, datatype = integer[4]);
sievingprimes := Array(svp, datatype = integer[4]);
svplogs := Array(1 .. nsvp, datatype = integer[2]);
for i to nsvp do
svplogs[i] := round(log[2.](sievingprimes[i]))
end do;
sqroots := Array(map(i -> numtheory:-msqrt(mn, i), svp), datatype = integer[4]);
polroots := Array(1 .. nsvp, 1 .. 2, datatype = integer[4]);
for i to nsvp do
polroots[i, 1] := (sqroots[i]-b) mod sievingprimes[i];
polroots[i, 2] := (-sqroots[i]-b) mod sievingprimes[i]
end do;
logapprox := round(log[2.](M)+log[2.](isqrt(mn))-splog);
sievearray := Array(1 .. 2*M+1, logapprox, datatype = integer[2]);
[m, mn, B, b, M, fb, sievingprimes, svplogs, nsvp, polroots, sievearray]
end proc:
The next function implements the sieve. No arrays or other data structures are
created and no Maple functions except basic programming ones and arithmetic
operations are used within this procedure in order to allow it to be compilable by the
external C compiler. The only modification that has to be done for it to be compilable
from Maple is to change the data type of the arrays
svplogs
and
sievearray
from
integer[2]
to
integer[4]
. The function has no output but the array
sievearray
is modified by subtracting the logarithms of the sieving primes at the
appropriate places as explained in Algorithm 6.5.
