A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm (Q968774): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||||||||||||||
(5 intermediate revisions by 4 users not shown) | |||||||||||||||
aliases / en / 0 | aliases / en / 0 | ||||||||||||||
A Birthday Paradox for Markov Chains, with an Optimal Bound for Collision in the Pollard Rho Algorithm for Discrete Logarithm | |||||||||||||||
description / en | description / en | ||||||||||||||
scientific article | scientific article; zbMATH DE number 5279301 | ||||||||||||||
Property / title | |||||||||||||||
A Birthday Paradox for Markov Chains, with an Optimal Bound for Collision in the Pollard Rho Algorithm for Discrete Logarithm (English) | |||||||||||||||
Property / title: A Birthday Paradox for Markov Chains, with an Optimal Bound for Collision in the Pollard Rho Algorithm for Discrete Logarithm (English) / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Open document ID | |||||||||||||||
Property / zbMATH Open document ID: 1205.11135 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / DOI | |||||||||||||||
Property / DOI: 10.1007/978-3-540-79456-1_27 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / published in | |||||||||||||||
Property / published in: Lecture Notes in Computer Science / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / publication date | |||||||||||||||
27 May 2008
| |||||||||||||||
Property / publication date: 27 May 2008 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH DE Number | |||||||||||||||
Property / zbMATH DE Number: 5279301 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
Birthday Paradox | |||||||||||||||
Property / zbMATH Keywords: Birthday Paradox / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
Pollard rho | |||||||||||||||
Property / zbMATH Keywords: Pollard rho / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
self intersection | |||||||||||||||
Property / zbMATH Keywords: self intersection / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
collision time | |||||||||||||||
Property / zbMATH Keywords: collision time / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / MaRDI profile type | |||||||||||||||
Property / MaRDI profile type: MaRDI publication profile / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Wikidata QID | |||||||||||||||
Property / Wikidata QID: Q123010543 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / arXiv ID | |||||||||||||||
Property / arXiv ID: 0712.0220 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / OpenAlex ID | |||||||||||||||
Property / OpenAlex ID: W2051025109 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Random walks arising in random number generation / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q5317673 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: On the Chung-Diaconis-Graham random process / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: The range of stable random walks / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Markov chain intersections and the loop-erased walk / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Algorithmic Number Theory / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Non-Degeneracy of Pollard Rho Collisions / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q4828950 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.) / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: A monte carlo method for factorization / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Monte Carlo Methods for Index Computation (mod p) / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q3615927 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q3840196 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q2765016 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Parallel collision search with cryptanalytic applications / rank | |||||||||||||||
Normal rank |
Latest revision as of 19:53, 2 July 2024
scientific article; zbMATH DE number 5279301
- A Birthday Paradox for Markov Chains, with an Optimal Bound for Collision in the Pollard Rho Algorithm for Discrete Logarithm
Language | Label | Description | Also known as |
---|---|---|---|
English | A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm |
scientific article; zbMATH DE number 5279301 |
|
Statements
A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm (English)
0 references
A Birthday Paradox for Markov Chains, with an Optimal Bound for Collision in the Pollard Rho Algorithm for Discrete Logarithm (English)
0 references
6 May 2010
0 references
27 May 2008
0 references
The authors propose to show a Birthday Paradox for self-intersection of Markov chains with uniform stationary distribution. The Birthday Paradox states that if \(C\sqrt{N}\) items are sampled uniformly at random with replacement from a set of \(N\) items, for large \(C\) with high probability, some items will be chosen twice. This can be interpreted as a statement that with high probability, a Markov chain on the complete graph \(K_N\) with transitions \(P(i, j)= 1/N\) will intersect its past in \(C\sqrt{N}\) steps. The authors refer to such a self-intersection as a collision and say the collision time is \(O(\sqrt{N})\). After an Introduction (Section 1), in Section 2 some preliminaries are given: an introduction to the Pollard Rho algorithm and a simple multiplicative bound on the collision time in terms of the mixing time. Then in Section 3 (collision time) the more general Birthday Paradox for Markov chains with uniform stationary distribution is discussed. The main result of this section is given in Theorem 3.2 (``Birthday Paradox for Markov chains''). Finally an example related to this theorem is discussed. The main result of the paper (Theorem 4.2) is presented in Section 4 entitled Convergence of the Rho walk. Some auxiliary results, used to prove this theorem, are given too. The authors finish in the last section (Distinguished point methods) by proving similar results for the distinguished points method of parallelizing the algorithm. The paper contains also an ``Appendix'' in which the theorem 4.7 given in Section 4 is proved. It is a good and instructive paper.
0 references
Pollard's Rho
0 references
discrete logarithm
0 references
Markov chain
0 references
mixing time
0 references
Birthday Paradox
0 references
Pollard rho
0 references
self intersection
0 references
collision time
0 references