Pollard's rho algorithm for logarithms: Difference between revisions

Revision as of 10:31, 3 December 2023

Latest revision as of 18:02, 2 August 2024

(One intermediate revision by one other user not shown)

Line 38:

'''output:''' An integer ''x'' such that ''a^x'' = ''b'', or failure

Initialise ''i'' ← 0, ''a''₀ ← 0, ''b''₀ ← 0, ''x''₀ ← 1 ∈ ''G''

''i'' ← 1

'''loop'''

''x_i'' ← ''f''(''x''_{''i''- + 1}),

''a_i'' ← ''g''(''x''_''i''-1, ''a''_''i''-1),

''b_i'' ← ''h''(''x''_''i''-1, ''b''_''i''-1)

''x''_2''i''-1'' ← ''f''(''x''_2''i''-2−1),

''a''_2''i''-1'' ← ''g''(''x''_2''i''-2−1, ''a''_2''i''-2−1),

''b''_2''i''-1'' ← ''h''(''x''_2''i''-2−1, ''b''_2''i''-2−1)

''x''_2''i'' ← ''f''(''x''_2''i''-1),

''a''_2''i'' ← ''g''(''x''_2''i''-1, ''a''_2''i''-1),

''b''_2''i'' ← ''h''(''x''_2''i''-1, ''b''_2''i''-1)

''x'if'<sub>2'' i''x_i−1'' =&larr; ''f''(''x''_2''i''−2 '''then'''),

''ra''_2''i''−1 &larr; ''bg''(''x''_2''i''−2'' -, ''ba''_2''i''−2),

''b''_2''i''−1'' &larr; ''h''(''x''_2''i''-1−2, ''b''_2''i''-1−2)

'''if''' r = 0 '''return failure'''

''x''_2''i'' &larr; ''rf''⁻¹(''ax''_2''i''−1 - ''a_i'') mod ''n'',

''a''_2''i'''' &larr; ''g''(''x''_2''i''-1−1, ''a''_2''i''-1−1),

'''return''' ''x''

''b'else'_{2'' <i>// ''x_i'' &nelarr; ''h''(''x''_2''i''−1, ''b''}2''i''−1</sub>)

'''while''' ''x_i'' &larrne; ''x''_{2''i'' + 1}

'''end if'''

''r'' &larr; ''x''b_2''i'''' &larr;− ''f''(''xb''_2''i''-1),

'''end loop'''

'''if''' r = 0 '''return failure'''

'''return''' ''r''^{<span class="nowrap" style="padding-left:0.1em">−1</span>}(''a''_2''i'' − ''a_i'') mod ''n''

==Example==

Line 121 ⟶ 117:

{{Reflist}}

*{{cite journal |first=J. M. |last=Pollard |title=Monte Carlo methods for index computation (mod ''p'') |journal=[[Mathematics of Computation]] |volume=32 |year=1978 |issue=143 |pages=918–924 |doi= 10.2307/2006496 |jstor=2006496 }}

*{{cite book |first1=Alfred J. |last1=Menezes |first2=Paul C. |last2=van Oorschot |first3=Scott A. |last3=Vanstone |chapter-url=httphttps://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf |title=Handbook of Applied Cryptography |chapter=Chapter 3 |year=2001 }}

{{Number-theoretic algorithms}}