Cryptography Reference
In-Depth Information
return false
end if;
if 2ˆ56 < n then
error "number too big"
end if;
s := isqrt(n);
r:=1;
for p in primearray while r <> 0 and p <= s do
r := modp(n, p)
end do;
evalb(r < > 0)
end proc:
The next function measures the time taken by
TrialDivide
when acting on a
given integer:
> TrialDivideTiming := proc(value)
local t;
t := time();
TrialDivide(value);
time()-t
end proc:
Now, in order to time the function
TrialDivide
, we build up a sample of
primes (we use Maple's function
prevprime
for speed but, of course, we could
use
TrialDivide
as well). The reason of taking prime numbers is that these are
the integers that require the most time when trial divided (most composite numbers
have small prime factors and hence require very little time to be tested).
> plist := [seq(prevprime(i*2ˆ52), i=1..16)];
plist := [4503599627370449, 9007199254740881, 13510798882111483, 18014398509481951,
22517998136852473, 27021597764222939,31525197391593467, 36028797018963913,
40532396646334423, 45035996273704937, 49539595901075453, 54043195528445869,
58546795155816433, 63050394783186917, 67553994410557429, 72057594037927931]
Next we time
TrialDivide
actingontheseprimes:
> tlist := map(TrialDivideTiming, plist);
tlist := [8.047, 11.172, 13.531, 15.531, 17.234, 18.751, 20.266, 21.609, 22.859,
23.938, 25.109, 26.172, 27.173, 28.171, 29.157, 30.047]
We now approximate the time function. We expect this function to be proportional
to a power of
n
, where the exponent should be close to 0
5. Observe that the running
time will be really exponential when given as a function of the size of the number
(or of its logarithm) although it is just a power when given as a function of
n
. Because
of this we use Maple's function
PowerFit
from the
Statistics
package, which
applies the least-squares method to build a model function of the form
a
.
n
b
·
that fits
these data points:
> t := Statistics:-PowerFit(plist, tlist, n);
2.91575852460995 10ˆ-7 nˆ0.475299605601998410
n
0
.
476
and we see that the
exponent obtained is close to 0.5 as expected. It is reasonable to expect that, when
performing these timings with Maple, there is some overhead time. If we subtract
a small constant value from the times in
tlist
above and repeat the computation
of the model function, we will see that the resulting function is even closer to the
theoretically expected one (i.e., the exponent is closer to 0.5).
10
−
7
The function obtained is approximately 2
.
92
·
·
