The internal workings of Shank's algorithm rely on the comparison of
two ordered lists. While the algorithm does not describe precisely
what kind of data structure would be best suited for implementing the
list, an array would be the best approach to store the elements of the
lists. The reason being that searching for a pair of elements with
equal values can be done more efficiently with an array than with other
data structures. However, the two lists that Shank describes can have up to
elements which can be a fairly
large number. The C programming language only allows arrays with an
int number of elements. Given that the DL problem involves using
numbers of about 500 bits, the int type in C is not suited for
this task since it can represent numbers of up to 32 bits or less, depending
on the platform.
As a consequence, a different data structure was needed for this implementation. We chose a linked list, which allows for any number of elements as long as sufficient memory is available. The drawback of this structure is its poor performance when searching for a given element. An additional problem of linked lists is the amount of time required to store large amounts of elements, as is the case in Shank's algorithm when applied to full size crypto systems. Some tests for storing elements only were performed, yieling the following results:
Table 1.
As it can be seen in this table, there is not a linear relation between the number of elements and the time required to store them. Consequently, for a larger number of elements such as that needed in Shank's algorithm, a linked list is certainly slow.