## Abstract

Random mappings from a finite set into itself axe either a heuristic or an exact model for a variety of applications in random number generation, computational number theory, cryptography, and the analysis of algorithms at large. This paper introduces a general framework in which the analysis of about twenty characteristic parameters of random mappings is carried out: These parameters are studied systematically through the use of generating functions and singularity analysis. In particular, an open problem of Knuth is solved, namely that of finding the expected diameter of a random mapping. The same approach is applicable to a larger class of discrete combinatorial models and possibilities of automated analysis using symbolic manipulation systems (“computer algebra”) are also briefly discussed.

Original language | English (US) |
---|---|

Title of host publication | Advances in Cryptology - EUROCRYPT 1989 - Workshop on the Theory and Application of Cryptographic Techniques, Proceedings |

Editors | Joos Vandewalle, Jean-Jacques Quisquater |

Publisher | Springer Verlag |

Pages | 329-354 |

Number of pages | 26 |

ISBN (Print) | 9783540534334 |

DOIs | |

State | Published - 1990 |

Externally published | Yes |

Event | 7th European Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1989 - Houthalen, Belgium Duration: Apr 10 1989 → Apr 13 1989 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 434 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 7th European Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1989 |
---|---|

Country/Territory | Belgium |

City | Houthalen |

Period | 4/10/89 → 4/13/89 |

### Bibliographical note

Funding Information:Acknowledgements. This research was supported in part by the ESPRIT I1 Basic Research Actions Program of the EC under contract No. 3075 (project ALCOM).

Publisher Copyright:

© Springer-Verlag Berlin Heidelberg 1990.