Content deleted Content added
m Reverted 1 edit by 103.86.23.15 (talk) to last revision by 128.30.60.184. (TW) |
|||
Line 110:
That is <math>2^{681} 5^{378} = 1010 = 2^{301} 5^{416} \pmod{1019}</math> and so <math>(416-378)\gamma = 681-301 \pmod{1018}</math>, for which <math>\gamma_1=10</math> is a solution as expected. As <math>n=1018</math> is not prime, there is another solution <math>\gamma_2=519</math>, for which <math>2^{519} = 1014 = -5\pmod{1019}</math> holds.
==Complexity==
The running time is approximately <math>\mathcal{O}(\sqrt{n})</math>. If used together with the [[Pohlig–Hellman algorithm|Pohlig-Hellman algorithm]], the running time of the combined algorithm is <math>\mathcal{O}(\sqrt{p})</math>, where <math>p</math> is the largest prime factor of <math>n</math>.
==References==
| |||