9.7 IS DES A RANDOM MAPPING?
In Section 10 of Chapter 8 the mappings of the set were described.
Proposition 9.1: If F is a randomly chosen one-to-one mapping of and Z is a randomly chosen element of , then
9.1a | The probability that Z belongs to an n-cycle in and |
9.1b | The average length of the cycle containing Z is (m + 1)/2. |
Proof: First an explanation of what is meant by “random”; there are m! permutations of the elements of . By the phrase “choose a mapping F randomly”, we mean that the permutation F is selected with probability 1/m!. Similarly, by the phrase “choose randomly”, we mean that a particular is selected with probability 1/m.
Let L denote the length of the cycle of F containing Z. As Z is to be any of m values, there are (m − 1)! permutations of the ...
Get Computer Security and Cryptography now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.