Cryptography Reference
In-Depth Information
The square-searching algorithm is implemented in the function Search below,
which actually serves a dual purpose: to find either squares (using Maple's issqr
as indicated above) or primes (using Maple's isprime in this case). The first input
parameter of the function is for a name which can be either squares or primes
and serves to tell the function what to search for. The remaining input parameters
length and numtrials are for two positive integers, the first of which specifies
the bit length of the integer to be searched for and the second, the number of trials to
be performed. If length is specified as k and numtrials as r then the function
makes r attempts to find a k -bit square (or prime) and prints on screen all the squares
(or primes) it finds, if any, finishing with a Search Finished statement printed
at the end.
> Search := proc(object::name, length::posint, numtrials::posint)
local test, i, n;
if object = 'squares' then
test := 'issqr'
elif object = 'primes' then
test := 'isprime'
else
error "unknown object"
end if;
randomize();
for i to numtrials do
n := RandomTools:-Generate(integer(range = 2ˆ(length-1) .. 2ˆlength-1))
if test(n) then
print(n)
end if
end do;
print('Finished Search')
end proc:
Now, we carry out the test and search for a 1024-bit square among, say, 100000
pseudo-random integers:
> Search(squares, 1024, 100000);
Finished Search
The procedure found no squares and most likely won't find them no matter how
many trials we perform because it is not feasible to find a square by this method .To
see that the problem does not lie with the procedure itself, let us make an attempt to
find 16-bit squares by testing just 1000 pseudo-random integers:
> Search(squares, 16, 1000);
51984
41209
33856
33489
Finished Search
Now four squares were found and this was due to the fact that squares are much
denser among 16-bit integers than among 1024-bit integers. The reason why the
search for a 1024-bit square was hopeless is that the probability that a random 1024-
bit integer turns out to be a square is:
> evalf((2ˆ512-ceil(sqrt(2ˆ1023)))/2ˆ1023);
4.368994848 10ˆ-155
Search WWH ::




Custom Search