Content deleted Content added
No edit summary |
No edit summary |
||
Line 11:
<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} \\
& = & g^{\phi(p)}g^{b_1\phi(p)/p_1} \pmod{p} \\
& = & (g^{
\end{matrix}
</math> (using [[Euler's theorem]])
| |||