Geodesic
Cycle detection algorithms and their applications
Fundamentalʹnaâ i prikladnaâ matematika, Tome 16 (2010) no. 6, pp. 109-122.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper considers several cycle detection algorithms. Proofs of their correctness are given, bounds for complexity are obtained, some number theory applications like the factorization of integers and the discrete log problem are examined. 
@article{FPM_2010_16_6_a8,
     author = {A. Yu. Nesterenko},
     title = {Cycle detection algorithms and their applications},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {109--122},
     publisher = {mathdoc},
     volume = {16},
     number = {6},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2010_16_6_a8/}
}
TY  - JOUR
AU  - A. Yu. Nesterenko
TI  - Cycle detection algorithms and their applications
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2010
SP  - 109
EP  - 122
VL  - 16
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2010_16_6_a8/
LA  - ru
ID  - FPM_2010_16_6_a8
ER  - 
%0 Journal Article
%A A. Yu. Nesterenko
%T Cycle detection algorithms and their applications
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2010
%P 109-122
%V 16
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2010_16_6_a8/
%G ru
%F FPM_2010_16_6_a8
A. Yu. Nesterenko. Cycle detection algorithms and their applications. Fundamentalʹnaâ i prikladnaâ matematika, Tome 16 (2010) no. 6, pp. 109-122. http://geodesic.mathdoc.fr/item/FPM_2010_16_6_a8/

[1] Kolchin V. F., Sluchainye grafy, Fizmatlit, M., 2004

[2] Uorren G. C., Algoritmicheskie tryuki dlya programmistov, Vilyams, M., 2003

[3] Beeler M., Gosper R. W., Schroeppel R., HACMEM MIT Artifical Intelligence Laboratory AIM 239, 1972

[4] Biham E., “New techniques for cryptanalysis of hash functions and improved attacks on Snefru”, Fast Software Encryption, 15th International Workshop, FSE 2008 (Lausanne, Switzerland, 2008)

[5] Brent R. P., “An improved Monte Carlo factorization algorithm”, BIT, 20 (1980), 176–184 | DOI | MR | Zbl

[6] Cohen H., A Course in Computational Algebraic Number Theory, Springer, Berlin, 1996 | MR

[7] Gordon D., “Discrete logarithms in $F_p$ using the number field sieve”, SIAM J. Discrete Math., 6 (1993), 124–138 | DOI | MR | Zbl

[8] Joux A., Lercier R., “Improvements to the general number field sieve for discrete logarithms in prime fields”, Math. Comp., 72:242 (2003), 953–967 | DOI | MR | Zbl

[9] Knuth D., The Art of Computer Programming, v. I, Fundamental Algorithms, Addison-Wesley, 1969 | MR | Zbl

[10] Knuth D., The Art of Computer Programming, v. II, Seminumerical Algorithms, Addison-Wesley, 1969 | MR | Zbl

[11] Nivash G., “Cycle detecting using a stack”, J. Inform. Process. Letters, 90:3 (2004) | MR

[12] Van Oorschot P. C., Wiener M. J., “Parallel collision search with cryptanalytic applications”, J. Cryptology, 12 (1999), 1–28 | DOI | MR | Zbl

[13] Pollard J. M., “A Monte Carlo method for factorization”, BIT, 15 (1975), 331–334 | DOI | MR | Zbl

[14] Sedgewick R., Szymansky T. G., Yao A. C., “The complexity of finding cycles in periodic functions”, SIAM J. Comput., 11:2 (1982), 376–390 | DOI | MR | Zbl

[15] Teske E., “On random walks for Pollard's rho method”, Math. Comp., 70 (2001), 809–825 | DOI | MR | Zbl