Time-memory-processor trade-offs

It is demonstrated that usual time-memory trade-offs offer no asymptotic advantage over exhaustive search. Instead, trade-offs between time, memory, and parallel processing are proposed. Using this approach it is shown that most searching problems allow a trade-off between C _s, the cost per solution, and C_m, the cost of the machine: doubling C_m increases the solution rate by a factor of four, halving C_s. The machine which achieves this has an unusual architecture, with a number of processors sharing a large memory through a sorting/switching network. The implications of cryptanalysis, the knapsack problem, and multiple encryption are discussed