The DOI matches its Crossref record; 39 of the 42 references it cites were found in a registry or an index.
Random Mapping Statistics
Open accessOverview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“For y $ ←Y , the probability of y to be a j-node, denoted by q (a N ) : Z ≥0 → [0, 1], is q (a N ) ( j) ≈ 1 e a • a j j! . (5 ) For x $ ←X , the probability of f (x) to be a j-node, denoted by r (a N ) : N → [0, 1], is r (a N ) ( j) ≈ j • q (a N ) ( j). (6 )”
From Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2 (2018) · cites this paper as [29]
Citations
Cites
The Art of Computer Programming: Volume 3: Sorting and Searching
Knuth, D. E. (1973) · Cited by 3,955
The Art of Computer Programming. Volume 2: Seminumerical Algorithms.
Taussky, O., & Knuth, D. E. (1970) · American Mathematical Monthly · doi:10.2307/2317055 · Cited by 3,863
Asymptotics and Special Functions
Olver, F. W. J. (1997) · A K Peters/CRC Press eBooks · doi:10.1201/9781439864548 · Cited by 3,368
Titchmarsh, E. C. (1932) · BURJC Digital (King Juan Carlos University) · Cited by 2,290
Stanley, R. P. (1986) · Springer eBooks · doi:10.1007/978-1-4615-9763-6 · Cited by 1,796
Asymptotic methods in analysis
de Bruijn, N. G. (1958) · International Linear Collider · Cited by 1,332
Pemantle, R., Wilson, M. C., & Melczer, S. (2024) · Cambridge University Press eBooks · doi:10.1017/9781108874144.003 · Cited by 939
Singularity Analysis of Generating Functions
Flajolet, P., & Odlyzko, A. M. (1990) · SIAM Journal on Discrete Mathematics · doi:10.1137/0403019 · Cited by 786
Self-citationThe Art of Computer Programming, Volume 3, Sorting and Searching
Wilkes, M. (1974) · The Computer Journal · doi:10.1093/comjnl/17.4.324 · Cited by 731
A monte carlo method for factorization
Pollard, J. M. (1975) · BIT Numerical Mathematics · doi:10.1007/bf01933667 · Cited by 403
Flagged first, then by citations
3 of the 42 references couldn’t be matched to a known paper.
Research works printed but not linked: 9
- A. Z. Broder. Weighted random mappings; properties and applications. Technical Report STAN-CS-85-1054, Computer Science Dept., Stanford University, 1985. (Author’s PhD Thesis).
- B.W. Char, K.O. Geddes, G.H. Gonnet, M.B. Monagan, and S.M. Watt. MAPLE: Reference Manual. University of Waterloo, 1988. 5th edition.
- M. A. Evgrafov. Analytic Functions. Dover, New York, 1966.
- J. Jaworski. Random Mappings. PhD thesis, A. Mickiewicz University, 1985. (In Polish).
- V. F. Kolchin. Random Mappings. Optimization Software Inc., New York, 1986. Translated from Slučajnye Otobraženija, Nauka, Moscow, 1984.
- L. R. Mutafčiev. On some stochastic problems of discrete mathematics. In Mathematics and Education in Mathematics (Sunny Beach), pages 57–80, Bulgarian Academy of Sciences, Sophia, Bulgaria, 1984.
- A. I. Pavlov. On an equation in a symmetric semigroup. Proceedings of the Steklov Institute of Mathematics, 177(4):121–128, 1988. (Issue on Probabilistic Problems of Discrete Mathematics).
- Yu. L. Pavlov. On random mappings with constraints on the number of cycles. Proceedings of the Steklov Institute of Mathematics, 177(4):131–143, 1988. (Issue on Probabilistic Problems of Discrete Mathematics).
- M. Soria. Méthodes d’analyse pour les constructions combinatories et les algorithmes. Doctorat ès sciences, Université de Paris-Sud, Orsay, 1989.
Cited by
Sorted by citations
Items 101–200 of 274
Period lengths of chaotic pseudo-random number generators
Keller, J., & Wiese, H. (2007) · Cited by 11
Вычисление распределений характеристик чисел компонент и циклических точек случайного отображения
Зубков, А. М. (2010) · Математические вопросы криптографии · doi:10.4213/mvk7 · Cited by 11
Fast and Small Nonlinear Pseudorandom Number Generators for Computer Simulation
Neves, S., & Araújo, F. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31464-3_10 · Cited by 11
On moment sequences and mixed Poisson distributions
Kuba, M., & Panholzer, A. (2016) · Probability Surveys · doi:10.1214/14-ps244 · Cited by 11
Linear models for a time-variant permutation generator
Golić, J. D. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.796378 · Cited by 11
Fast Synchronization of Random AutomataPreprint
Nicaud, C. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1404.6962 · Cited by 11
A structural analysis of the A5/1 state transition graph∗Preprint
Wijs, A. J., Beckmann, C. A., Fedorowicz, J., Keller, J., Meyer, U., Beckmann, A., Fedorowicz, J., Keller, J., & Meyer, U. (2016) · Cited by 11
Lin, Z., Lin, D., & Pei, D. (2016) · Cryptography and Communications · doi:10.1007/s12095-016-0183-8 · Cited by 10
Functional Graphs and Their Applications in Generic Attacks on Iterated Hash Constructions
Bao, Z., Guo, J., & Wang, L. (2018) · IACR Transactions on Symmetric Cryptology · doi:10.46586/tosc.v2018.i1.201-253 · Cited by 10
Local properties of random mappings with exchangeable in-degrees
Hansen, J. C., & Jaworski, J. (2008) · Advances in Applied Probability · doi:10.1017/s0001867800002433 · Cited by 10
Rationalizable strategies in random games
Pei, T., & Takahashi, S. (2019) · Games and Economic Behavior · doi:10.1016/j.geb.2019.08.011 · Cited by 10
On the probability of being synchronizablePreprint
Berlinkov, M. V. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1304.5774 · Cited by 10
A structural analysis of the A5/1 state transition graph
Beckmann, A., Fedorowicz, J., Keller, J., & Meyer, U. (2012) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.99.4 · Cited by 9
On Functional Graphs of Quadratic Polynomials
Mans, B., Sha, M., Shparlinski, I. E., & Sutantyo, D. (2017) · Experimental Mathematics · doi:10.1080/10586458.2017.1391725 · Cited by 9
Improved Generic Attacks Against Hash-Based MACs and HAIFA
Dinur, I., & Leurent, G. (2016) · Algorithmica · doi:10.1007/s00453-016-0236-6 · Cited by 9
Stream Ciphers Using a Random Update Function: Study of the Entropy of the Inner State
Röck, A. (2008) · Springer eBooks · doi:10.1007/978-3-540-68164-9_18 · Cited by 9
Efficient Sampling of the Structure of Crypto Generators’ State Transition Graphs
Keller, J. (2007) · Springer eBooks · doi:10.1007/978-1-84628-750-3_1 · Cited by 9
The graph structure of a deterministic automaton chosen at random
Cai, X. S., & Devroye, L. (2016) · Random Structures and Algorithms · doi:10.1002/rsa.20707 · Cited by 9
La securite des primitives cryptographiques
Serge Vaudenay, B. (1995) · Cited by 9
Memoryless near-collisions, revisited
Lamberger, M., & Teufl, E. (2012) · Information Processing Letters · doi:10.1016/j.ipl.2012.11.004 · Cited by 9
Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata
Felice, S. D., & Nicaud, C. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38771-5_17 · Cited by 8
Periods of iterated rational functions
Burnette, C., & Schmutz, E. J. (2016) · International Journal of Number Theory · doi:10.1142/s1793042117500713 · Cited by 8
Совокупность образов подмножества конечного множества при итерациях случайных отображений
Зубков, А. М., Серов, А. А., & Serov, A. A. (2014) · Дискретная математика · doi:10.4213/dm1303 · Cited by 8
Зубков, А. М., & Олегович, М. В. (2017) · Математические вопросы криптографии · doi:10.4213/mvk239 · Cited by 8
The Image Size of Iterated Rational Maps over Finite Fields
Juul, J. (2019) · International Mathematics Research Notices · doi:10.1093/imrn/rnz217 · Cited by 8
On the fixed points of the map $x \mapsto x^x$ modulo a prime
Kurlberg, P., Luca, F., & Shparlinski, I. E. (2015) · Mathematical Research Letters · doi:10.4310/mrl.2015.v22.n1.a8 · Cited by 8
A Statistical Look at Maps of the Discrete Logarithm
Lindle, N. (2008) · Rose-Hulman Scholar (Rose–Hulman Institute of Technology) · Cited by 8
The asymptotic distribution of the diameter of a random mapping
Aldous, D., & Pitman, J. (2002) · Comptes Rendus Mathématique · doi:10.1016/s1631-073x(02)02386-5 · Cited by 8
On iteration-based security flaws in modern hash functions
Kortelainen, T. (2014) · Cited by 7
Uniform asymptotics of some Abel sums arising in coding theory
Hwang, H. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00238-3 · Cited by 7
Предельная теорема для мощности образа подмножества при композиции случайных отображений
Зубков, А. М., & Серов, А. А. (2017) · Дискретная математика · doi:10.4213/dm1403 · Cited by 7
Hwang, H. (1998) · Combinatorics Probability Computing · doi:10.1017/s0963548397003295 · Cited by 7
Random Mappings with Restricted Preimages
MacFie, A., & Panario, D. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33481-8_14 · Cited by 6
Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets
Viola, A. (2010) · Discrete Mathematics & Theoretical Computer Science · doi:10.46298/dmtcs.519 · Cited by 6
Numeration and discrete dynamical systems
Berthé, V. (2011) · Computing · doi:10.1007/s00607-011-0181-9 · Cited by 6
A fast and secure stream cipher based on cellular automata over GF(q)
Mihaljević, M. J., Yuliang Zheng, A., & Imai, H. (2002) · Globecom · doi:10.1109/glocom.1998.775806 · Cited by 6
Bellah, E., Garton, D., Tannenbaum, E., & Walton, N. (2017) · Involve a Journal of Mathematics · doi:10.2140/involve.2018.11.169 · Cited by 6
Limit theorem for the size of an image of subset under compositions of random mappings
Zubkov, A. M., & Серов, А. А. (2018) · Discrete Mathematics and Applications · doi:10.1515/dma-2018-0013 · Cited by 6
Gravel, C., Panario, D., & Thomson, D. (2019) · Cryptography and Communications · doi:10.1007/s12095-019-00384-4 · Cited by 6
Periodic points of polynomials over finite fields
Garton, D. (2022) · Transactions of the American Mathematical Society · doi:10.1090/tran/8634 · Cited by 6
On the heuristic of approximating polynomials over finite fields by random mappings
Martins, R. S. V., & Panario, D. (2015) · International Journal of Number Theory · doi:10.1142/s1793042116501219 · Cited by 7
Exact Largest and Smallest Size of Components
Panario, D., & Richmond, B. (2001) · Algorithmica · doi:10.1007/s00453-001-0047-1 · Cited by 6
Discrete Logarithms on Elliptic Curves
Blumenfeld, A. (2011) · Rose-Hulman Scholar (Rose–Hulman Institute of Technology) · Cited by 6
One-dimensional cellular automata with random rules: longest temporal period of a periodic solution
Gravner, J., & Liu, X. (2022) · Electronic Journal of Probability · doi:10.1214/22-ejp744 · Cited by 6
The Analysis of Linear Probing Hashing with Buckets
Viola, A., & Poblete, P. V. (1998) · Algorithmica · doi:10.1007/pl00009208 · Cited by 6
Completion of a Rational Function Sequence of CarlitzPreprint
Smiley, L. M. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.math/0006106 · Cited by 6
Halunen, K. (2012) · Cited by 5
О множестве образов $k$-кратной итерации равновероятного случайного отображения
Олегович, М. В., & Михайлов, В. Г. (2018) · Математические вопросы криптографии · doi:10.4213/mvk264 · Cited by 5
The identity is the most likely exchange shuffle for large n
Goldstein, D., & Moews, D. (2003) · Aequationes Mathematicae · doi:10.1007/s000100300001 · Cited by 5
Structural Transition in Random Mappings
Hansen, J. C., & Jaworski, J. (2014) · The Electronic Journal of Combinatorics · doi:10.37236/3572 · Cited by 5
Parallel Storage Allocation for Intermediate Results During Exploration of Random Mappings
Heichler, J., Keller, J., Sibeyn, J. F., & Halle, M.-L.-U. (2008) · Cited by 5
Structure and Randomness of the Discrete Lambert Map
Chen, J., & Lotts, M. (2011) · Rose-Hulman Scholar (Rose–Hulman Institute of Technology) · Cited by 5
Образы конечного множества при итерациях двух случайных зависимых отображений
Серов, А. А. (2015) · Дискретная математика · doi:10.4213/dm1352 · Cited by 5
Fast Synchronization of Random Automata
Nicaud, C. (2016) · HAL · doi:10.4230/lipics.approx-random.2016.43 · Cited by 5
Period Lengths for Iterated Functions
Schmutz, E. J. (2010) · Combinatorics Probability Computing · doi:10.1017/s0963548310000337 · Cited by 5
Fixed point proportions for Galois groups of non-geometric iterated extensions
Juul, J. (2018) · Acta Arithmetica · doi:10.4064/aa8535-2-2018 · Cited by 5
Generic Attack on Duplex-Based AEAD Modes Using Random Function Statistics
Gilbert, H., Boissier, R. H., Khati, L., & Rotella, Y. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-30634-1_12 · Cited by 5
Structure and Statistics of the Self-Power Map
Friedrichsen, M., Larson, B., & McDowell, E. J. (2010) · Rose-Hulman Scholar (Rose–Hulman Institute of Technology) · Cited by 5
On the Profile of Random Forests
Gittenberger, B. (2002) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-8211-8_17 · Cited by 5
Stark, D. (1999) · Combinatorics Probability Computing · doi:10.1017/s0963548399004009 · Cited by 5
Algorithmes de calcul de logarithmes discrets dans les corps finisPreprint
Thomé, E. (2003) · HAL (Le Centre pour la Communication Scientifique Directe) · Cited by 5
Expected deadlock time in a multiprocessing system
Compton, K. J., & Ravishankar, C. V. (1995) · Journal of the ACM · doi:10.1145/210346.210412 · Cited by 5
Cryptanalysis of Hash Functions
Toz, D. (2013) · Lirias (KU Leuven) · Cited by 5
Images of a finite set under iterations of two random dependent mappings
Серов, А. А. (2016) · Discrete Mathematics and Applications · doi:10.1515/dma-2016-0015 · Cited by 4
Iterated monodromy groups of rational functions and periodic points over finite fields
Bridy, A., Jones, R., Kelsey, G. A., & Lodge, R. (2023) · Mathematische Annalen · doi:10.1007/s00208-023-02745-0 · Cited by 4
Evidence for the Dynamical Brauer–Manin Criterion
Amerik, E. Y., Kurlberg, P., Nguyen, K. D., Towsley, A., Viray, B., & Voloch, J. F. (2015) · Experimental Mathematics · doi:10.1080/10586458.2015.1056889 · Cited by 5
Bhaumik, R., Dutta, A., Guo, J., Jean, J., Mouha, N., & Nikolić, I. (2015) · Cited by 4
Tweaking cryptographic primitives with moderate state space by direct manipulation
Keller, J., & Spenger, G. (2017) · International Conference on Communications · doi:10.1109/icc.2017.7996733 · Cited by 4
Слои в графе $k$-кратной итерации равновероятного случайного отображения
Олегович, М. В. (2019) · Математические вопросы криптографии · doi:10.4213/mvk277 · Cited by 4
Improving Cryptanalytic Applications with Stochastic Runtimes on GPUs
Oden, L., & Keller, J. (2021) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw52791.2021.00077 · Cited by 4
An efficient SAT-based algorithm for finding short cycles in cryptographic algorithms
Dubrova, E., & Teslenko, M. (2018) · IEEE International Symposium on Hardware Oriented Security and Trust (HOST) · doi:10.1109/hst.2018.8383892 · Cited by 4
Pattern-based Programming Abstractions for Heterogeneous Parallel Computing
Ernstsson, A. (2022) · Linköping studies in science and technology. Dissertations · doi:10.3384/9789179291969 · Cited by 4
Periodic Properties of Counter Assisted Stream Ciphers
Scavenius, O., Boesgaard, M., Pedersen, T. B., Christiansen, J., & Rijmen, V. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24660-2_4 · Cited by 4
Profiles of large combinatorial structures
Lugo, M. (2010) · Cited by 4
On the number of predecessors in constrained random mappings
Gittenberger, B. (1997) · Statistics & Probability Letters · doi:10.1016/s0167-7152(97)00045-x · Cited by 4
Agent-Based Models as Markov Chains
Banisch, S. (2015) · Understanding complex systems · doi:10.1007/978-3-319-24877-6_3 · Cited by 4
Ant Colony-Inspired Parallel Algorithm to Improve Cryptographic Pseudo Random Number Generators
Keller, J., Spenger, G., & Wendzel, S. (2017) · IEEE Security and Privacy Workshops (SPW) · doi:10.1109/spw.2017.31 · Cited by 4
Solving discrete logarithm problems faster with the aid of pre-computation
Hong, J., & Lee, H. (2019) · Discrete Applied Mathematics · doi:10.1016/j.dam.2019.03.023 · Cited by 4
Latent Semantic Mapping: Principles & Applications
Bellegarda, J. R. (2007) · Synthesis lectures on speech and audio processing · doi:10.2200/s00048ed1v01y200609sap003 · Cited by 4
Security and Privacy in RFID Protocols
Bocchetti, S. (2006) · Cited by 4
The Discrete Logarithm Problem and Ternary Functional Graphs
Frederick, C., & Brugger, M. (2007) · Rose-Hulman Scholar (Rose–Hulman Institute of Technology) · Cited by 4
Smart card implementation of a digital signature scheme for Twisted Edwards curves
Duif, N. (2011) · TU/e Research Portal · Cited by 4
Brownian bridge asymptotics for random mappings
Aldous, D. (1992) · Advances in Applied Probability · doi:10.1017/s0001867800024599 · Cited by 4
THE PROBABILISTIC STRUCTURE OF DISCRETE AGENT-BASED MODELSPreprint
(2016) · Cited by 4
Almost optimal sparsification of random geometric graphs
Broutin, N., Devroye, L., & Lugosi, G. (2016) · The Annals of Applied Probability · doi:10.1214/15-aap1170 · Cited by 3
Collision bounds for the additive Pollard rho algorithm for solving discrete logarithms
Bos, J. W., Dudeanu, A., & Jetchev, D. (2014) · Journal of Mathematical Cryptology · doi:10.1515/jmc-2012-0032 · Cited by 3
Оценки среднего размера образа подмножества при композиции случайных отображений
Зубков, А. М., & Серов, А. А. (2018) · Дискретная математика · doi:10.4213/dm1521 · Cited by 3
New Generic Attacks Against Hash-based MACs.
Leurent, G., Peyrin, T., & Wang, L. (2014) · Cited by 3
Proof-of-work based new encoding scheme for information hiding purposes
Rajba, P., Keller, J., & Mazurczyk, W. (2023) · International Conference on Availability, Reliability and Security (ARES) · doi:10.1145/3600160.3605085 · Cited by 3
The Cycle Structure of Unicritical Polynomials
Bridy, A., & Garton, D. (2018) · International Mathematics Research Notices · doi:10.1093/imrn/rny232 · Cited by 3
Open Problems for Polynomials over Finite Fields and Applications
Panario, D. (2014) · Springer eBooks · doi:10.1007/978-3-319-10683-0_6 · Cited by 3
On the birthday problem: some generalizations and applications
Rathie, P. N., & Zörnig, P. (2003) · International Journal of Mathematics and Mathematical Sciences · doi:10.1155/s0161171203110101 · Cited by 3
Parallel-External Computation of the Cycle Structure of Invertible Cryptographic Functions
Beckmann, A., & Keller, J. (2007) · Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP) · doi:10.1109/pdp.2007.61 · Cited by 3
A Note on Shanks’s Chains of Primes
Teske, E., & Williams, H. C. (2000) · Lecture notes in computer science · doi:10.1007/10722028_38 · Cited by 3
Structural improvements of chaotic PRNG implementations
Spenger, G., & Keller, J. (2016) · International Conference for Internet Technology and Secured Transactions · doi:10.1109/icitst.2016.7856754 · Cited by 3
Efficient multi-signature schemes for cooperating entities
Delos, O., & Quisquater, J.-J. (1994) · Lecture notes in computer science · doi:10.1007/3-540-57843-9_9 · Cited by 3
Network analysis of the state space of chaotic map in digital domain.Preprint
Li, C. (2014) · arXiv (Cornell University) · Cited by 3
Quantifying Studies of (Pseudo) Random Number Generation for Cryptography
Roeck, A., & SENDRIER, N. (2009) · OpenGrey (Institut de l'Information Scientifique et Technique) · Cited by 3
Propagation Rules for Graph Partitioning Constraints
Cymer, R. (2016) · Journal of Graph Algorithms and Applications · doi:10.7155/jgaa.00397 · Cited by 2
On the Analysis of Public-Key Cryptologic Algorithms
Miele, A. (2015) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5075/epfl-thesis-6603 · Cited by 2
Metadata
- Authors
- Flajolet, P., & Odlyzko, A. M.
- Affiliations
- Institut national de recherche en sciences et technologies du numérique (FR)
- AT&T (United States) (US)
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2007-11-15
- Pages
- 329-354
- OpenAlex
- W2226303357
- Cited by
- 274
- References
- 42
- Citations by year
- 2026: 1 · 2025: 4 · 2024: 5 · 2023: 7 · 2022: 6 · 2021: 6 · 2020: 9 · 2019: 15 · 2018: 12 · 2017: 11 · 2016: 15 · 2015: 15 · 2014: 17 · 2013: 11 · 2012: 13
- FWCI
- 12.13
- Type
- conference paper
- Language
- en
- Open access
- green
- inria.hal.science
- Licence
- other-oa
- Locations
- Springer eBooks (publishedVersion)
- HAL (submittedVersion, other-oa)
- Topics
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Advanced Combinatorial Mathematics
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Keywords
- random maps, finite sets, generating functions, singularity analysis, characteristic parameters, symbolic computation, random number generation, algorithm analysis
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
