Miscellaneous generic functions¶
https://doc.sagemath.org/html/en/reference/groups/sage/groups/generic.html
In [1]:
Copied!
from sage.groups.generic import * # some generic group functions (like bsgs) need to be imported explicitly
from sage.groups.generic import * # some generic group functions (like bsgs) need to be imported explicitly
DLP 离散对数问题 ¶
DLP 指的是离散对数问题（Discrete Logarithm Problem
基本参数说明：求解以
base为底，a的对数；ord为base的阶，可以缺省；operation可以是+与*，默认为*；bounds是一个区间(ld,ud)，需要保证所计算的对数在此区间内。
即：$base^k≡a\pmod p$
sage 求解 ¶
k = discrete_log(a, base, ord=None, bounds=None, operation='*', identity=None, inverse=None, op=None, algothrim='bsgs')- 可以看到，
discrete_log可以选择使用bsgsrholambda算法，默认为bsgs算法。 - 其他使用方式
k = discrete_log(mod(a, p), mod(base, p)) - 等价名：
discrete_log_generic
- 可以看到，
或者我们可以用以下的方式来指定求解离散对数使用的算法：
bsgs(base, a, bounds, operation='*')- 小步大步法。
discrete_log_lambda(a, base, bounds, operation='*')- 求离散对数的 Pollard-kangaroo 算法（也称为 lambda 算法
） 。 - It uses only a logarithmic amount of memory. It’s useful if you have bounds on the logarithm. If you are computing logarithms in a whole finite group, you should use Pollard Rho algorithm.
- 求离散对数的 Pollard-kangaroo 算法（也称为 lambda 算法
discrete_log_rho(a, base, ord=None, operation='*')- 求离散对数的 Pollard-Rho 算法。
- Pollard Rho algorithm for computing discrete logarithm in cyclic group of prime order. If the group order is very small it falls back to the baby step giant step algorithm.
使用 log ¶
使用 help(discrete_log) 我们会看到其中有这么一句话：
manual
.. WARNING::
If ``x`` has a ``log`` method, it is likely to be vastly faster
than using this function. E.g., if ``x`` is an integer modulo
`n`, use its ``log`` method instead!
那么实现了 log 的对象有哪些呢？
- Finite Fields
- Elliptic Curves
- ...
In [2]:
Copied!
p = 0x10001
F = GF(p)
g = F.primitive_element() # 原根
# g = F.multiplicative_generator() # 乘法生成元
print("g:", g)
x = 10086
# g^x = c mod p
c = g**x
discrete_log(c, g), discrete_log(mod(c,p), mod(g,p)), c.log(g) # the last use method is talked below
p = 0x10001
F = GF(p)
g = F.primitive_element() # 原根
# g = F.multiplicative_generator() # 乘法生成元
print("g:", g)
x = 10086
# g^x = c mod p
c = g**x
discrete_log(c, g), discrete_log(mod(c,p), mod(g,p)), c.log(g) # the last use method is talked below
g: 3
Out[2]:
(10086, 10086, 10086)
In [3]:
Copied!
def Pohlig_Hellman_DLP(g, a, p):
""" Pohlig-Hellman algorithm for solving DLP in a cyclic group of prime order."""
# Get the order of multiplicative group
order = p - 1
# Factor the order
factors, exponents = zip(*factor(order))
# Calculate prime powers
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
dlogs = []
print(f"Group order: {order}")
print(f"Prime factors: {factors}")
print(f"Prime powers: {primes}")
for fac in primes:
# Calculate t = order/fac
t = int(order // fac)
# Calculate subgroup elements
gt = power_mod(g, t, p)
at = power_mod(a, t, p)
# Solve DLP in subgroup
dlog = discrete_log(at, gt, p)
dlogs.append(dlog)
print(f"factor: {fac}, Discrete Log: {dlog}")
# Use Chinese Remainder Theorem to get final result
return crt(dlogs, primes)
def Pohlig_Hellman_DLP(g, a, p):
""" Pohlig-Hellman algorithm for solving DLP in a cyclic group of prime order."""
# Get the order of multiplicative group
order = p - 1
# Factor the order
factors, exponents = zip(*factor(order))
# Calculate prime powers
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
dlogs = []
print(f"Group order: {order}")
print(f"Prime factors: {factors}")
print(f"Prime powers: {primes}")
for fac in primes:
# Calculate t = order/fac
t = int(order // fac)
# Calculate subgroup elements
gt = power_mod(g, t, p)
at = power_mod(a, t, p)
# Solve DLP in subgroup
dlog = discrete_log(at, gt, p)
dlogs.append(dlog)
print(f"factor: {fac}, Discrete Log: {dlog}")
# Use Chinese Remainder Theorem to get final result
return crt(dlogs, primes)
In [4]:
Copied!
n = 2*2*3*5*7*31*41
factors , exps = zip(*factor(n))
print(factor(n), factors, exps, sep=' | ')
n = 2*2*3*5*7*31*41
factors , exps = zip(*factor(n))
print(factor(n), factors, exps, sep=' | ')
2^2 * 3 * 5 * 7 * 31 * 41 | (2, 3, 5, 7, 31, 41) | (2, 1, 1, 1, 1, 1)
Pohlig_Hellman¶
如果群的阶数（即群元素个数）可被因式分解（称为光滑的
In [ ]:
Copied!
def FF_Pohlig_Hellman(g, a, p):
""" Pohlig-Hellman algorithm for solving DLP in a Finite field group of prime order."""
# Get the order of multiplicative group
order = p - 1
# Factor the order
factors = list(factor(E.order()))[:-1] # remove the last some factor to be faster
primes = [i**j for i,j in factors]
dlogs = []
print(f"Group order: {order}")
print(f"Prime factors: {factors}")
print(f"Prime powers: {primes}")
for fac in primes:
# Calculate t = order/fac
t = int(order // fac)
# Calculate subgroup elements
gt = power_mod(g, t, p)
at = power_mod(a, t, p)
# Solve DLP in subgroup
dlog = discrete_log(at, gt, p)
dlogs.append(dlog)
print(f"factor: {fac}, Discrete Log: {dlog}")
return crt(dlogs, primes)
def FF_Pohlig_Hellman(g, a, p):
""" Pohlig-Hellman algorithm for solving DLP in a Finite field group of prime order."""
# Get the order of multiplicative group
order = p - 1
# Factor the order
factors = list(factor(E.order()))[:-1] # remove the last some factor to be faster
primes = [i**j for i,j in factors]
dlogs = []
print(f"Group order: {order}")
print(f"Prime factors: {factors}")
print(f"Prime powers: {primes}")
for fac in primes:
# Calculate t = order/fac
t = int(order // fac)
# Calculate subgroup elements
gt = power_mod(g, t, p)
at = power_mod(a, t, p)
# Solve DLP in subgroup
dlog = discrete_log(at, gt, p)
dlogs.append(dlog)
print(f"factor: {fac}, Discrete Log: {dlog}")
return crt(dlogs, primes)