A birthday paradox for Markov chains, with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm
Duration: 24 mins 33 secs
About this item
| Description: |
Montenegro, R (Massachusetts Lowell)
Wednesday 26 March 2008, 14:35-15:05 Markov-chain Monte Carlo Methods |
|---|
| Created: | 2008-04-01 14:28 | ||||
|---|---|---|---|---|---|
| Collection: | Combinatorics and Statistical Mechanics | ||||
| Publisher: | Isaac Newton Institute | ||||
| Copyright: | Montenegro, R | ||||
| Language: | eng (English) | ||||
| Credits: |
|
||||
| Abstract: | We show a Birthday Paradox for self-intersections of Markov chains with uniform stationary distribution. As an application, we analyze Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group G and find that, if the partition in the algorithm is given by a random oracle, then with high probability a collision occurs in order |G|^0.5 steps. This is the first proof of the correct order bound which does not assume that every step of the algorithm produces an i.i.d. sample from G.
Related Links * http://www.ravimontenegro.com/research/prho.pdf - Preprint of the paper |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 480x360 | 1.84 Mbits/sec | 339.48 MB | View | Download | |
| WebM | 480x360 | 438.01 kbits/sec | 78.81 MB | View | Download | |
| Flash Video | 480x360 | 803.36 kbits/sec | 145.04 MB | View | Download | |
| iPod Video | 480x360 | 505.22 kbits/sec | 91.21 MB | View | Download | |
| QuickTime | 384x288 | 847.6 kbits/sec | 153.03 MB | View | Download | |
| MP3 | 44100 Hz | 125.04 kbits/sec | 22.36 MB | Listen | Download | |
| Windows Media Video | 478.31 kbits/sec | 86.36 MB | View | Download | ||
| Auto * | (Allows browser to choose a format it supports) | |||||
