Parallel-external computation of the cycle structure of invertible cryptographic functions

We present an algorithm to compute the cycle structure of large directed graphs where each node has exactly one outgoing edge. Such graphs appear as state diagrams of finite state machines such as pseudo-random number generators in cryptography. The size of the graphs necessitates that the adjacency list is kept on hard disks. Our algorithm uses multiple processing units, so that a parallel storage system has to be employed to store the graph. We present experimental resultsfor randomly chosen graphs, andfor the graph of the A5/1 generator used in GSM mobile phones.