Content deleted Content added
m Bot: Migrating 1 interwiki links, now provided by Wikidata on d:Q1755812 |
The formula listed is not the totient. It is unclear why the author referenced that. |
||
Line 8:
:'''Output''' An Integer ''x'', such that ''e'' ≡ ''g''<sup>''x''</sup> (mod ''p'') (if one exists).
:#Determine the prime factorization of the order of the group
:#From the [[Chinese remainder theorem]] it will be sufficient to determine the values of ''x'' modulo each prime power dividing the group order. Suppose for illustration that ''p''<sub>1</sub> divides this order but ''p''<sub>1</sub><sup>2</sup> does not. Then we need to determine ''x'' mod ''p''<sub>1</sub>, that is, we need to know the ending coefficient ''b''<sub>1</sub> in the base-''p<sub>1</sub>'' expansion of ''x'', i.e. in the expansion ''x'' = ''a''<sub>1</sub> ''p''<sub>1</sub> + ''b''<sub>1</sub>. We can find the value of ''b<sub>1</sub>'' by examining all the possible values between 0 and ''p''<sub>1</sub>-1. (We may also use a faster algorithm such as [[baby-step giant-step]] when the order of the group is prime.<ref name="Menezes97p109">[[#Menezes97|Menezes, et. al 1997]], pg. 109</ref>) The key behind the examination is that:<br> <center><math>
\begin{align}e^{\varphi(p)/p_1} & \equiv (g^x)^{\varphi(p)/p_1} \pmod{p} \\
| |||