import itertools
def HPSonP (Generator, Target, P):
    Unknown = 0
    N = P - 1
    K = factor(N)
    K = list(K)
    #print K
    for pk in K:
        #print pk
        primes =pk[0]
        powers = pk[1]
        Z = N / primes
        chi = power_mod(int(Generator), int(Z),int(P))
        n = 0
        t = [0]*powers
        a = [0]*powers
        d = [0]*powers
        for j in range(0, powers):
            #print j
            if j == 0:
                a[j - 1] = Target
            else:
                Z2 = (d[j - 1 - 1] * power_mod(int(primes),int(j - 1),int(N))) % N
                Pt = power_mod(int(Generator), int(Z2),int(P))# % P
                a[j-1] = (a[j - 1 - 1] / Pt) % P
            y = Z / primes ** j
            t[j-1] = power_mod(int(a[j - 1]),int(y),int(P))# % P
            s = 1
            for k in itertools.count():
                #print "k",k
                if t[j - 1] == s:
                    d[j - 1] = k
                    break
                s = (s * chi) % P
            n = (n + d[j - 1] * primes ** j) % N
        NN = N / primes ** powers
        X = (1 / NN) % primes ** powers
        Unknown = (Unknown + NN * n * X) % N
    #unassign(t)
    return(Unknown)



def Dirichlet (q):
    j=0
    #for j in numpy.arange(0.10e1, infinity + 0.10e1, 0.10e1):
    while True:
        j+=1
        p = 2 * j * q + 1
        if is_prime(p) == True:
            return(p)

def findLargePrimitiveRoot(n,p):
    n=n+1
    eulerp = euler_phi(p)
    Q = list(factor(eulerp))
    while n<p:
        found = True
        for Q2 in Q:
            q=Q2[0]
            totest = power_mod(ZZ(n),ZZ(eulerp/q),ZZ(p)) 
#            print(totest)
            if totest==1:
                found = False
        if found:
            return n
        n+=1

def ASCIIPad(Message):
    newList = []
    messLen = len(Message)
    tempIter = messLen - 1
    while tempIter >= 0:
        newList.append(Message[tempIter])
        tempIter -= 1
    x = [100+ord(newList[i]) for i in range(messLen)];
    x = ZZ(x,1000);
    return(x);

def ASCIIDepad(Number):
    n = Number.ndigits() % 3;
    if (n > 0):
        print("This is not a padded ASCII string\n");
    else:
        L = [((Number - (Number % (1000^i)))/1000^i)%1000 - 100 for i in range(Number.ndigits()/3)];
        N = "";
        for i in range(Number.ndigits()/3):
            N = chr(L[i]) + N;
        return(N)

################## Public Signature Key
P= 634404508895808192310313936486634711780110256438029402544697478374579200001
g= 369453800891893802517289247828810138682703208596756001785976436264055339058
b= 618412742800474831309763217987552595958100274226513299534696990325703710427

message="El Gamal"
M=ASCIIPad(message)
################# Trapdoor Information
y= 5823678520857072221167
r= 825693824659243777

################# Note that w=gcd(y,P-1)
w= 342569324756298365951
f=power_mod(b,w,P)
h=power_mod(g,w,P)
z=HPSonP(h,f,P)
################ Note that y=c*w
c=17
################ Creating a valid signature
s=((M-w*z*c)/r) % (P-1)
y= 5823678520857072221167
############### Verification that the signature (y,s) is a valid signature
V1= power_mod(y,s,P)*power_mod(b,y,P) % P
V2=power_mod(g,M,P)