Pollard's rho algorithm for logarithms
Pollard's rho algorithm for logarithms is an algorithm introduced by John Pollard in 1978 to solve the discrete logarithm problem, analogous to Pollard's rho algorithm to solve the integer factorization problem.
- Abstraction100002137
- Act100030358
- Activity100407535
- Algorithm105847438
- Communication100033020
- Event100029378
- Exponent106812417
- Logarithm106812631
- MathematicalNotation106808720
- Notation106808493
- Procedure101023820
- PsychologicalFeature100023100
- Rule105846932
- WikicatLogarithms
- WikicatNumberTheoreticAlgorithms
- Writing106359877
- WrittenCommunication106349220
- YagoPermanentlyLocatedEntity
- Comment
- enPollard's rho algorithm for logarithms is an algorithm introduced by John Pollard in 1978 to solve the discrete logarithm problem, analogous to Pollard's rho algorithm to solve the integer factorization problem.
- Has abstract
- enPollard's rho algorithm for logarithms is an algorithm introduced by John Pollard in 1978 to solve the discrete logarithm problem, analogous to Pollard's rho algorithm to solve the integer factorization problem. The goal is to compute such that , where belongs to a cyclic group generated by . The algorithm computes integers , , , and such that . If the underlying group is cyclic of order , by substituting as and noting that two powers are equal if and only if the exponents are equivalent modulo the order of the base, in this case modulo , we get that is one of the solutions of the equation . Solutions to this equation are easily obtained using the extended Euclidean algorithm. To find the needed , , , and the algorithm uses Floyd's cycle-finding algorithm to find a cycle in the sequence , where the function is assumed to be random-looking and thus is likely to enter into a loop of approximate length after steps. One way to define such a function is to use the following rules: Divide into three of approximately equal size: , , and . If is in then double both and ; if then increment , if then increment .
- Is primary topic of
- Pollard's rho algorithm for logarithms
- Label
- enPollard's rho algorithm for logarithms
- Link from a Wikipage to an external page
- www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf
- Link from a Wikipage to another Wikipage
- C++
- Category:Logarithms
- Category:Number theoretic algorithms
- Cyclic group
- Discrete logarithm
- Disjoint subsets
- Divisor
- Extended Euclidean algorithm
- Floyd's cycle-finding algorithm
- Function (mathematics)
- Group (mathematics)
- If and only if
- Integer
- Integer factorization
- John Pollard (mathematician)
- Mathematics of Computation
- Order of a group
- Pohlig–Hellman algorithm
- Pollard's rho algorithm
- Prime number
- SameAs
- 3jnb1
- Algorithme rho de Pollard (logarithme discret)
- Algoritmo rho de Pollard (logaritmos discretos)
- m.05j1tc
- Pollard's rho algorithm for logarithms
- Pollards rho-algoritme
- Q4053693
- Ро-метод Полларда для дискретного логарифмирования
- אלגוריתם רו של פולרד ללוגריתם הדיסקרטי
- ポラード・ロー離散対数アルゴリズム
- 离散对数的波拉德ρ算法
- Subject
- Category:Logarithms
- Category:Number theoretic algorithms
- WasDerivedFrom
- Pollard's rho algorithm for logarithms?oldid=1122150005&ns=0
- WikiPageLength
- 6950
- Wikipage page ID
- 1630817
- Wikipage revision ID
- 1122150005
- WikiPageUsesTemplate
- Template:Cite book
- Template:Cite journal
- Template:Number-theoretic algorithms
- Template:Reflist
- Template:Short description