Cryptography Reference
In-Depth Information
Exercise 2.7
Experiment by using the
TrialDivideTiming
function with dif-
ferent data sets of integers in order to obtain the timing functions that fit these data.
In each case, compare the function obtained with the expected one and check that
subtracting some small constant value from the times list gives a timing function
which is closer to the theoretically expected one.
In order to be able to plot the data points we have used, we build the list of these
points, where each point will be given as a list of length two, whose first element is
an integer and whose second element is the time taken by
TrialDivide
on this
integer:
l := [ListTools:-LengthSplit(ListTools:-Interleave(plist, tlist), 2)]:
Now we plot the curve
t
together with the set of data points we have obtained; this
lets us graphically appreciate that the exponential function
t
does fit the data well.
To plot the list of points we use the function
listplot
in the
plots
package
and, to take into account the fact that the running time function grows exponentially
in len
(or in ln
n
)weplot
t
with the
semilogplot
command (also from the
plots
package), which gives the horizontal axis a logarithmic scale.
(
n
)
> with(plots):
display(title='Trial division timing', {semilogplot(t, n=2ˆ52..2ˆ56, color=black),
listplot(l, color=black, style=point, symbol=circle, symbolsize=10)}, axes=boxed)
The output of this command is the following plot:
