Random mapping statistics

Philippe Flajolet, Andrew M. Odlyzko

Research output: Chapter in Book/Report/Conference proceedingConference contribution

207 Scopus citations

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 languageEnglish (US)
Title of host publicationAdvances in Cryptology - EUROCRYPT 1989 - Workshop on the Theory and Application of Cryptographic Techniques, Proceedings
EditorsJoos Vandewalle, Jean-Jacques Quisquater
PublisherSpringer Verlag
Pages329-354
Number of pages26
ISBN (Print)9783540534334
DOIs
StatePublished - 1990
Externally publishedYes
Event7th European Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1989 - Houthalen, Belgium
Duration: Apr 10 1989Apr 13 1989

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume434 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th European Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1989
Country/TerritoryBelgium
CityHouthalen
Period4/10/894/13/89

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1990.

Fingerprint

Dive into the research topics of 'Random mapping statistics'. Together they form a unique fingerprint.

Cite this