暗号学のPohlig-Helllimanアルゴリズムは離散対数を求めます


1つの素数pについて、まずn=p-1を求め、それをx個の素数因子に分解し、各因子qとその指数cについてPohlig-Helllimanアルゴリズムを適用して解く(a 0,a 1,a 3............ac-1).
a=(for i=0 to c-1:ai*q^i)+s*q^(sはある整数)からx個の同余式を求め,最後に中国の残留定理を用いて離散対数の解を解く
# -*- coding: utf-8 -*-
_author_ = 'xiao_lu'
import sys
import time
the_a={}
# n        
def get_result(n):
   i=2
   while n!=1:
      if n%i==0:
           the_a[i]+=1
           n=n/i
      else: i+=1
#        
def extended_euclid(a,b,x,y):
    if b == 0:
         x[0] = 1
         y[0] = 0
         return a
    d = extended_euclid(b, a % b, y, x)
    y[0] -= a / b * x[0]
    return d
#      
def chinese_remainder(b ,w ,len):
    ret = 0;    n = 1
    x = [0];    y = [0]
    for i in range(len):
         n *= w[i];
    for i in range(len):
        m = n / w[i];
        d = extended_euclid(w[i],m,x,y);
        ret = (ret + y[0] * m * b[i]) % n;
    return (n + ret % n) % n;
#     Pohilg-helllman  
if __name__ == '__main__':
    t1 = time.time()
    print t1
    p,a,b = map(int, sys.stdin.readline().split())
    n = int(p)-1
    #   
    for i in range(2,10000):
        the_a.setdefault(i,0)
    #  n        
    get_result(int(n))
    chu=[];  yu=[]
    for key, value in the_a.items():
        if value != 0:
            #Pohlig-Helliman  
            j = 0
            A = []; B = []
            B.append(int(b))
            key1 = key
            while j <= int(value) - 1:
                x = (int(B[j])** (n/(key1)))%int(p)
                for i in range(0, 10000):
                    if x == (int(a)**((i * n) / int(key)))%int(p):
                        A.append(i)
                        break
                B.append(( B[j] * (int(a)**((-i) * (int(key)**j))))%int(p))
                j += 1
                key1 *= key
            s=0
            for ii in range(0,int(value)):
                # a
                s+=int(A[ii])*(int(key)**ii)
            chu.append(int(key)**int(value))
            yu.append(s)
    #              
    print  "log%d %d = %d"%(a,b,(chinese_remainder(yu,chu,len(yu))))
    t2 = time.time()
    print t2