Content deleted Content added
No edit summary |
mNo edit summary |
||
Line 7:
'''Output''' Integer ''x'', such that ''e = g<sup>x</sup> (mod p)''.
<math>\phi(p)=p_0\cdot p_1 \cdot \ldots \cdot p_n</math>
#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]] :
:<math>\begin{matrix}e^{\phi(p)/p_1} & = & (g^x)^{\phi(p)/p_1} \pmod{p} \\
Line 23:
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 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 simulatious congruencies so that ''x'' can be solved using the [[Chinese remainder theorem]].
{{math-stub}}
| |||