Content deleted Content added
Cleanup: It is clearly incorrect to italicize digits in this context; "align" rather than "matrix" is right TeX here (look at the difference in appearance!); and "baby" is a common noun. |
further such cleanups: neither the parentheses nor the word "mod" should be italicized here; see WP:MOSMATH; also some other math notation edits |
||
Line 3:
The algorithm was discovered by Roland Silver, but first published by [[Stephen Pohlig]] and [[Martin Hellman]] (independent of Silver).
We will explain the algorithm in terms of the group formed by taking all the elements of '''Z'''<sub>''p''</sub> which are [[coprime]] to ''p'', and leave it to the advanced reader to extend the algorithm to other groups by using [[Lagrange's_theorem_(group_theory)|Lagrange's
:'''Input''' Integers ''p'', ''g'', ''e''.
:'''Output''' Integer ''x'', such that ''e'' ≡ ''g''<sup>''x''</sup> (mod ''p
:#Determine the prime factorization of the order of the group (the [[totient]] in this case) : <br><center><math>\varphi(p)= p_1\cdot p_2 \
:#From the [[remainder theorem]] we know that ''x'' = ''a''<sub>1</sub> ''p''<sub>1</sub> + ''b''<sub>1</sub>. We now find the value of ''b<sub>1</sub>'' for which the following equation holds using a fast algorithm such as [[baby-step giant-step]] :<br> <center><math>
\begin{align}e^{\varphi(p)/p_1} & \equiv (g^x)^{\varphi(p)/p_1} \pmod{p} \\
| |||