Pohlig–Hellman algorithm

<h2 id="groups-of-prime-power-order">Groups of prime-power order</h2>
<p>As an important special case, which is used as a subroutine in the general algorithm (see below), the Pohlig–Hellman algorithm applies to <a href="/facts/Group_(mathematics)/IQTYqINt">groups</a> whose order is a <a href="/facts/Prime_power/R0vo3uYp">prime power</a>. The basic idea of this algorithm is to iteratively compute the 
  
    
      
        p
      
    
    {\displaystyle p}
  
-adic digits of the logarithm by repeatedly "shifting out" all but one unknown digit in the exponent, and computing that digit by elementary methods.
</p><p>(Note that for readability, the algorithm is stated for cyclic groups — in general, 
  
    
      
        G
      
    
    {\displaystyle G}
  
 must be replaced by the subgroup 
  
    
      
        ⟨
        g
        ⟩
      
    
    {\displaystyle \langle g\rangle }
  
 generated by 
  
    
      
        g
      
    
    {\displaystyle g}
  
, which is always cyclic.)
</p>
Input. A cyclic group 
  
    
      
        G
      
    
    {\displaystyle G}
  
 of order 
  
    
      
        n
        =
        
          p
          
            e
          
        
      
    
    {\displaystyle n=p^{e}}
  
 with generator 
  
    
      
        g
      
    
    {\displaystyle g}
  
 and an element 
  
    
      
        h
        ∈
        G
      
    
    {\displaystyle h\in G}
  
.
Output. The unique integer 
  
    
      
        x
        ∈
        {
        0
        ,
        …
        ,
        n
        −
        1
        }
      
    
    {\displaystyle x\in \{0,\dots ,n-1\}}
  
 such that 
  
    
      
        
          g
          
            x
          
        
        =
        h
      
    
    {\displaystyle g^{x}=h}
  
.
<ol><li>Initialize 
  
    
      
        
          x
          
            0
          
        
        :=
        0.
      
    
    {\displaystyle x_{0}:=0.}
  
</li>
<li>Compute 
  
    
      
        γ
        :=
        
          g
          
            
              p
              
                e
                −
                1
              
            
          
        
      
    
    {\displaystyle \gamma :=g^{p^{e-1}}}
  
. By <a href="/facts/Lagrange%27s_theorem_(group_theory)/VgyNjGlz">Lagrange's theorem</a>, this element has order 
  
    
      
        p
      
    
    {\displaystyle p}
  
.</li>
<li>For all 
  
    
      
        k
        ∈
        {
        0
        ,
        …
        ,
        e
        −
        1
        }
      
    
    {\displaystyle k\in \{0,\dots ,e-1\}}
  
, do:
<ol><li>Compute 
  
    
      
        
          h
          
            k
          
        
        :=
        (
        
          g
          
            −
            
              x
              
                k
              
            
          
        
        h
        
          )
          
            
              p
              
                e
                −
                1
                −
                k
              
            
          
        
      
    
    {\displaystyle h_{k}:=(g^{-x_{k}}h)^{p^{e-1-k}}}
  
. By construction, the order of this element must divide 
  
    
      
        p
      
    
    {\displaystyle p}
  
, hence 
  
    
      
        
          h
          
            k
          
        
        ∈
        ⟨
        γ
        ⟩
      
    
    {\displaystyle h_{k}\in \langle \gamma \rangle }
  
.</li>
<li>Using the <a href="/facts/Baby-step_giant-step/AWR8opeS">baby-step giant-step algorithm</a>, compute 
  
    
      
        
          d
          
            k
          
        
        ∈
        {
        0
        ,
        …
        ,
        p
        −
        1
        }
      
    
    {\displaystyle d_{k}\in \{0,\dots ,p-1\}}
  
 such that 
  
    
      
        
          γ
          
            
              d
              
                k
              
            
          
        
        =
        
          h
          
            k
          
        
      
    
    {\displaystyle \gamma ^{d_{k}}=h_{k}}
  
. It takes time <a href="/facts/Big_O_notation/weFFjSWg">
  
    
      
        O
        (
        
          
            p
          
        
        )
      
    
    {\displaystyle O({\sqrt {p}})}
  
</a>.</li>
<li>Set 
  
    
      
        
          x
          
            k
            +
            1
          
        
        :=
        
          x
          
            k
          
        
        +
        
          p
          
            k
          
        
        
          d
          
            k
          
        
      
    
    {\displaystyle x_{k+1}:=x_{k}+p^{k}d_{k}}
  
.</li></ol></li>
<li>Return 
  
    
      
        
          x
          
            e
          
        
      
    
    {\displaystyle x_{e}}
  
.</li></ol>
<p>The algorithm computes discrete logarithms in time complexity <a href="/facts/Big_O_notation/weFFjSWg">
  
    
      
        O
        (
        e
        
          
            p
          
        
        )
      
    
    {\displaystyle O(e{\sqrt {p}})}
  
</a>, far better than the <a href="/facts/Baby-step_giant-step/AWR8opeS">baby-step giant-step algorithm's</a> <a href="/facts/Big_O_notation/weFFjSWg">
  
    
      
        O
        (
        
          
            
              p
              
                e
              
            
          
        
        )
      
    
    {\displaystyle O({\sqrt {p^{e}}})}
  
</a> when 
  
    
      
        e
      
    
    {\displaystyle e}
  
 is large.
</p>
<h2 id="the-general-algorithm">The general algorithm</h2>
<p>In this section, we present the general case of the Pohlig–Hellman algorithm. The core ingredients are the algorithm from the previous section (to compute a logarithm modulo each prime power in the group order) and the <a href="/facts/Chinese_remainder_theorem/7wwFIkuV">Chinese remainder theorem</a> (to combine these to a logarithm in the full group).
</p><p>(Again, we assume the group to be cyclic, with the understanding that a non-cyclic group must be replaced by the subgroup generated by the logarithm's base element.)
</p>
Input. A cyclic group 
  
    
      
        G
      
    
    {\displaystyle G}
  
 of order 
  
    
      
        n
      
    
    {\displaystyle n}
  
 with generator 
  
    
      
        g
      
    
    {\displaystyle g}
  
, an element 
  
    
      
        h
        ∈
        G
      
    
    {\displaystyle h\in G}
  
, and a prime factorization 
  
    
      
        n
        =
        
          ∏
          
            i
            =
            1
          
          
            r
          
        
        
          p
          
            i
          
          
            
              e
              
                i
              
            
          
        
      
    
    {\textstyle n=\prod _{i=1}^{r}p_{i}^{e_{i}}}
  
.
Output. The unique integer 
  
    
      
        x
        ∈
        {
        0
        ,
        …
        ,
        n
        −
        1
        }
      
    
    {\displaystyle x\in \{0,\dots ,n-1\}}
  
 such that 
  
    
      
        
          g
          
            x
          
        
        =
        h
      
    
    {\displaystyle g^{x}=h}
  
.
<ol><li>For each 
  
    
      
        i
        ∈
        {
        1
        ,
        …
        ,
        r
        }
      
    
    {\displaystyle i\in \{1,\dots ,r\}}
  
, do:
<ol><li>Compute 
  
    
      
        
          g
          
            i
          
        
        :=
        
          g
          
            n
            
              /
            
            
              p
              
                i
              
              
                
                  e
                  
                    i
                  
                
              
            
          
        
      
    
    {\displaystyle g_{i}:=g^{n/p_{i}^{e_{i}}}}
  
. By <a href="/facts/Lagrange%27s_theorem_(group_theory)/VgyNjGlz">Lagrange's theorem</a>, this element has order 
  
    
      
        
          p
          
            i
          
          
            
              e
              
                i
              
            
          
        
      
    
    {\displaystyle p_{i}^{e_{i}}}
  
.</li>
<li>Compute 
  
    
      
        
          h
          
            i
          
        
        :=
        
          h
          
            n
            
              /
            
            
              p
              
                i
              
              
                
                  e
                  
                    i
                  
                
              
            
          
        
      
    
    {\displaystyle h_{i}:=h^{n/p_{i}^{e_{i}}}}
  
. By construction, 
  
    
      
        
          h
          
            i
          
        
        ∈
        ⟨
        
          g
          
            i
          
        
        ⟩
      
    
    {\displaystyle h_{i}\in \langle g_{i}\rangle }
  
.</li>
<li>Using the algorithm above in the group 
  
    
      
        ⟨
        
          g
          
            i
          
        
        ⟩
      
    
    {\displaystyle \langle g_{i}\rangle }
  
, compute 
  
    
      
        
          x
          
            i
          
        
        ∈
        {
        0
        ,
        …
        ,
        
          p
          
            i
          
          
            
              e
              
                i
              
            
          
        
        −
        1
        }
      
    
    {\displaystyle x_{i}\in \{0,\dots ,p_{i}^{e_{i}}-1\}}
  
 such that 
  
    
      
        
          g
          
            i
          
          
            
              x
              
                i
              
            
          
        
        =
        
          h
          
            i
          
        
      
    
    {\displaystyle g_{i}^{x_{i}}=h_{i}}
  
.</li></ol></li>
<li>Solve the simultaneous congruence 
  
    
      
        x
        ≡
        
          x
          
            i
          
        
        
          
          (
          mod
          
          
            p
            
              i
            
            
              
                e
                
                  i
                
              
            
          
          )
        
        
        ∀
        i
        ∈
        {
        1
        ,
        …
        ,
        r
        }
        
          .
        
      
    
    {\displaystyle x\equiv x_{i}{\pmod {p_{i}^{e_{i}}}}\quad \forall i\in \{1,\dots ,r\}{\text{.}}}
  
The <a href="/facts/Chinese_remainder_theorem/7wwFIkuV">Chinese remainder theorem</a> guarantees there exists a unique solution 
  
    
      
        x
        ∈
        {
        0
        ,
        …
        ,
        n
        −
        1
        }
      
    
    {\displaystyle x\in \{0,\dots ,n-1\}}
  
.</li>
<li>Return 
  
    
      
        x
      
    
    {\displaystyle x}
  
.</li></ol>
<p>The correctness of this algorithm can be verified via the <a href="/facts/Abelian_group/FfWwmx4R">classification of finite abelian groups</a>: Raising 
  
    
      
        g
      
    
    {\displaystyle g}
  
 and 
  
    
      
        h
      
    
    {\displaystyle h}
  
 to the power of 
  
    
      
        n
        
          /
        
        
          p
          
            i
          
          
            
              e
              
                i
              
            
          
        
      
    
    {\displaystyle n/p_{i}^{e_{i}}}
  
 can be understood as the projection to the factor group of order 
  
    
      
        
          p
          
            i
          
          
            
              e
              
                i
              
            
          
        
      
    
    {\displaystyle p_{i}^{e_{i}}}
  
.
</p>
<h2 id="complexity">Complexity</h2>
<p>The worst-case input for the Pohlig–Hellman algorithm is a group of prime order: In that case, it degrades to the <a href="/facts/Baby-step_giant-step/AWR8opeS">baby-step giant-step algorithm</a>, hence the worst-case time complexity is 
  
    
      
        
          
            O
          
        
        (
        
          
            n
          
        
        )
      
    
    {\displaystyle {\mathcal {O}}({\sqrt {n}})}
  
. However, it is much more efficient if the order is smooth: Specifically, if 
  
    
      
        
          ∏
          
            i
          
        
        
          p
          
            i
          
          
            
              e
              
                i
              
            
          
        
      
    
    {\displaystyle \prod _{i}p_{i}^{e_{i}}}
  
 is the prime factorization of 
  
    
      
        n
      
    
    {\displaystyle n}
  
, then the algorithm's complexity is 
  
    
      
        
          
            O
          
        
        
          (
          
            
              ∑
              
                i
              
            
            
              
                e
                
                  i
                
              
              (
              log
              ⁡
              n
              +
              
                
                  
                    p
                    
                      i
                    
                  
                
              
              )
            
          
          )
        
      
    
    {\displaystyle {\mathcal {O}}\left(\sum _{i}{e_{i}(\log n+{\sqrt {p_{i}}})}\right)}
  
 group operations.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<h2 id="notes">Notes</h2>

<ul><li>Mollin, Richard (2006-09-18). <a href="https://archive.org/details/An_Introduction_to_Cryptography_Second_Edition"><i>An Introduction To Cryptography</i></a> (2nd ed.). Chapman and Hall/CRC. p. <a href="https://archive.org/details/An_Introduction_to_Cryptography_Second_Edition/page/n353">344</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-58488-618-1.</li>
<li>Pohlig, S.; <a href="/facts/Martin_Hellman/QCxKCFgn">Hellman, M.</a> (1978). <a href="http://www-ee.stanford.edu/~hellman/publications/28.pdf">"An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance"</a> (PDF). <i>IEEE Transactions on Information Theory</i> (24): 106–110. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FTIT.1978.1055817">10.1109/TIT.1978.1055817</a>.</li>
<li><a href="/facts/Alfred_Menezes/nduu6dew">Menezes, Alfred J.</a>; <a href="/facts/Paul_van_Oorschot/zHRUkK4P">van Oorschot, Paul C.</a>; <a href="/facts/Scott_Vanstone/KcQlUQAY">Vanstone, Scott A.</a> (1997). <a href="http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf">"Number-Theoretic Reference Problems"</a> (PDF). <a href="https://archive.org/details/handbookofapplie0000mene/page/107"><i>Handbook of Applied Cryptography</i></a>. <a href="/facts/CRC_Press/duTuH4hz">CRC Press</a>. pp. <a href="https://archive.org/details/handbookofapplie0000mene/page/107">107–109</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-8493-8523-7.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Mollin 2006, pg. 344 - Mollin, Richard (2006-09-18). An Introduction To Cryptography (2nd ed.). Chapman and Hall/CRC. p. 344. ISBN 978-1-58488-618-1. <a href="https://archive.org/details/An_Introduction_to_Cryptography_Second_Edition" target="_blank">https://archive.org/details/An_Introduction_to_Cryptography_Second_Edition</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Pohlig & Hellman 1978. - Pohlig, S.; Hellman, M. (1978). "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance" (PDF). IEEE Transactions on Information Theory (24): 106–110. doi:10.1109/TIT.1978.1055817. <a href="http://www-ee.stanford.edu/~hellman/publications/28.pdf" target="_blank">http://www-ee.stanford.edu/~hellman/publications/28.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Menezes, et al. 1997, pg. 108 - Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (1997). "Number-Theoretic Reference Problems" (PDF). Handbook of Applied Cryptography. CRC Press. pp. 107–109. ISBN 0-8493-8523-7. <a href="http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf" target="_blank">http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Pohlig–Hellman algorithm open-in-new

Pohlig–Hellman algorithm