Question :
Rivest's "distinguished point" (DP) method is a variable length hash chain where all chain end points have the same d-bit suffix. In the precomputation phase, a chain is computed until a value is output with the proper suffix.
During the on-line phase, the precomputed chains are checked only if a reduction on a hash value results in an output with the d-bit suffix.
(a) How many expected table lookups are required when using DP as compared to without using DP? Explain your answer.
(b) What is the practical benefit of using tables built using DPs? Explain your answer.