#!/usr/bin/env sage -python
#
# An implementation of the Pohlig-Hellman discrete logarithm algorithm.
#
# Computes discrete log base alpha of beta, modulo q^c 
# - alpha is a primitive element modulo p
# - q is prime, p-1=0 (mod q^c), p-1<>0 (mod q^(c+1))
# Returns list a of indices into gamma
#
# Adapted from pseudocode found on p. 169 of
# _Cryptography: Theory and Practice_. Stinson, D. R., CRC Press, 1995.
#
# Stephen Forrest, http://wandership.ca/

import sys 
from sage.all import * 

def PohligHellman (p, alpha, beta, q, c):
    a = [ 0 for i in range(0,c) ]
    R = IntegerModRing(p)
    alpha_R = R(alpha)
    gamma = [ alpha_R ** ((p-1)*i/q) for i in range(0,q) ]
    beta_j = R(beta);
    for j in range(0,c):
        delta = beta_j ** ((p-1)/q**(j+1))
        a[j] = gamma.index( delta );
        beta_j = beta_j * alpha_R ** (-a[j] * q**j)
    return(a)

# Examples
print PohligHellman( 29, 2, 18, 2, 2 )
print PohligHellman( 29, 2, 18, 7, 1 )