Random mapping statistics

Philippe Flajolet; Andrew M. Odlyzko

doi:10.1007/3-540-46885-4_34

Random mapping statistics

Philippe Flajolet, Andrew M. Odlyzko

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

196 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 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	https://doi.org/10.1007/3-540-46885-4_34
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.

Publisher link

10.1007/3-540-46885-4_34

Find It

Find It at U of M Libraries

Cite this

Flajolet, P., & Odlyzko, A. M. (1990). Random mapping statistics. In J. Vandewalle, & J-J. Quisquater (Eds.), Advances in Cryptology - EUROCRYPT 1989 - Workshop on the Theory and Application of Cryptographic Techniques, Proceedings (pp. 329-354). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 434 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-46885-4_34

Random mapping statistics. / Flajolet, Philippe; Odlyzko, Andrew M.

Advances in Cryptology - EUROCRYPT 1989 - Workshop on the Theory and Application of Cryptographic Techniques, Proceedings. ed. / Joos Vandewalle; Jean-Jacques Quisquater. Springer Verlag, 1990. p. 329-354 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 434 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Flajolet, P & Odlyzko, AM 1990, Random mapping statistics. in J Vandewalle & J-J Quisquater (eds), Advances in Cryptology - EUROCRYPT 1989 - Workshop on the Theory and Application of Cryptographic Techniques, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 434 LNCS, Springer Verlag, pp. 329-354, 7th European Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1989, Houthalen, Belgium, 4/10/89. https://doi.org/10.1007/3-540-46885-4_34

Flajolet P, Odlyzko AM. Random mapping statistics. In Vandewalle J, Quisquater J-J, editors, Advances in Cryptology - EUROCRYPT 1989 - Workshop on the Theory and Application of Cryptographic Techniques, Proceedings. Springer Verlag. 1990. p. 329-354. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-46885-4_34

Flajolet, Philippe ; Odlyzko, Andrew M. / Random mapping statistics. Advances in Cryptology - EUROCRYPT 1989 - Workshop on the Theory and Application of Cryptographic Techniques, Proceedings. editor / Joos Vandewalle ; Jean-Jacques Quisquater. Springer Verlag, 1990. pp. 329-354 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{56c3368b4f014a8a88bf3b5bb8f53e4b,

title = "Random mapping statistics",

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.",

author = "Philippe Flajolet and Odlyzko, {Andrew M.}",

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: {\textcopyright} Springer-Verlag Berlin Heidelberg 1990.; 7th European Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1989 ; Conference date: 10-04-1989 Through 13-04-1989",

year = "1990",

doi = "10.1007/3-540-46885-4_34",

language = "English (US)",

isbn = "9783540534334",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "329--354",

editor = "Joos Vandewalle and Jean-Jacques Quisquater",

booktitle = "Advances in Cryptology - EUROCRYPT 1989 - Workshop on the Theory and Application of Cryptographic Techniques, Proceedings",

}

TY - GEN

T1 - Random mapping statistics

AU - Flajolet, Philippe

AU - Odlyzko, Andrew M.

N1 - 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.

PY - 1990

Y1 - 1990

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84915939958&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84915939958&partnerID=8YFLogxK

U2 - 10.1007/3-540-46885-4_34

DO - 10.1007/3-540-46885-4_34

M3 - Conference contribution

AN - SCOPUS:84915939958

SN - 9783540534334

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

SP - 329

EP - 354

BT - Advances in Cryptology - EUROCRYPT 1989 - Workshop on the Theory and Application of Cryptographic Techniques, Proceedings

A2 - Vandewalle, Joos

A2 - Quisquater, Jean-Jacques

PB - Springer Verlag

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

Y2 - 10 April 1989 through 13 April 1989

ER -

Random mapping statistics

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this