Cryptography Reference
In-Depth Information
n
1
/
2
+
ε
)
(
as
O
. The running time is, therefore, exponential, and using this test with a
1024-bit number would approximately require—in case the number is prime—
> evalf(Li(sqrt(2ˆ1024)));
3.788709545*10ˆ151
divisions, which is far from feasible. It is not necessary to resort to such big numbers
to reach the practical limits of this algorithm. In fact, it has been estimated in [60]
that testing the primality of a 50-digit integer this way would require a computational
effort equivalent to all the computation done until the beginning of the twenty-first
century, i.e., around 10
24
bit operations. It must be pointed out, however, that trial
division is often useful as a first step in factoring algorithms, where it serves to get
rid of small factors quickly.
Exercise 2.6
Modify the function
TrialDivision
so that the function itself
computes the primes used and does not require
primelist
to be computed
independently.
2.3.3.3 An Experiment on Trial Division Timing
We are now going to do an experiment—that may serve as a model for other experi-
ments with different algorithms—to test the running time of trial division in practice
and check how well it agrees with the theoretically expected one. To approximate
the complexity of the algorithm we want to work with numbers as large as possible
and so, to minimize the time and memory required to build the list of primes by
means of the sieve of Eratosthenes, we will use an array instead of a list. Another
advantage of using arrays throughout is that this will allow us to write functions that
are compilable by the external C compiler included with Maple, with a considerable
gain in speed; thus this experiment will also serve to introduce new features of Maple
as a programming language. In order to achieve these goals we will modify the pre-
vious procedure
Eratosthenes
in which, after running the sieve, the initial array
contains zeros in the positions corresponding to primes and ones in the positions cor-
responding to composites. We want an array containing only the sequence of prime
numbers less than or equal to
n
and the next function,
ReduceArray
, converts the
larger array to this form.
> ReduceArray := proc(n::integer[4],
a::Array(datatype=integer[4]), b::Array(datatype=integer[4]))
local i, j;
j:=1;
for i from 2 to n do
if a[i] = 0 then a[i] := 2*i-1 end if
end do;
foritondo
if a[i] <> 1 then
b[j] := a[i];
j:=j+1
end if
end do
end proc:
