Cryptography Reference
In-Depth Information
To make it compilable, the preceding function has explicit type declarations
of integers as hardware integers. We compile the function, obtaining the function
CompReduceArray
3
:
> CompReduceArray := Compiler:-Compile(ReduceArray):
Next we give the new function, called
Sieve
, that implements the sieve and
builds the array of prime numbers up to
n
. Note that in order to build this array we
need to know in advance the number of primes
n
. We did not use this knowledge
when giving the first version of the sieve as it seems inappropriate to use a much more
sophisticated algorithm in order to implement it. Now, however, we are not interested
in a function to sieve different intervals but rather in a function that allows us to build
an array of primes as large as possible to use in trial division. In this case it makes
sense to assume that we know the number of primes as given by the Maple function
numtheory:-pi
.
Sieve
is just a modification of
Eratosthenes
, and now we
use
CompReduceArray
in the final stage to produce as output an array containing
the primes.
≤
> Sieve := proc(n)
local s, f, a, b, i, j;
s := floor((isqrt(n)+1)/2);
f := floor((n+1)/2);
a := Array(1 .. f, datatype = integer[4]);
a[1] := 2;
for i from 2 to s do
if a[i] = 0 then
j := 2*iˆ2-2*i+1;
ArrayTools:-Fill(1, a, j-1, 2*i-1)
end if
end do;
b := Array(1 .. numtheory:-pi(n), datatype = integer[4]);
CompReduceArray(f, a, b);
b
end proc:
We are going to build an array containing all the primes up to 2
28
. The number of
primes in this array is
> numtheory:-pi(2ˆ28);
14630843
i.e., more than 14 million primes. The array containing the primes is then:
> primearray := Sieve(2ˆ28):
Now we give the function that performs trial division based on this array; we do
not compile it because we want it to work, even in 32-bit computers, with integers
longer than 32 bits:
> TrialDivide := proc(n)
local s, p, r;
ifn<2then
3
Compiled functions like this one are not included in the Maple language files provided on the
topic's website and must be generated by calling
Compiler:-Compile
from the corresponding
examples worksheet, where the appropriate command is already included.
