暗号学のPohlig-Helllimanアルゴリズムは離散対数を求めます
2101 ワード
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個の同余式を求め,最後に中国の残留定理を用いて離散対数の解を解く
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