Content deleted Content added
m Fix common mistake "a the". See: WP:FCM. |
No edit summary |
||
Line 3:
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.
:'''Input''' Integers ''p'', ''g'', ''e''.
:'''Output''' Integer ''x'', such that ''e ≡ g<sup>x</sup> (mod p)''.▼
:#Use [[Euler's totient function]] to determine the prime factorization of the order of the group : <br><center><math>\varphi(p)= p_0\cdot p_1 \cdot \ldots \cdot p_n</math></center>▼
▲'''Output''' Integer ''x'', such that ''e ≡ g<sup>x</sup> (mod p)''.
:#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>▼
▲#Use [[Euler's totient function]] to determine the prime factorization of the order of the group : <br><center><math>\varphi(p)= p_0\cdot p_1 \cdot \ldots \cdot p_n</math></center>
▲#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{matrix}e^{\varphi(p)/p_1} & \equiv & (g^x)^{\varphi(p)/p_1} \pmod{p} \\
& \equiv & (g^{\varphi(p)})^{a_1}g^{b_1\varphi(p)/p_1} \pmod{p} \\
Line 14 ⟶ 13:
\end{matrix}
</math> (using [[Euler's theorem]])</center><br>Note that if <math>g^{\varphi(p)/p_1} \equiv 1 \pmod{p}</math> then the order of ''g'' is less than φ(''p'') and <math>e^{\varphi(p)/p_1} \mod p</math> must be 1 for a solution to exist. In this case there will be more than one solution for ''x'' less than φ(''p''), but since we are not looking for the whole set, we can require that ''b''<sub>1</sub>=0.<br><br>The same operation is now performed for ''p<sub>2</sub>'' up to ''p<sub>n</sub>''.<br><br>A minor modification is needed where a prime number is repeated. Suppose we are seeing ''p<sub>i</sub>'' for the ''k+1''-th time. Then we already know ''c<sub>i</sub>'' in the equation ''x = a<sub>i</sub> p<sub>i</sub><sup>k+1</sup> + b<sub>i</sub> p<sub>i</sub><sup>k</sup>+c<sub>i</sub>'', and we find ''b<sub>i</sub>'' the same way as before.
:#We end up with enough simultaneous congruences so that ''x'' can be solved using the [[Chinese remainder theorem]].
{{Numtheory-stub}}
| |||