Pohlig–Hellman algorithm: Difference between revisions

Revision as of 11:07, 11 July 2005

Revision as of 02:58, 13 July 2005

Line 14:

\end{matrix}

</math> (using [[Euler's theorem]])</center><br>Note that if <math>g^{\phi(p)/p_1} = 1 \pmod{p}</math> then the order of ''g'' is less than ø(''p'') and <math>e^{\phi(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''₁=0.<br><br>The same operation is now performed for ''p₂'' up to ''p_n''.<br><br>A minor modification is needed where a prime number is repeated. Suppose we are seeing ''p_i'' for the ''k+1''-th time. Then we already know ''c_i'' in the equation ''x = a_i p_i^k+1 + b_i p_i^k+c_i'', and we find ''b_i'' the same way as before.

#We end up with enough simultaneous congruenciescongruences so that ''x'' can be solved using the [[Chinese remainder theorem]].

{{math-stub}}