The core of Shank's algorithm is the search operation. If a regular
sequential search was used, it would result in O(p) comparisons.
However this can be improved by realizing a binary search, which reduces
the number of comparisons to O(
) (note
) [1]. By using a binary search,
only one list needs to be actually built. As the values of the second
list are generated, they are tested against the first list. Thus, this
method reduces memory usage by half (only one list needs to be stored
in memory) and saves the time of having to store a second list which as
we saw in Section 4.1, can take very long for large values of p.
Table 2 shows the measurements obtained when searching once for a
single element through n elements.
A search in 100000 elements like the one shown
in Table 2 would occur when using a prime whose (p-1) factors are in the
order of 34-bit.
Table 2.